Longest Subarray with given Sum K

Problem Statement: Given an array and a sum k, we need to print the length of the longest subarray that sums to k.

Examples:

Example 1:
Input:
arr = {7,1,6,0}, k = 7

Output: Length of the longest subarray with sum K is 3
Explanation:
 1 + 6 + 0 = 7, it is the longest subarray with sum 7 and length 3.

Example 2:
Input: 
arr = {2,3,5,1,9}, k = 10
Output: Length of the longest subarray with sum K is 3
Explanation: 2 + 3 + 5 = 10, it is the longest subarray with sum 10 and length 3

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 sub-arrays, check the sum, and update the max length we found so far.

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, now we check whether the length of the current subarray is greater than the value we found so far.
Else, we move on to the next possible one..

Code:

C++ Code

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int longestSubArrWithSumK_BF(int arr[], int n, int k) {
  int maxLength = 0;
  for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
      sum += arr[j];
      if (sum == k)
        maxLength = max(maxLength, (j - i + 1));
    }

  }
  return maxLength;
}

int main() {

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

  cout << "Length of the longest subarray with sum K is " << 
  longestSubArrWithSumK_BF(arr, n, k);

  return 0;
}

Output: Length of the longest subarray with sum K is 3

Time Complexity: O(n^2) time to generate all possible subarrays.

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 = {7,1,6,0};
    int n = arr.length, k = 7;

    System.out.println("Length of the longest subarray with sum K is " + 
    longestSubArrWithSumK_BF(arr, n, k));
  }

  public static int longestSubArrWithSumK_BF(int[] arr, int n, int k) {
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
        sum += arr[j];
        if (sum == k)
          maxLength = Math.max(maxLength, (j - i + 1));
      }

    }
    return maxLength;
  }

}

Output: Length of the longest subarray with sum K is 3

Time Complexity: O(n^2) time to generate all possible subarrays.

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

Solution 2:

Intuition 2:

A simple intuition for the optimal approach is that, while forming a subarray if the sum as already greater than k, we can stop there and increase the 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 the ends slide towards right all the time.
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 index and increase the ending index 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. We check whether we have got the sum, if so, now we compare with the max length we found so far, and replace it with the greatest.
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 hereafter).
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<bits/stdc++.h>

using namespace std;

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

    if (sum == k)
      maxLength = max(maxLength, (end - start + 1));

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

int main() {

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

  cout << "Length of the longest subarray with sum K is " << 
  longestSubArrWithSumK_Optimal(arr, n, k);

  return 0;
}

output: Length of the longest subarray with sum K is 3

Time Complexity: O(2n) ~ O(n), 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.

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 = {7,1,6,0};
    int n = arr.length, k = 7;

    System.out.println("Length of the longest subarray with sum K is " + 
    longestSubArrWithSumK_Optimal(arr, n, k));
  }

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

      if (sum == k)
        maxLength = Math.max(maxLength, (end - start + 1));

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

}

output: Length of the longest subarray with sum K is 3

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