CODEWITHSUNDEEP
javaarrays
brij
brij

Reputation: 341

How to find all subarrays with sum k in O(n) time complexity?

I can search for a subarrays with a sum k with the below code :

public static void subarraySum(int[] arr, int sum) {

    int start=0;
    int currSum=arr[0];

    for(int i = 1;i<=arr.length;i++) {
        while(currSum>sum ) {
            currSum-=arr[start];
            start++;
        }
        if(currSum==sum) {
            System.out.println(start + " " + (i-1) + " index");
            start=i;
            currSum=0;
        }
        if(i<arr.length) {
            currSum +=arr[i];
        }

    }

This will work for array like {15,2,4,8,9,5,10,23}. Output for this will be 2 subarrays {2,4,9,8} and {23}.

However, for arrays like {1,5,2,5,1,3}, this will only give me output as 1 subarray however there are 2 subarrays with sum 7 which are {5,2} and {2,5}. Any suggestions on how to tweek the above code to give the correct answer in the 2nd array ?

Upvotes: 2

Views: 1279

Answers (2)

Amer Qarabsa
Amer Qarabsa

Reputation: 6574

The algorithm is not complicated, I will explain the idea and leave the implementation to you to try it.

You need to have two indexes i, j. Make them both start with the first element. Now take the sub array between them (initially since they are both in the same place no sub array) and do the following test:

  • if the sum of it equals to your goal then add the current sub array

  • if the sum is less than your goal move j to the right to include one more element and do the test again

  • if the sum is greater than your goal move i to the right to remove the first element from the subarray and do the test again.

Finally, you will be having all the subarrays with sum equalling your goal.

please note that this solution only works for positive numbers

Upvotes: 4

Oleg Cherednik
Oleg Cherednik

Reputation: 18245

Yes, I am too slow. While I was solving this problem to give a code, we have a corrent algorytm answer. +1 for it from me and optionally my solution with code (I had this question in interview many ears ago):

public static List<int[]> subarraySum(int[] arr, int sum) {
    List<int[]> res = new ArrayList<>();
    int[] tmp;
    int start = 0;  // inclusive
    int end = 0;    // exclusive
    int currSum = 0;

    do {
        if (end == arr.length && currSum < sum)
            break;
        if (currSum > sum)
            currSum -= arr[start++];
        else if (currSum < sum)
            currSum += arr[end++];
        else if (currSum == sum) {
            res.add(tmp = new int[end - start]);
            System.arraycopy(arr, start, tmp, 0, tmp.length);
            currSum -= arr[start];
            start++;
        }
    } while (start <= arr.length && end <= arr.length);

    return res;
}

It looks correct, but I have tested this solution only in a couple of cases.

Upvotes: 0

Related Questions