What Is Subarray With Given Sum?

Introduction

A frequently asked question by Amazon, Paytm, and many other Product based companies is Subarray with given sum, “Given an unsorted array of integers, and an integer k. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray equals to k or not”.

There are many possibilities in this problem, maybe there is more than one subarray with the given sum (return the indices of the first possible subarray), or maybe there is no subarray with the given sum.

Go ahead and try out this question on your own at CodeStudio before moving on to the solution.

What are sub-arrays?

An array is a collection of homogeneous elements stored at contiguous locations in the memory. A subarray of an array is part/slice of an array where elements are stored at adjacent positions.

Consider, for example, an array with five elements as shown below:

sample_arr[] = {3, 8, 13, 9, 5 }

Some of the possible subarrays are {3, 8, 9} ,{8, 13} etc.
In general, for an array with n elements, total ( n * ( n + 1 )) / 2 subarrays are possible.

Approach 1 – Brute Force

Explanation:

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
- If sum_subarray == 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.

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

Programme

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.

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);
 
    }
}

Complexity Analysis:

Time complexity: O(N²), 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- Sliding Window

Explanation:

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.

Image Source: StackOverflow

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.

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 W_s < W_end 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).

Steps

Create three variables, curr_sum = arr[0], start_window and i
Traverse the array from start to end.
Update the variable curr_sum by adding current element, curr_sum = curr_sum + array[i]
If the curr_sum is greater than the given sum k, update the variable curr_sum as curr_sum = curr_sum – array[start_window], and update start_window as, start_window++.
If the curr_sum is equal to the given sum k, print the subarray and break the loop.

Programme:

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.

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

Complexity Analysis

Time Complexity: O(N) because of a single loop
Space Complexity: O(1) as constant extra space is required

Disadvantages of Sliding Window Technique

The above approach works fine with an array of all positive integers but in cases where the array may consist of negative integers, the variation of the sliding window technique used above is not valid.

Because there is no guarantee that adding more elements to the curr_sum will lead to the desired sum or not, as the elements may be positive or negative.

Approach 3- Prefix Sum Technique

Explanation:

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.

Programme:

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

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.

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 CodeStudio.

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 calculate Subarray size k?

The idea is to use a variation of the sliding window technique simultaneously where the size of the window is fixed to k. Firstly check for subarray starting from 0th index to kth index, if this is the required subarray simply print the starting index and ending index. Maintain two pointers, start and end, pointing to the first and last element of the current window.

The sum of the first window is computed, and then both start and end are incremented by one position. Now the sum of this window can be computed by just adding the new element and removing the outgoing element (previously start) from the previous window’s sum.

How do you find the minimum sum of the Subarray?

Use Kadane’s algorithm with a slight variation as follows. Initialize two variables max_ending_here for the minimum sum value of sum that ends at this point and max_so_far for the minimum sum so far with the maximum value of integers INT_MAX.

for i = 0 to n-1
if max_ending_here > 0
max_ending_here = arr[i]
else
max_ending_here += arr[i]
max_so_far = min(max_so_far, max_ending_here)
return max_so_far

Key Takeaways

In the blog, we discussed a very important interview question. 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.

Once you have read the article, make sure to try this question and other related questions on your own. CodeStudio has a variety of important questions that are asked in companies. Ending this post on a positive note, “Practice creates confidence. Confidence Empowers you”.

Happy Coding!

By Manvi Chaddha