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 Format: N = 3, k = 5, array[] = {2,3,5}
Result: 2
Explanation: The longest subarray with sum 5 is {2, 3}. And its length is 2.
Example 2:
Input Format: N = 3, k = 1, array[] = {-1, 1, 1}
Result: 3
Explanation: The longest subarray with sum 1 is {-1, 1, 1}. And its length is 3.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Problem Link [Postives + Negatives].
Solution:
Naive Approach (Brute-force approach):
Here, in this approach, we are going to generate all possible subarrays to solve this problem.
How to generate all possible subarrays?
We will select all possible starting indices(say i) and all possible ending indices(say j) to generate all possible subarrays. The possible starting indices i.e. i can vary from index 0 to index n-1(i.e. The last index). For every index i, the possible ending index j can vary from i to n-1. So, the nested loops to generate all possible subarrays will be like the following:
Approach:
The steps are as follows:
- First, we will run a loop(say i) that will select every possible starting index of the subarray. The possible starting indices can vary from index 0 to index n-1(n = size of the array).
- Inside the loop, we will run another loop(say j) that will signify the ending index of the subarray. For every subarray starting from the index i, the possible ending index can vary from index i to n-1(n = size of the array).
- After that for each subarray starting from index i and ending at index j (i.e. arr[i….j]), we will run another loop to calculate the sum of all the elements(of that particular subarray).
- If the sum is equal to k, we will consider its length i.e. (j-i+1). Among all such subarrays, we will consider the maximum length by comparing all the lengths.
Intuition: We will check the sum of every possible subarray and consider the one with the sum k and the maximum length among them. To get every possible subarray sum, we will be using three nested loops. The first loops(say i and j) will iterate over every possible starting index and ending index of a subarray. Basically, in each iteration, the subarray range will be from index i to index j. Using another loop we will get the sum of the elements of the subarray [i…..j]. Among all the subarrays with sum k, we will consider the one with the maximum length.
Note: We are selecting every possible subarray using two nested loops and for each of them, we add all its elements using another loop.
Note: For a better understanding of intuition, please watch the video at the bottom of the page.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int getLongestSubarray(vector<int>& a, int k) {
int n = a.size(); // size of the array.
int len = 0;
for (int i = 0; i < n; i++) { // starting index
for (int j = i; j < n; j++) { // ending index
// add all the elements of
// subarray = a[i...j]:
int s = 0;
for (int K = i; K <= j; K++) {
s += a[K];
}
if (s == k)
len = max(len, j - i + 1);
}
}
return len;
}
int main()
{
vector<int> a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
cout << "The length of the longest subarray is: " << len << "\n";
return 0;
}Output: The length of the longest subarray is: 3
Time Complexity: O(N3) approx., where N = size of the array.
Reason: We are using three nested loops, each running approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Java Code
import java.util.*;
public class tUf {
public static int getLongestSubarray(int []a, int k) {
int n = a.length; // size of the array.
int len = 0;
for (int i = 0; i < n; i++) { // starting index
for (int j = i; j < n; j++) { // ending index
// add all the elements of
// subarray = a[i...j]:
int s = 0;
for (int K = i; K <= j; K++) {
s += a[K];
}
if (s == k)
len = Math.max(len, j - i + 1);
}
}
return len;
}
public static void main(String[] args) {
int[] a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
System.out.println("The length of the longest subarray is: " + len);
}
}Output: The length of the longest subarray is: 3
Time Complexity: O(N3) approx., where N = size of the array.
Reason: We are using three nested loops, each running approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Python Code
from typing import List
def getLongestSubarray(a: [int], k: int) -> int:
n = len(a) # size of the array.
length = 0
for i in range(n): # starting index
for j in range(i, n): # ending index
# add all the elements of
# subarray = a[i...j]:
s = 0
for K in range(i, j+1):
s += a[K]
if s == k:
length = max(length, j - i + 1)
return length
if __name__ == "__main__":
a = [-1, 1, 1]
k = 1
length = getLongestSubarray(a, k)
print(f"The length of the longest subarray is: {length}")Output: The length of the longest subarray is: 3
Time Complexity: O(N3) approx., where N = size of the array.
Reason: We are using three nested loops, each running approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Better Approach (Using two loops):
Approach:
The steps are as follows:
- First, we will run a loop(say i) that will select every possible starting index of the subarray. The possible starting indices can vary from index 0 to index n-1(n = array size).
- Inside the loop, we will run another loop(say j) that will signify the ending index as well as the current element of the subarray. For every subarray starting from the index i, the possible ending index can vary from index i to n-1(n = size of the array).
- Inside loop j, we will add the current element to the sum of the previous subarray i.e. sum = sum + arr[j].
- If the sum is equal to k, we will consider its length i.e. (j-i+1). Among all such subarrays with sum k, we will consider the one with the maximum length by comparing all the lengths.
Intuition: If we carefully observe, we can notice that to get the sum of the current subarray we just need to add the current element(i.e. arr[j]) to the sum of the previous subarray i.e. arr[i….j-1].
Assume previous subarray = arr[i……j-1]
current subarray = arr[i…..j]
Sum of arr[i….j] = (sum of arr[i….j-1]) + arr[j]
This is how we can remove the third loop and while moving the j pointer, we can calculate the sum.
Note: For a better understanding of intuition, please watch the video at the bottom of the page.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int getLongestSubarray(vector<int>& a, int k) {
int n = a.size(); // size of the array.
int len = 0;
for (int i = 0; i < n; i++) { // starting index
int s = 0;
for (int j = i; j < n; j++) { // ending index
// add the current element to
// the subarray a[i...j-1]:
s += a[j];
if (s == k)
len = max(len, j - i + 1);
}
}
return len;
}
int main()
{
vector<int> a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
cout << "The length of the longest subarray is: " << len << "\n";
return 0;
}Output: The length of the longest subarray is: 3
Time Complexity: O(N2) approx., where N = size of the array.
Reason: We are using two nested loops, each running approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Java Code
import java.util.*;
public class tUf {
public static int getLongestSubarray(int []a, int k) {
int n = a.length; // size of the array.
int len = 0;
for (int i = 0; i < n; i++) { // starting index
int s = 0;
for (int j = i; j < n; j++) { // ending index
// add the current element to
// the subarray a[i...j-1]:
s += a[j];
if (s == k)
len = Math.max(len, j - i + 1);
}
}
return len;
}
public static void main(String[] args) {
int[] a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
System.out.println("The length of the longest subarray is: " + len);
}
}Output: The length of the longest subarray is: 3
Time Complexity: O(N2) approx., where N = size of the array.
Reason: We are using two nested loops, each running approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Python Code
from typing import List
def getLongestSubarray(a: [int], k: int) -> int:
n = len(a) # size of the array.
length = 0
for i in range(n): # starting index
s = 0
for j in range(i, n): # ending index
# add the current element to
# the subarray a[i...j-1]:
s += a[j]
if s == k:
length = max(length, j - i + 1)
return length
if __name__ == '__main__':
a = [-1, 1, 1]
k = 1
len = getLongestSubarray(a, k)
print("The length of the longest subarray is:", len)Output: The length of the longest subarray is: 3
Time Complexity: O(N2) approx., where N = size of the array.
Reason: We are using two nested loops, each running approximately N times.
Space Complexity: O(1) as we are not using any extra space.
Optimal Approach (Using Hashing):
Approach:
The steps are as follows:
- First, we will declare a map to store the prefix sums and the indices.
- Then we will run a loop(say i) from index 0 to n-1(n = size of the array).
- For each index i, we will do the following:
- We will add the current element i.e. a[i] to the prefix sum.
- If the sum is equal to k, we should consider the length of the current subarray i.e. i+1. We will compare this length with the existing length and consider the maximum one.
- We will calculate the prefix sum i.e. x-k, of the remaining subarray.
- If that sum of the remaining part i.e. x-k exists in the map, we will calculate the length i.e. i-preSumMap[x-k], and consider the maximum one comparing it with the existing length we have achieved until now.
- If the sum, we got after step 3.1, does not exist in the map we will add that with the current index into the map. We are checking the map before insertion because we want the index to be as minimum as possible and so we will consider the earliest index where the sum x-k has occurred. [Detailed discussion in the edge case section]
In this approach, we are using the concept of the prefix sum to solve this problem. Here, the prefix sum of a subarray ending at index i, simply means the sum of all the elements of that subarray.
Observation: Assume, the prefix sum of a subarray ending at index i is x. In that subarray, we will search for another subarray ending at index i, whose sum equals k. Here, we need to observe that if there exists another subarray ending at index i with sum k, then the prefix sum of the rest of the subarray will be x-k. The below image will clarify the concept:
Now, for a subarray ending at index i with the prefix sum x, if we remove the part with the prefix sum x-k, we will be left with the part whose sum is equal to k. And that is what we want.
That is why, instead of searching the subarrays with sum k, we will keep track of the prefix sum of the subarrays generated at every index using a map data structure.
In the map, we will store every prefix sum calculated, with the index(where the subarray with that prefix sum ends) in a <key, value> pair. Now, at index i, we just need to check the map data structure to get the index i.e. preSumMap[x-k] where the subarray with the prefix sum x-k ends. Then we will simply subtract that index i.e. preSumMap[x-k] from the current index i to get the length of the subarray with sum k i.e. len = i -preSumMap[x-k].
We will apply the above process for all possible indices of the given array. The possible values of the index i can be from 0 to n-1(where n = size of the array).
Edge Case: Why do we need to check the map if the prefix sum already exists?
In the algorithm, we have seen that at step 3.4, we are checking the map if the prefix sum already exists, and if it does we are not updating it. Let’s understand the reason by considering the following example:
Assume the given array is {2, 0, 0, 3}. If we apply the algorithm to the given array without checking, it will be like the following:
In steps 2 and 3 the element at index i is 0. So, in those steps, the prefix sum remains the same but the index is getting updated in the map. Now, when index i reaches the end, it calculates the length i.e. i-preSumMap[rem] = 3-2 = 1. Here it is considering only the subarray [3] which is incorrect as the longest subarray we can get is [0, 0, 3] and hence the length should be 3.
Now, to avoid this edge case i.e. to maximize the calculated length, we need to observe the formula we are using to calculate the length i.e. len = i – preSumMap[rem].
Now, if we minimize the term preSumMap[rem] (i.e. the index where the subarray with sum x-k ends), we will get the maximum length. That is why we will consider only the first or the leftmost index where the subarray with sum x-k ends. After that, we will not update that particular index even if we get a similar subarray ending at a later index.
So, we will check the map before inserting the prefix sum. If it already exists in the map, we will not update it but if it is not present, we will insert it for the first time.
Note: For a better understanding of intuition, please watch the video at the bottom of the page.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
int getLongestSubarray(vector<int>& a, int k) {
int n = a.size(); // size of the array.
map<int, int> preSumMap;
int sum = 0;
int maxLen = 0;
for (int i = 0; i < n; i++) {
//calculate the prefix sum till index i:
sum += a[i];
// if the sum = k, update the maxLen:
if (sum == k) {
maxLen = max(maxLen, i + 1);
}
// calculate the sum of remaining part i.e. x-k:
int rem = sum - k;
//Calculate the length and update maxLen:
if (preSumMap.find(rem) != preSumMap.end()) {
int len = i - preSumMap[rem];
maxLen = max(maxLen, len);
}
//Finally, update the map checking the conditions:
if (preSumMap.find(sum) == preSumMap.end()) {
preSumMap[sum] = i;
}
}
return maxLen;
}
int main()
{
vector<int> a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
cout << "The length of the longest subarray is: " << len << "\n";
return 0;
}Output: The length of the longest subarray is: 3
Time Complexity: O(N) or O(N*logN) depending on which map data structure we are using, where N = size of the array.
Reason: For example, if we are using an unordered_map data structure in C++ the time complexity will be O(N)(though in the worst case, unordered_map takes O(N) to find an element and the time complexity becomes O(N2)) but if we are using a map data structure, the time complexity will be O(N*logN). The least complexity will be O(N) as we are using a loop to traverse the array.
Note: To know more about maps, please refer to this: Hashing | Maps | Time Complexity | Collisions | Division Rule of Hashing | Strivers A2Z DSA Course.
Space Complexity: O(N) as we are using a map data structure.
Java Code
import java.util.*;
public class tUf {
public static int getLongestSubarray(int []a, int k) {
int n = a.length; // size of the array.
Map<Integer, Integer> preSumMap = new HashMap<>();
int sum = 0;
int maxLen = 0;
for (int i = 0; i < n; i++) {
//calculate the prefix sum till index i:
sum += a[i];
// if the sum = k, update the maxLen:
if (sum == k) {
maxLen = Math.max(maxLen, i + 1);
}
// calculate the sum of remaining part i.e. x-k:
int rem = sum - k;
//Calculate the length and update maxLen:
if (preSumMap.containsKey(rem)) {
int len = i - preSumMap.get(rem);
maxLen = Math.max(maxLen, len);
}
//Finally, update the map checking the conditions:
if (!preSumMap.containsKey(sum)) {
preSumMap.put(sum, i);
}
}
return maxLen;
}
public static void main(String[] args) {
int[] a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
System.out.println("The length of the longest subarray is: " + len);
}
}Output: The length of the longest subarray is: 3
Time Complexity: O(N) or O(N*logN) depending on which map data structure we are using, where N = size of the array.
Reason: For example, if we are using an unordered_map data structure in C++ the time complexity will be O(N)(though in the worst case, unordered_map takes O(N) to find an element and the time complexity becomes O(N2)) but if we are using a map data structure, the time complexity will be O(N*logN). The least complexity will be O(N) as we are using a loop to traverse the array.
Note: To know more about maps, please refer to this: Hashing | Maps | Time Complexity | Collisions | Division Rule of Hashing | Strivers A2Z DSA Course.
Space Complexity: O(N) as we are using a map data structure.
Python Code
from typing import List
def getLongestSubarray(a: [int], k: int) -> int:
n = len(a) # size of the array.
preSumMap = {}
Sum = 0
maxLen = 0
for i in range(n):
# calculate the prefix sum till index i:
Sum += a[i]
# if the sum = k, update the maxLen:
if Sum == k:
maxLen = max(maxLen, i + 1)
# calculate the sum of remaining part i.e. x-k:
rem = Sum - k
# Calculate the length and update maxLen:
if rem in preSumMap:
length = i - preSumMap[rem]
maxLen = max(maxLen, length)
# Finally, update the map checking the conditions:
if Sum not in preSumMap:
preSumMap[Sum] = i
return maxLen
if __name__ == "__main__":
a = [-1, 1, 1]
k = 1
length = getLongestSubarray(a, k)
print(f"The length of the longest subarray is: {length}")Output: The length of the longest subarray is: 3
Time Complexity: O(N) or O(N*logN) depending on which map data structure we are using, where N = size of the array.
Reason: For example, if we are using an unordered_map data structure in C++ the time complexity will be O(N)(though in the worst case, unordered_map takes O(N) to find an element and the time complexity becomes O(N2)) but if we are using a map data structure, the time complexity will be O(N*logN). The least complexity will be O(N) as we are using a loop to traverse the array.
Note: To know more about maps, please refer to this: Hashing | Maps | Time Complexity | Collisions | Division Rule of Hashing | Strivers A2Z DSA Course.
Space Complexity: O(N) as we are using a map data structure.
Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]