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
– user1071840, Commented Feb 19, 2013 at 1: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
– user1071840, Commented Feb 19, 2013 at 1:31
@jogojapan. Yep, I'm sure it would have a dupe..but wasn't able to find one so posted. — user1071840
– user1071840, Commented Feb 19, 2013 at 1: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
– jogojapan, Commented Feb 19, 2013 at 1:56
Related, but not a duplicate: stackoverflow.com/questions/13093602/… — jogojapan
– jogojapan, Commented Feb 19, 2013 at 1:57

Evgeny Kluev · Accepted Answer · 2013-02-19 09:02:11Z

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, 2013 at 9:02

Evgeny Kluev

24.7k7 gold badges58 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

17 Comments

Evgeny Kluev Over a year ago

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.

Nirdesh Sharma Over a year ago

This is really a great soluation.It finds all the possible continous sub-arry of sum K.

L.E. Over a year ago

I dont understand this algorithm. does anybody have running code for this?

temporary_user_name Over a year ago

what is start list 2??? It is redeclared in each loop but not actually used...I am extremely confused by this.

temporary_user_name Over a year ago

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.

|

Menezes Sousa · Accepted Answer · 2015-11-02 07:23:52Z

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

Sameer Shrestha · Accepted Answer · 2018-05-16 23:34:56Z

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

Saurin · Accepted Answer · 2016-04-07 21:47:14Z

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

Kenster · Accepted Answer · 2017-05-26 14:15:18Z

0

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, ]

edited May 26, 2017 at 14:15

Kenster

25.8k23 gold badges87 silver badges115 bronze badges

answered May 6, 2014 at 6:30

Manmohan Soni

6,7112 gold badges25 silver badges30 bronze badges

1 Comment

Anubhaw Arya Over a year ago

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

N_Divyasri · Accepted Answer · 2017-11-15 10:28:08Z

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

Nagappa L M · Accepted Answer · 2022-11-23 06:28:23Z

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

Aman Goel · Accepted Answer · 2017-04-18 08:46:24Z

-2

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

answered Apr 18, 2017 at 8:46

Aman Goel

3,5511 gold badge24 silver badges17 bronze badges

1 Comment

CuriousCoder Over a year ago

OP wants the subarray whose sum is K. He doesn't want the sub array with maximum sum

Collectives™ on Stack Overflow

Given an input array find all subarrays with given sum K

8 Answers 8

17 Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

17 Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

1 Comment

Linked

Related