Given an input array find all subarrays with given sum K

Question

Given an input array we can find a single sub-array which sums to K (given) in linear time, by keeping track of sum found so far and the start position. If the current sum becomes greater than the K we keep removing elements from start position until we get current sum <= K.

I found sample code from geeksforgeeks and updated it to return all such possible sets. But the assumption is that the input array consists of only +ve numbers.

bool subArraySum(int arr[], int n, int sum)
{
    int curr_sum = 0, start = 0, i;
    bool found = false;

    for (i = 0; i <= n; i++)
    {
        while (curr_sum > sum && start < i)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        if (curr_sum == sum)
        {
            cout<<"Sum found in b/w indices: "<<start<<" & "<<(i-1)<<"\n";
            curr_sum -= arr[start];
            start++;
            found = true;
        }

        // Add this element to curr_sum
        if (i < n) {
          curr_sum = curr_sum + arr[i];
        }
    }

    return found;
}

My question is do we have such a solution for mixed set of numbers too (both positive and negative numbers)?

@jogojapan, Removed the C++ tag. But, the question you pointed is different, that requires subarray OF AT LEAST 'k' consecutive elements with maximum sum. I'm asking for any length subarray with given sum. — user1071840, Feb 19 '13 at 01:27
@jogojapan. For maximum sum, we've kadane's algorithm which takes care of both positive and negative input and can be updated to consist of exactly 'k' elements. — user1071840, Feb 19 '13 at 01:31
@jogojapan. Yep, I'm sure it would have a dupe..but wasn't able to find one so posted. — user1071840, Feb 19 '13 at 01:54
@user1071840 Sure. Just to let you know, I'll remove my comments above, so as to not cause anyone to hit the "close vote" button prematurely. — jogojapan, Feb 19 '13 at 01:56
Related, but not a duplicate: http://stackoverflow.com/questions/13093602/finding-subarray-with-maximum-sum-number-of-elements — jogojapan, Feb 19 '13 at 01:57

score 25 · Answer 1 · answered Feb 19 '13 at 09:02

25

There is no linear-time algorithm for the case of both positive and negative numbers.

Since you need all sub-arrays which sum to K, time complexity of any algorithm cannot be better than size of the resulting set of sub-arrays. And this size may be quadratic. For example, any sub-array of [K, -K, K, -K, K, -K, ...], starting and ending at positive 'K' has the required sum, and there are N²/8 such sub-arrays.

Still it is possible to get the result in O(N) expected time if O(N) additional space is available.

Compute prefix sum for each element of the array and insert the pair (prefix_sum, index) to a hash map, where prefix_sum is the key and index is the value associated with this key. Search prefix_sum - K in this hash map to get one or several array indexes where the resulting sub-arrays start:

hash_map[0] = [-1]
prefix_sum = 0
for index in range(0 .. N-1):
  prefix_sum += array[index]
  start_list = hash_map[prefix_sum - K]
  for each start_index in start_list:
    print start_index+1, index
  start_list2 = hash_map[prefix_sum]
  start_list2.append(index)

answered Feb 19 '13 at 09:02

Evgeny Kluev

24,287
7
55
98

is this a typo: `Still it is possible to get the result in O(N)`? You just proved such complexity can not be achieved. – Ivaylo Strandjev Feb 19 '13 at 09:17
1

This is not a typo. I've proved that O(N) worst case time is not possible. But here I'm explaining O(N) expected time algorithm. – Evgeny Kluev Feb 19 '13 at 09:19
1

This is really a great soluation.It finds all the possible continous sub-arry of sum K. – Nirdesh Sharma May 16 '13 at 06:20
6

I dont understand this algorithm. does anybody have running code for this? – L.E. Jul 20 '13 at 03:17
@EvgenyKluev Nice Approach. Can you tell all subarray pairs which are divisible by K. ??? – devsda Oct 23 '13 at 11:23
@devsda: It's not clear what do you mean by "subarray pairs". If you need to find all contiguous sub-arrays having sum divisible by K, then yes, this algorithm could be modified to do this. Just perform all operations related to `prefix_sum` modulo K: `prefix_sum = (prefix_sum + array[index]) % K; start_list = hash_map[prefix_sum]`. – Evgeny Kluev Oct 23 '13 at 12:09
@EvgenyKluev What will be the time complexity ? – devsda Oct 23 '13 at 12:11
@devsda: Expected complexity would be O(N + N^2 / K). – Evgeny Kluev Oct 23 '13 at 12:11
http://stackoverflow.com/questions/19541223/find-numbers-of-subarray-of-an-array-whose-sum-is-divided-by-given-number – devsda Oct 23 '13 at 12:12
@devsda: It looks like you don't need sub-arrays themselves. Since you need to know only how many of sub-arrays have sum divisible by K, you could simplify this algorithm by ignoring all list operations and using counters instead of lists. Which makes worst-case time complexity only O(N). – Evgeny Kluev Oct 23 '13 at 12:26
3

what is start list 2??? It is redeclared in each loop but not actually used...I am extremely confused by this. – temporary_user_name Jan 16 '14 at 23:54
1

