Problem Statement
Given an array of integers and a target sum, find the contiguous subarray (of size at least one) whose elements sum up to the given target. If multiple subarrays satisfy the condition, return any one of them.
Constraints
- The array can contain both positive and negative integers.
- The array size is between 1 and 10^5.
- Integer values in the array are between -10^9 and 10^9.
Example:
Example Explanation:
Output for Multiple Subarrays: If there are multiple contiguous subarrays that produce the desired sum, any one of them can be returned as the output. The problem statement does not specify any preference for a particular subarray, allowing flexibility in selecting the output.
Example
Example 1
Input: nums = [1, 4, 20, 3, 10, 5], target = 33
Output: [20, 3, 10]
Example 2
Input: nums = [1, 4, 0, 0, 3, 10, 5], target = 7
Output: [4, 0, 0, 3]
Example Explanation
In the first example, the subarray [20, 3, 10] has elements summing up to the target value 33. In the second example, the subarray [4, 0, 0, 3] has elements summing up to the target value 7.
What is the Output if We Get Multiple Such Sub-Arrays Producing the Desired Sum by Adding their Elements?
If there are multiple contiguous subarrays that produce the desired sum, any one of them can be returned as the output. The problem statement does not specify any preference for a particular subarray, allowing flexibility in selecting the output.
Approach 1 : Brute Force or Simple Approach
A possible approach could be to first generate all the subarrays, calculate the subarray sum and if it is equal to the given sum (i.e. the sum is equal to the given value k), return the starting and ending positions of that subarray; else return -1. This approach will work fine for both positive and negative elements in the array.
Thought Process
- Use two nested loops, one for the starting position and one for the ending position.
- At each iteration, check whether the subarray sum equals k
Return the starting position and ending position of the array
- If after all iterations, no subarray with a given sum equal to k is found, return -1.
Algorithm
- Initialize Variables:
- n as the length of the array.
- Loop through the array to generate starting points of subarrays.
- Generate Subarrays:
- For each starting point, generate subarrays by varying the ending point.
- Compute the sum of each subarray.
- Check Sum:
- If a subarray sum equals the target k, return the starting and ending indices of that subarray.
- If no such subarray is found after checking all possibilities, return -1.
Example
Input 1:
arr[] = {10, 20, -45, 45, 60}
k = 80
Output:
Subarray found between indices 1 and 4
Explanation:
The sum of elements from indices 1 to 4, i.e. 20 + (-45) + 45 + 60 = 80
Input 2:
arr[] = {1, 2, 4, 15, 0}
K = 30
Output:
No subarray with a given sum equal to k is found in the array.
Explanation: There is no subarray with a sum equals to 30 in the input array
Implementation
In the case of multiple subarrays with the given sum, the below code would only give the indices of the first such subarray. In case of no subarray with the given sum, a message will be displayed to the user.
- C
- C++
- Java
- Python
- Javascript
- C#
C
#include <stdio.h>
void findSubarrays(int arr[], int n, int k) {
for (int start = 0; start < n; start++) {
int subarray_sum = 0;
for (int end = start; end < n; end++) {
subarray_sum += arr[end];
if (subarray_sum == k) {
printf("Subarray found between indices %d and %d\n", start, end);
return;
}
}
}
printf("No subarray with given sum equal to %d is found in the array\n", k);
}
int main() {
int arr1[] = {10, 20, -45, 45, 60};
int k1 = 60;
findSubarrays(arr1, 5, k1);
int arr2[] = {1, 2, 4, 15, 0};
int k2 = 30;
findSubarrays(arr2, 5, k2);
return 0;
}
You can also try this code with Online C Compiler
C++
#include <iostream>
using namespace std;
void findSubarrays(int arr[], int n, int k) {
for (int start = 0; start < n; start++) {
int subarray_sum = 0;
for (int end = start; end < n; end++) {
subarray_sum += arr[end];
if (subarray_sum == k) {
cout << "Subarray found between indices " << start << " and " << end << endl;
return;
}
}
}
cout << "No subarray with given sum equal to " << k << " is found in the array" << endl;
}
int main() {
int arr1[] = {10, 20, -45, 45, 60};
int k1 = 60;
findSubarrays(arr1, 5, k1);
int arr2[] = {1, 2, 4, 15, 0};
int k2 = 30;
findSubarrays(arr2, 5, k2);
return 0;
}
You can also try this code with Online C++ Compiler
Java
public class SubArraySum {
// Function to find subarrays with the given sum in an array
public static void findSubarrays(int[] arr, int k) {
for (int start = 0; start < arr.length; start++) {
int subarray_sum = 0;
// consider all subarrays starting from `i` and ending at `j`
for (int end = start; end < arr.length; end++) {
// sum of elements so far
subarray_sum += arr[end];
// if the sum so far is equal to the given sum
if (subarray_sum == k) {
System.out.println("Subarray found between indices " + start + " and " + end);
return;
}
}
}
System.out.println("No subarray with given sum equal to " + k + " is found in the array");
}
public static void main(String[] args) {
int arr1[] = { 10, 20, -45, 45, 60 };
int k1 = 60;
findSubarrays(arr1, k1);
int arr2[] = { 1, 2, 4, 15, 0 };
int k2 = 30;
findSubarrays(arr2, k2);
}
}
You can also try this code with Online Java Compiler
Python
def find_subarrays(arr, k):
for start in range(len(arr)):
subarray_sum = 0
for end in range(start, len(arr)):
subarray_sum += arr[end]
if subarray_sum == k:
print(f"Subarray found between indices {start} and {end}")
return
print(f"No subarray with given sum equal to {k} is found in the array")
arr1 = [10, 20, -45, 45, 60]
k1 = 60
find_subarrays(arr1, k1)
arr2 = [1, 2, 4, 15, 0]
k2 = 30
find_subarrays(arr2, k2)
You can also try this code with Online Python Compiler
Javascript
function findSubarrays(arr, k) {
for (let start = 0; start < arr.length; start++) {
let subarray_sum = 0;
for (let end = start; end < arr.length; end++) {
subarray_sum += arr[end];
if (subarray_sum === k) {
console.log(`Subarray found between indices ${start} and ${end}`);
return;
}
}
}
console.log(`No subarray with given sum equal to ${k} is found in the array`);
}
let arr1 = [10, 20, -45, 45, 60];
let k1 = 60;
findSubarrays(arr1, k1);
let arr2 = [1, 2, 4, 15, 0];
let k2 = 30;
findSubarrays(arr2, k2);
You can also try this code with Online Javascript Compiler
C#
using System;
public class SubArraySum
{
public static void FindSubarrays(int[] arr, int k)
{
for (int start = 0; start < arr.Length; start++)
{
int subarray_sum = 0;
for (int end = start; end < arr.Length; end++)
{
subarray_sum += arr[end];
if (subarray_sum == k)
{
Console.WriteLine($"Subarray found between indices {start} and {end}");
return;
}
}
}
Console.WriteLine($"No subarray with given sum equal to {k} is found in the array");
}
public static void Main()
{
int[] arr1 = { 10, 20, -45, 45, 60 };
int k1 = 60;
FindSubarrays(arr1, k1);
int[] arr2 = { 1, 2, 4, 15, 0 };
int k2 = 30;
FindSubarrays(arr2, k2);
}
}
Complexity Analysis
- Time complexity: O(N2), where N is the size of the array. Since two nested loops are used.
- Space complexity: O(1), constant extra space is required.
Approach 2: Linear Complexity or Efficient Approach (Sliding Window Technique + Two Pointers technique)
Adding two positive numbers greater than 0 will give another positive number. For sure, this third number is greater than both of the numbers. This common fact is the key to solving a subarray with a given sum problem in an array with all positive integers.
That is if we keep adding more elements to the subarray, the subarray sum is bound to increase. All we need to do now is to start with an empty subarray, keep adding elements to it until the sum of elements in the subarray is greater than the desired sum, k.
Once the sum has increased k, there is no possibility that adding more elements to it will give the desired sum. In that case, we need to remove some elements from the starting of the array. The approach is in fact a slight variation of the sliding-window technique.
The sliding window technique is used in cases where we are to deal with a contiguous set of elements stored in memory. The intuition is to start from the 1st element, take a window size of say, ‘s’ units, Repeatedly slide the window back and forth depending on the problem we have in hand.
In contrast with a sliding window, in the subarray with a given sum problem, start with an empty array and repeatedly add elements to it. If the subarray sum is greater than the desired sum, start removing elements from the starting of the subarray.
Consider an example array of 5 elements and the problem is to find a subarray with a given sum equals k.
Algorithm
- Initialize Variables:
- start as the starting index of the current subarray (initially 0).
- current_sum to keep track of the sum of the current subarray (initially 0).
- Iterate Through the Array:
- For each element in the array, add it to current_sum.
- Adjust the Window:
- While current_sum is greater than k, subtract the element at the start index from current_sum and increment start.
- This step ensures that the subarray size is adjusted to potentially match the target sum k.
- Check for Target Sum:
- If current_sum equals k, return the current subarray indices [start, end].
- Return Result:
- If no subarray with the given sum is found, return -1.
Example
Consider an array of 5 elements and we need to find a subarray with sum equal to 17.
arr[] = {3, 6, 9, 12, 15}
k = 17
The variable curr_sum will store the sum of elements from the starting of the window (Ws) to the ending of the window(Wend). Initially, Ws and Wend are both at the starting position of the array, the position of Ws and Wend will change as shown below:
Now if we increment the position of Ws, it will be greater than Wend. This will not satisfy the condition Ws < Wend. Hence the program should stop execution at this point.
The above approach should execute till Ws < Wend and should stop after that. Two nested loops are changed to a single loop using this approach, making the overall complexity from O(N^2) to O(N).
Implementation
If there are multiple subarrays with a sum equal to given sum, the above code will list out the indices of the first such subarray. In case of no subarray with given sum, a message will be displayed to the user.
- C
- C++
- Java
- Python
- Javascript
- C#
C
#include <stdio.h>
int slidingWindow(int arr[], int n, int k) {
int curr_sum = arr[0], start_window = 0;
for (int i = 1; i <= n; i++) {
while (curr_sum > k && start_window < i - 1) {
curr_sum -= arr[start_window];
start_window++;
}
if (curr_sum == k) {
printf("Sum found between indexes %d and %d\n", start_window, i - 1);
return 1;
}
if (i < n) {
curr_sum += arr[i];
}
}
printf("No subarray with given sum equals to %d is found in the array\n", k);
return 0;
}
int main() {
int arr1[] = {10, 20, -45, 45, 60};
int k1 = 80;
slidingWindow(arr1, 5, k1);
int arr2[] = {1, 2, 4, 15, 10};
int k2 = 30;
slidingWindow(arr2, 5, k2);
return 0;
}
You can also try this code with Online C Compiler
C++
#include <iostream>
using namespace std;
int slidingWindow(int arr[], int n, int k) {
int curr_sum = arr[0], start_window = 0;
for (int i = 1; i <= n; i++) {
while (curr_sum > k && start_window < i - 1) {
curr_sum -= arr[start_window];
start_window++;
}
if (curr_sum == k) {
cout << "Sum found between indexes " << start_window << " and " << i - 1 << endl;
return 1;
}
if (i < n) {
curr_sum += arr[i];
}
}
cout << "No subarray with given sum equals to " << k << " is found in the array" << endl;
return 0;
}
int main() {
int arr1[] = {10, 20, -45, 45, 60};
int k1 = 80;
slidingWindow(arr1, 5, k1);
int arr2[] = {1, 2, 4, 15, 10};
int k2 = 30;
slidingWindow(arr2, 5, k2);
return 0;
}
You can also try this code with Online C++ Compiler
Java
public class Subarray {
static int slidingWindow(int arr[], int k) {
int curr_sum = arr[0], start_window = 0, i;
int n = arr.length;
// Pick a starting point
for (i = 1; i <= n; i++) {
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum > k && start_window < i - 1) {
curr_sum = curr_sum - arr[start_window];
start_window++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum == k) {
int end_window = i - 1;
System.out.println("Sum found between indexes " + start_window + " and " + end_window);
return 1;
}
// Add this element to curr_sum
if (i < n)
curr_sum = curr_sum + arr[i];
}
System.out.println("No subarray with given sum equals to " + k + " is found in the array");
return 0;
}
public static void main(String[] args) {
int[] arr1 = { 10, 20, -45, 45, 60 };
int k1 = 80;
slidingWindow(arr1, k1);
int[] arr2 = { 1, 2, 4, 15, 10 };
int k2 = 30;
slidingWindow(arr2, k2);
} // main method ends here
} // class ends here
You can also try this code with Online Java Compiler
Python
def sliding_window(arr, k):
curr_sum = arr[0]
start_window = 0
for i in range(1, len(arr) + 1):
while curr_sum > k and start_window < i - 1:
curr_sum -= arr[start_window]
start_window += 1
if curr_sum == k:
end_window = i - 1
print(f"Sum found between indexes {start_window} and {end_window}")
return 1
if i < len(arr):
curr_sum += arr[i]
print(f"No subarray with given sum equals to {k} is found in the array")
return 0
arr1 = [10, 20, -45, 45, 60]
k1 = 80
sliding_window(arr1, k1)
arr2 = [1, 2, 4, 15, 10]
k2 = 30
sliding_window(arr2, k2)
You can also try this code with Online Python Compiler
Javascript
function slidingWindow(arr, k) {
let curr_sum = arr[0];
let start_window = 0;
for (let i = 1; i <= arr.length; i++) {
while (curr_sum > k && start_window < i - 1) {
curr_sum -= arr[start_window];
start_window++;
}
if (curr_sum === k) {
console.log(`Sum found between indexes ${start_window} and ${i - 1}`);
return 1;
}
if (i < arr.length) {
curr_sum += arr[i];
}
}
console.log(`No subarray with given sum equals to ${k} is found in the array`);
return 0;
}
let arr1 = [10, 20, -45, 45, 60];
let k1 = 80;
slidingWindow(arr1, k1);
let arr2 = [1, 2, 4, 15, 10];
let k2 = 30;
slidingWindow(arr2, k2);
You can also try this code with Online Javascript Compiler
C#
using System;
public class Subarray
{
public static int SlidingWindow(int[] arr, int k)
{
int curr_sum = arr[0], start_window = 0;
for (int i = 1; i <= arr.Length; i++)
{
while (curr_sum > k && start_window < i - 1)
{
curr_sum -= arr[start_window];
start_window++;
}
if (curr_sum == k)
{
int end_window = i - 1;
Console.WriteLine($"Sum found between indexes {start_window} and {end_window}");
return 1;
}
if (i < arr.Length)
{
curr_sum += arr[i];
}
}
Console.WriteLine($"No subarray with given sum equals to {k} is found in the array");
return 0;
}
public static void Main(string[] args)
{
int[] arr1 = { 10, 20, -45, 45, 60 };
int k1 = 80;
SlidingWindow(arr1, k1);
int[] arr2 = { 1, 2, 4, 15, 10 };
int k2 = 30;
SlidingWindow(arr2, k2);
}
}
Complexity Analysis
Time Complexity: O(N) because of a single loop
Space Complexity: O(1) as constant extra space is required
Approach 3: Prefix Sum Technique
For an array with negative integers, A variation of the Prefix Sum technique can be used. The idea to approach the problem is if the prefix sum up to ith index is X, and the prefix sum up to jth index is Y and it is found that Y = X +k, then the required subarray is found with i as start index and j as end index.
Suppose the required subarray sum (k) is 110, the prefix sum up to index 5 (Y) is 174, and the prefix sum up to index 3 (X) is 64
At this particular position, the desired sum is actually Y – X, which implies that the required subarray is found between indices 4 and 5.
To store the index value and the sum of elements up to that index a hashmap can be used.
- Store the sum of elements of every prefix of the array in a hashmap i.e, every index stores the sum of elements up to that index hashmap. In other words, key stores the prefix sum, and the value stores the index. A variable to store the current sum is ‘sum‘ and the sum of the subarray as ‘k’
- So to check if there is a subarray with given sum equal to k, check for every index i, and sum up to that index as x. If there is a prefix with a sum equal to x – k, then the subarray with the given sum is found.
Example
Consider for example an array of 5 integers and the desired subarray sum to be -14.
arr[] = {10, 30, -44, 8, 23}
k = -4
At this step, the sum == k, hence the desired subarray is found with the ending index as the value of the last key, value pair stored in hashmap. In the example above, the index is 2.
Hence the required subarray is {10, 30, -44}.
Steps
- Declare a Hashmap where the key of hashmap will store the index value and the value will store the sum of elements up to that index.
- Keep two variables, one to store the current sum and one to store the subarray sum.
- Iterate through the array from start to end, at each iteration, update the sum variable as sum = sum + arr[i]
- If the subarray with given sum or a subarray with sum equal to k is found, then print that subarray from 0 to i
- If there is any key in the hashmap that equals sum – k, then print the subarray from hashmap[sum – k] to i.
- Print the sum and index in the hashmap as a key-value pair.
Implementation
- C
- C++
- Java
- Python
- Javascript
- C#
C
#include <stdio.h>
#include <stdlib.h>
typedef struct HashMap {
int key;
int value;
struct HashMap* next;
} HashMap;
HashMap* createNode(int key, int value) {
HashMap* newNode = (HashMap*)malloc(sizeof(HashMap));
newNode->key = key;
newNode->value = value;
newNode->next = NULL;
return newNode;
}
void put(HashMap** map, int key, int value) {
int hash = key % 1000;
if (map[hash] == NULL) {
map[hash] = createNode(key, value);
} else {
HashMap* temp = map[hash];
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = createNode(key, value);
}
}
int get(HashMap** map, int key) {
int hash = key % 1000;
HashMap* temp = map[hash];
while (temp != NULL) {
if (temp->key == key) {
return temp->value;
}
temp = temp->next;
}
return -1;
}
int containsKey(HashMap** map, int key) {
int hash = key % 1000;
HashMap* temp = map[hash];
while (temp != NULL) {
if (temp->key == key) {
return 1;
}
temp = temp->next;
}
return 0;
}
void subArraySum(int* arr, int n, int k) {
int cur_sum = 0;
int start_point = 0;
int end_point = -1;
HashMap* hm[1000] = {NULL};
for (int i = 0; i < n; i++) {
cur_sum += arr[i];
if (cur_sum == k) {
start_point = 0;
end_point = i;
break;
}
if (containsKey(hm, cur_sum - k)) {
start_point = get(hm, cur_sum - k) + 1;
end_point = i;
break;
}
put(hm, cur_sum, i);
}
if (end_point == -1) {
printf("No subarray with a sum equals to %d in the input array\n", k);
} else {
printf("The elements from position %d to %d form the required subarray\n", start_point, end_point);
}
}
int main() {
int arr1[] = {10, 20, -45, 45, 60};
int k1 = 80;
subArraySum(arr1, 5, k1);
int arr2[] = {1, 2, 4, 15, 10};
int k2 = 30;
subArraySum(arr2, 5, k2);
return 0;
}
You can also try this code with Online C Compiler
C++
#include <iostream>
#include <unordered_map>
using namespace std;
void subArraySum(int arr[], int n, int k) {
unordered_map<int, int> hm;
int cur_sum = 0;
int start_point = 0;
int end_point = -1;
for (int i = 0; i < n; i++) {
cur_sum += arr[i];
if (cur_sum == k) {
start_point = 0;
end_point = i;
break;
}
if (hm.find(cur_sum - k) != hm.end()) {
start_point = hm[cur_sum - k] + 1;
end_point = i;
break;
}
hm[cur_sum] = i;
}
if (end_point == -1) {
cout << "No subarray with a sum equals to " << k << " in the input array" << endl;
} else {
cout << "The elements from position " << start_point << " to " << end_point << " form the required subarray" << endl;
}
}
int main() {
int arr1[] = {10, 20, -45, 45, 60};
int k1 = 80;
subArraySum(arr1, 5, k1);
int arr2[] = {1, 2, 4, 15, 10};
int k2 = 30;
subArraySum(arr2, 5, k2);
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.HashMap;
public class Subarray
{
public static void subArraySum(int[] arr, int k)
{
int n = arr.length;
//cur_sum to keep track of cummulative sum till that point
int cur_sum = 0;
int start_point = 0; // to keep track of starting point of subarray
int end_point = -1; // to keep track of ending point
// creating a hash map whose key will be equal to the index
// and value will be equal to the sum till that index
HashMap<Integer, Integer> hm = new HashMap<>();
// Iterating the array from starting to ending position
for (int i = 0; i < n; i++)
{
/*
There are three possibilties for an element now :-
CASE 1) If the element is not present in Hashmap, simply add it.
CASE 2) If adding the current element gives the desired sub array (i.e. subarrat found between 0th and the
current position
CASE 3) If the hashmap already contains that value, means we already have the subarray, simply STOP at this point
*/
cur_sum = cur_sum + arr[i];
hm.put(cur_sum, i); // CASE 1,we are adding curr_sum as value and i as index in the hashmap
if (cur_sum - k == 0) // CASE 2
{
start_point = 0;
end_point = i;
break;
}
if (hm.containsKey(cur_sum - k)) // CASE 3
{
start_point = hm.get(cur_sum - k) + 1;
end_point = i;
break;
}
}
// if end is -1 : means we have reached end without the sum
if (end_point == -1)
{
System.out.println("No subarray with a sum equals to k in the input array");
}
else
{
System.out.println("The elements from position " + start_point + " to " + end_point + "form the required sub array");
}
}
public static void main(String[] args)
{
int[] arr1 = {10, 20, -45, 45, 60};
int k1 = 80;
subArraySum(arr1, k1);
int[] arr2 = {1, 2, 4, 15, 10};
int k2 = 30;
subArraySum(arr2, k2);
} // main method ends here
} // class ends here
You can also try this code with Online Java Compiler
Python
def sub_array_sum(arr, k):
cur_sum = 0
start_point = 0
end_point = -1
hm = {}
for i in range(len(arr)):
cur_sum += arr[i]
if cur_sum == k:
start_point = 0
end_point = i
break
if cur_sum - k in hm:
start_point = hm[cur_sum - k] + 1
end_point = i
break
hm[cur_sum] = i
if end_point == -1:
print(f"No subarray with a sum equals to {k} in the input array")
else:
print(f"The elements from position {start_point} to {end_point} form the required subarray")
arr1 = [10, 20, -45, 45, 60]
k1 = 80
sub_array_sum(arr1, k1)
arr2 = [1, 2, 4, 15, 10]
k2 = 30
sub_array_sum(arr2, k2)
You can also try this code with Online Python Compiler
Javascript
function subArraySum(arr, k) {
let cur_sum = 0;
let start_point = 0;
let end_point = -1;
let hm = new Map();
for (let i = 0; i < arr.length; i++) {
cur_sum += arr[i];
if (cur_sum == k) {
start_point = 0;
end_point = i;
break;
}
if (hm.has(cur_sum - k)) {
start_point = hm.get(cur_sum - k) + 1;
end_point = i;
break;
}
hm.set(cur_sum, i);
}
if (end_point == -1) {
console.log(`No subarray with a sum equals to ${k} in the input array`);
} else {
console.log(`The elements from position ${start_point} to ${end_point} form the required subarray`);
}
}
let arr1 = [10, 20, -45, 45, 60];
let k1 = 80;
subArraySum(arr1, k1);
let arr2 = [1, 2, 4, 15, 10];
let k2 = 30;
subArraySum(arr2, k2);
You can also try this code with Online Javascript Compiler
C#
using System;
using System.Collections.Generic;
public class Subarray
{
public static void SubArraySum(int[] arr, int k)
{
int cur_sum = 0;
int start_point = 0;
int end_point = -1;
Dictionary<int, int> hm = new Dictionary<int, int>();
for (int i = 0; i < arr.Length; i++)
{
cur_sum += arr[i];
if (cur_sum == k)
{
start_point = 0;
end_point = i;
break;
}
if (hm.ContainsKey(cur_sum - k))
{
start_point = hm[cur_sum - k] + 1;
end_point = i;
break;
}
if (!hm.ContainsKey(cur_sum))
{
hm[cur_sum] = i;
}
}
if (end_point == -1)
{
Console.WriteLine("No subarray with a sum equals to " + k + " in the input array");
}
else
{
Console.WriteLine("The elements from position " + start_point + " to " + end_point + " form the required subarray");
}
}
public static void Main(string[] args)
{
int[] arr1 = { 10, 20, -45, 45, 60 };
int k1 = 80;
SubArraySum(arr1, k1);
int[] arr2 = { 1, 2, 4, 15, 10 };
int k2 = 30;
SubArraySum(arr2, k2);
}
}
Complexity Analysis
The time complexity of the above program is O(N) as we need to iterate through the array of size N once
The space complexity is O(N) because a hashmap of size N is needed.
Check out this problem - Pair Sum In Array.
Variations of the Programme
The program can be modified in various ways. Some of the variations are :
- Fixing the subarray size to ‘a’ units: In this case, instead of trying all the possible subarrays from index ‘i’, check for arrays of size ‘a’.
- Find a subarray whose sum of elements is equal to zero: In this case, Iterate through the array, and for every element, arr[i], calculate the sum of elements from 0 to i. If the current sum was seen before, then there is a zero-sum array.
- Finding Maximum and Minimum subarray sum from an array: A slight variation of the problem can be practiced on Code360.
Frequently Asked Questions
How do you find the number of Subarray given the sum?
We can either generate all the subarrays or Use the techniques discussed above, depending on the type of elements that are stored in the array.
Positive Elements – Variation of Sliding Window Technique.
Negative Elements – Prefix Sum technique.
How do you find all the subarrays in an array?
Use two nested loops, one for the starting position and the other for the ending position of the subarray. Print the elements between the starting and ending positions.
How do you find if there is a Subarray with a sum equal to zero?
One important property of Hash Map is that it does not store duplicate elements. So, Hashing can be used in a similar manner as you do for an array with negative elements. Iterate through the array and for every element arr[i], calculate the sum of elements from 0 to i. If the current sum was seen before, then there is a zero-sum array. This approach will have a time complexity of O(N)
How do you find a contiguous subarray whose sum is equal to a given number?
To find a contiguous subarray whose sum is equal to a given number, you can use the sliding window technique. Start with an empty subarray, add elements until the sum exceeds the target, then remove elements from the start until the sum equals the target.
Conclusion
There are different techniques used to find the subarray with a given sum in an array. The brute force method was to first generate all the subarrays and then check for each subarray sum, the time complexity was O(N^2).
In an array with all positive elements, a variation of the sliding window technique can be used making the overall time complexity O(N). In an array with all negative elements, the concept of prefix-sum can be used.
The array is an important topic from an interview perspective. In almost all companies, questions related to arrays are being asked in the technical rounds. Therefore, it’s very important to have a solid grasp of Arrays.
Recommended problems -
568+ registered 
