Subarray with Given Sum

Problem Statement: Subarray with Given Sum

Given an array and a sum k, generate the subarray whose elements sum to k.

Examples:

Example 1:
Input:
 arr = {1, 7, 3, 9}, k = 10

Output: 7 3
Explanation:
 Of all the subarrays, 7 and 3 sums to 10.

Example 2:
Input: arr = {2,1,3,4,5,6}, k = 10
Output: 2 1 3 4
Explanation: Of all the subarrays, 2, 1, 3 and 4 sums to 10

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Intuition:

There is no special intuition needed for the brute force solution. We just need to generate all possible subarrays and check the sum.

Approach:

  • In order to generate all the subarrays, we need two nested loops. First loop decides the starting index of the subarray.
  • Second loop traverses from the starting index and generates all possible subarrays from that.
  • At each point we check whether we have reached the required sum.
  • If so, i and j are the starting and ending indexes of the subarray, we print using them.
  • Else, we move on to the next possible one.

Code:

C++ Code

#include<iostream>

using namespace std;

void subArrWithSumKBruteForce(int arr[], int n, int k) {
  for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
      sum += arr[j];
      if (sum == k) {
        for (int p = i; p <= j; p++)
          cout << arr[p] << " ";
        cout << endl;
      }
    }
  }
}

int main() {

  int arr[] = {1, 9, 3, 7};
  int n = sizeof(arr) / sizeof(arr[0]), k = 10;

  cout << "Subarray with given sum is: " << endl;
  subArrWithSumKBruteForce(arr, n, k);

  return 0;
}

Output:

Subarray with given sum is:
1 9
3 7

Time Complexity: O(n^2 + n), because we need to generate all possible subarrays. This contributes O(n^2) and printing the subarray takes O(n). As a result, O(n^2 + n) ~ O(n^2).

Space Complexity: O(1), we are not using any extra space.

Java Code

import java.util.*;

public class Solution {

  public static void main(String[] args) {
    int[] arr = {1, 9, 3, 7};
    int n = arr.length, k = 10;
    System.out.println("Subarray with given sum is: ");
    subArrWithSumKBruteForce(arr, n, k);
  }

  public static void subArrWithSumKBruteForce(int[] arr, int n, int k) {

    for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
        sum += arr[j];
        if (sum == k) {
          for (int p = i; p <= j; p++)
            System.out.print(arr[p] + " ");
          System.out.println();
        }
      }
    }
  }
}

Output:

Subarray with given sum is:
1 9
3 7

Time Complexity: O(n^2 + n), because we need to generate all possible subarrays. This contributes O(n^2) and printing the subarray takes O(n). As a result, O(n^2 + n) ~ O(n^2).

Space Complexity: O(1), we are not using any extra space.

Solution 2:

Intuition:

  • A simple intuition for the optimal approach is that, while forming a subarray if the sum is already greater than k, we can stop there and move on to the next starting index. 
  • Because already the sum has reached k, if we are still going to add more elements, it would definitely go up.

Approach:

  • This method is called a sliding window technique. We can think of a window covering the subarray, and just the ends slide towards right.
  • Here we have 2 nested loops. The outer loop slides the starting index of the window towards the right. The inner loop slides the ending index of the window towards the right.
  • Here is the working. First we fix the starting variable and increase the ending variable which increases the window size. We do this until we get the sum greater than k or we go out of bounds.
  • If we get a greater sum, we come out of the inner loop. Now, it’s time for us to shift the starting index, therefore we subtract the current starting element from the sum(meaning that we don’t include that number).
  • And we increase the start index which in turn decreases the window size. Now we can go on increasing the ending index as we did earlier.

Code:

C++ Code

#include<iostream>

using namespace std;

void subArrWithSumKOptimal(int arr[], int n, int k) {
  int start = 0, end = -1, sum = 0;
  while (start < n) {
    while ((end + 1 < n) && (sum + arr[end + 1] <= k))
      sum += arr[++end];

    if (sum == k) {
      for (int p = start; p <= end; p++)
        cout << arr[p] << " ";
      cout << "\n";
    }
    sum -= arr[start];
    start++;
  }

}
int main() {

  int arr[] = {1, 9, 3, 7};
  int n = sizeof(arr) / sizeof(arr[0]), k = 10;
  cout << "Subarray with given sum is: " << endl;
  subArrWithSumKOptimal(arr, n, k);

  return 0;
}

Output:

Subarray with given sum is:
1 9
3 7

Time Complexity: O(n^2), if we observe closely the window only forwards to the right always. And every element is visited at most 2 times, one by the end variable and by the start variable. So, it takes O(n) time to determine whether a subarray sum to k and O(n) time to print each such subarray.

Space Complexity: O(1), we are not using any extra space.

Java Code

import java.util.*;

public class Solution {

  public static void main(String[] args) {
    int[] arr = {1, 9, 3, 7};
    int n = arr.length, k = 10;
    System.out.println("Subarray with given sum is: ");
    subArrWithSumKOptimal(arr, n, k);
  }

  public static void subArrWithSumKOptimal(int[] arr, int n, int k) {
    int start = 0, end = -1, sum = 0;
    while (start < n) {
      while ((end + 1 < n) && (sum + arr[end + 1] <= k))
        sum += arr[++end];

      if (sum == k) {
        for (int p = start; p <= end; p++)
          System.out.print(arr[p] + " ");
        System.out.println();
      }

      sum -= arr[start];
      start++;
    }
  }

}

Output:

Subarray with given sum is:
1 9
3 7

Time Complexity: O(n^2), if we observe closely the window only forwards to the right always. And every element is visited at most 2 times, one by the end variable and by the start variable. So, it takes O(n) time to determine whether a subarray sum to k and O(n) time to print each such subarray.

Space Complexity: O(1), we are not using any extra space.

Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article