I really do not follow this algorithm at all. I understand the "construct a prefix table" part, but that's where my understanding ends. That table only tells you the sums of arrays starting from element index `0`, so what good is it? I tried to make sense of the pseudocode and couldn't. – temporary_user_name Jan 17 '14 at 00:56
@Aerovistae: prefix sum at one position in the array subtracted from prefix sum at other position gives exactly sum of all elements between these positions. And hash table allows to perform this precess in-reverse: given sum and one prefix, find the position where other prefix has necessary value. You could use [this Python implementation](http://ideone.com/F7JfJV) (or implement it yourself in your preferred language) to print all intermediate results and find out how this algorithm works. – Evgeny Kluev Jan 17 '14 at 10:09
I also don't understand the algorithm. Could you please provide a running code in C or Java? – Hengameh Jul 07 '15 at 13:47
1

@Hengameh: I'm afraid I could not do it. I don't write in Java. And C is too low-level for this task. – Evgeny Kluev Jul 07 '15 at 14:38
I have rewritten the logic in Java for all those finding it difficult to understand it from here. Nice logic @Evgeny! – Menezes Sousa Nov 02 '15 at 07:24
still having trouble processing this visually or even by reading the code and output. it feels like it ignores the shorter subarrays and my mind can't compute :( – dtc Apr 13 '17 at 18:26

score 7 · Answer 2 · answered Nov 02 '15 at 07:23

Solution as given by @Evgeny Kluev coded in Java with a little explanation.

public static void main(String[] args) {
    int[] INPUT = {5, 6, 1, -2, -4, 3, 1, 5};
    printSubarrays(INPUT, 5);
}

private static void printSubarrays(int[] input, int k) {
    Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    List<Integer> initial = new ArrayList<Integer>();
    initial.add(-1);
    map.put(0, initial);
    int preSum = 0;

    // Loop across all elements of the array
    for(int i=0; i< input.length; i++) {
        preSum += input[i];
        // If point where sum = (preSum - k) is present, it means that between that 
        // point and this, the sum has to equal k
        if(map.containsKey(preSum - k)) {   // Subarray found 
            List<Integer> startIndices = map.get(preSum - k);
            for(int start : startIndices) {
                System.out.println("Start: "+ (start+1)+ "\tEnd: "+ i);
            }
        }

        List<Integer> newStart = new ArrayList<Integer>();
        if(map.containsKey(preSum)) { 
            newStart = map.get(preSum);
        }
        newStart.add(i);
        map.put(preSum, newStart);
    }
}

score 1 · Answer 3 · answered May 16 '18 at 23:34

Quadratic Time: O(n2) in worst case.

private static void findSubArray(int[] is, int N) {
    System.out.println("Continuous sub array of " + Arrays.toString(is) + " whose sum is " + N + " is ");
    List<Integer> arry = new ArrayList<>(is.length);
    for (int i = 0; i < is.length; i++) {
        int tempI = is[i];
        arry.add(tempI);
        for (int j = i + 1; j < is.length; j++) {
            if (tempI + is[j] == N) {
                arry.add(is[j]);
                System.out.println(arry);

            } else if (tempI + is[j] < N) {
                arry.add(is[j]);
                tempI = tempI + is[j];
            } else {
                arry.clear();
                break;
            }
        }
    }

}
public static void main(String[] args) {
    findSubArray(new int[] { 42, 15, 12, 8, 6, 32 }, 26);

    findSubArray(new int[] { 12, 5, 31, 13, 21, 8 }, 49);

    findSubArray(new int[] { 15, 51, 7, 81, 5, 11, 25 }, 41);
}

score 0 · Answer 4 · edited May 26 '17 at 14:15

Try this code this can work for you:

private static void printSubArrayOfRequiredSum(int[] array, int requiredSum) {
        for (int i = 0; i < array.length; i++) {
            String str = "[ ";
            int sum = 0;
            for (int j = i; j < array.length; j++) {
                sum = sum + array[j];
                str = str + array[j] + ", ";
                if (sum == requiredSum) {
                    System.out.println(" sum : " + sum + " array : " + str
                            + "]");
                    str = "[ ";
                    sum = 0;
                }
            }
        }
    }

Use this method like :

 int array[] = { 3, 5, 6, 9, 14, 8, 2, 12, 7, 7 };
 printSubArrayOfRequiredSum(array, 14);

Output :

sum : 14 array : [ 3, 5, 6, ]
sum : 14 array : [ 14, ]
sum : 14 array : [ 2, 12, ]
sum : 14 array : [ 7, 7, ]

I know this is months late, but it's O(n^2) because you have two array iterations, both which got from 0-n. Therefore, you get n (from the outer loop) * n (from the inner loop), which equals n^2 — Anubhaw Arya, Feb 05 '15 at 03:37

score 0 · Answer 5 · answered Apr 07 '16 at 21:47

This problem is very similar to the combination problem solved here: http://introcs.cs.princeton.edu/java/23recursion/Combinations.java.html

Here is my solution:

public static void main(String[] args) {
    int [] input = {-10, 0, 5, 10, 15, 20, 30};
    int expectedSum = 20;

    combination(new SumObj(new int[0]), new SumObj(input), expectedSum);
}

private static void combination(SumObj prefixSumObj, SumObj remainingSumObj, int expectedSum){
    if(prefixSumObj.getSum() == expectedSum){
        System.out.println(Arrays.toString(prefixSumObj.getElements()));
    } 

    for(int i=0; i< remainingSumObj.getElements().length ; i++){
        // prepare new prefix
        int [] newPrefixSumInput = new int[prefixSumObj.getElements().length + 1];
        System.arraycopy(prefixSumObj.getElements(), 0, newPrefixSumInput, 0, prefixSumObj.getElements().length);
        newPrefixSumInput[prefixSumObj.getElements().length] = remainingSumObj.getElements()[i];
        SumObj newPrefixSumObj = new SumObj(newPrefixSumInput);

        // prepare new remaining
        int [] newRemainingSumInput = new int[remainingSumObj.getElements().length - i - 1];            
        System.arraycopy(remainingSumObj.getElements(), i+1, newRemainingSumInput, 0, remainingSumObj.getElements().length - i - 1);
        SumObj newRemainingSumObj = new SumObj(newRemainingSumInput);

        combination(newPrefixSumObj, newRemainingSumObj, expectedSum);
    }
}

private static class SumObj {
    private int[] elements;
    private int sum;

    public SumObj(int[] elements) {
        this.elements = elements;
        this.sum = computeSum();
    }

    public int[] getElements() {
        return elements;
    }

    public int getSum() {
        return sum;
    }

    private int computeSum(){
        int tempSum = 0;
        for(int i=0; i< elements.length; i++){
            tempSum += elements[i];
        }
        return tempSum;
    }
}

N_Divyasri · Answer 6 · 2017-11-15T10:28:08.210

Solution as given by @Evgeny Kluev coded in c++

#include<bits/stdc++.h>
using namespace std;
int c=0;
// Function to print subarray with sum as given sum
void subArraySum(int arr[], int n, int k)
{
   map<int,vector<int>>m1;
   m1[0].push_back(-1);
   int curr_sum=0;
   for(int i=0;i<n;i++){
       curr_sum=curr_sum+arr[i];
       if(m1.find(curr_sum-k)!=m1.end()){
           vector<int>a=m1[curr_sum-k];
           c+=m1[curr_sum-k].size();
           for(int j=0;j<a.size();j++){  // printing all indexes with sum=k
              cout<<a[j]+1<<" "<<i<<endl;
            }
        }
        m1[curr_sum].push_back(i);
    }  
 }
int main()
{
   int arr[] =  {10,2,0,10,0,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   int sum = 10;
   subArraySum(arr, n, sum);
   cout<<c<<endl; //count of subarrays with given sum
   return 0;
}

score 0 · Answer 7 · answered Nov 23 '22 at 06:28

class Solution
{
    //Function to find a continuous sub-array which adds up to a given number.
    static ArrayList<Integer> subarraySum(int[] arr, int n, int s) 
    {
        ArrayList<Integer> res=new ArrayList<>();
       
        
        int i=0,j=0,sum=0;
        sum=sum+arr[i];
        if(s==0){
            res.add(-1);
                    return res;
        }
        while(true)
        {
                if(sum<s)
                {
                    j=j+1;
                    if(j>=n || i>=n){
                     res.add(-1);
                    return res;
                     }
                    sum=sum+arr[j];
                }else if(sum>s){
                    sum=sum-arr[i];
                    i=i+1;
                    if(sum==s){
                       res.add(i+1);
                    res.add(j+1);
                    return res; 
                    }
                }else{
                    res.add(i+1);
                    res.add(j+1);
                    return res;
                }   
                if(j>=n || i>=n){
                     res.add(-1);
                    return res;
                }
                
        }
        
        
    }
  
}

Passing all 165 test cases from geeksforgeeks

score -2 · Answer 8 · answered Apr 18 '17 at 08:46

I also faced this problem in couple of interviews and came up with following best approach:

class MazSubArraySum {
public static void main(String[] args) {
    int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };
    System.out.println("Maximum contiguous sum is " + maxSubArraySum(a));

}

static int maxSubArraySum(int a[]) {
    int size = a.length;
    int currentindex = 0, end = 0, begin = 0;
    int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

    for (int i = 0; i < size; i++) {

        max_ending_here = max_ending_here + a[i];

        if (max_so_far < max_ending_here) {
            max_so_far = max_ending_here;
            begin = currentindex;
            end = i;

        }
        if (max_ending_here < 0) {
            max_ending_here = 0;
            currentindex++;

        }
    }

    System.out.println("begin and end: " + begin + "&" + end);
    return max_so_far;
}

}

Below is the output:

begin and end: 2&6
Maximum contiguous sum is 7

Above solution is the best solution in terms of time and space complexity that is O(n).

OP wants the subarray whose sum is K. He doesn't want the sub array with maximum sum — CuriousCoder, May 11 '18 at 18:33

Given an input array find all subarrays with given sum K

8 Answers8

Linked