Last Updated: 21 Jul, 2022
Longest Subarray With Sum K.
Moderate
Asked in companies
Ninja and his friend are playing a game of subarrays. They have an array ‘NUMS’ of length ‘N’. Ninja’s friend gives him an arbitrary integer ‘K’ and asks him to find the length of the longest subarray in which the sum of elements is equal to ‘K’.
Ninjas asks for your help to win this game. Find the length of the longest subarray in which the sum of elements is equal to ‘K’.
If there is no subarray whose sum is ‘K’ then you should return 0.
Example:
Input: ‘N’ = 5, ‘K’ = 4, ‘NUMS’ = [ 1, 2, 1, 0, 1 ]
Output: 4
There are two subarrays with sum = 4, [1, 2, 1] and [2, 1, 0, 1]. Hence the length of the longest subarray with sum = 4 is 4.
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
The first line of each test case contains two integers ‘N’ and ‘K’ denoting the length of the array ‘NUMS’ and an arbitrary integer.
The second line of each test case contains ‘N’ space separated integers.
Output format :
For each test case, you don’t need to print anything just return the length of the longest subarray with the sum ‘K’.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
-10^6 <= NUMS[ i ] <= 10^6
-10^6 <= K <= 10^6
Sum of N Over all the Test cases <= 10^5
Time Limit: 1 sec
Approaches
In this approach, We can iterate over all the subarrays and calculate the sum for each subarray then we can check if the sum of that subarray is equal to ‘K’ or not. If it is equal to ‘K’ then it can be one of the possible answers. We can maintain a variable to find the maximum length among all the subarrays with the sum equal to ‘K’.
The steps are as follows:-
function getLongestSubarray(vector<int>& nums, int k):
- Initialize a variable 'ANS' with 0.
- Run a loop from 'i' = 0... 'N' - 1:
- Initialize a variable 'SUM' with 0.
- Again Run a loop from 'j' = 'i'... 'N' -1:
- Add the value of 'NUMS[ j ]' in variable 'SUM'.
- If 'SUM' is equal to 'K' then update the value of 'ANS' with the maximum of 'ANS' and ('j' - 'i' +1)
- Return the value of 'ANS'.
We can use prefix sum and hashtable to solve this problem efficiently. The idea here is if the sum of elements from 0…’i’ is ‘X’ and the sum of elements from 0…j is also ‘X’ and ‘j’ > ‘i’, then that means the sum of elements of the subarray from ‘i’ + 1 to ‘j’ is 0. Similarly if the sum of elements from 0…’i’ is ‘X’ and the sum of elements from 0…’j’ is ‘X’ + ‘K’ then the sum of elements of the subarray from ‘i’ + 1 to ‘j’ is ‘K’.
We will use a hashtable to store the prefix sum at every index. At every index, we will check if ‘SUM’ - ‘K’ is present in the hashtable or not . If it is present then we can get the index from the hashtable where that sum was encountered. In the case of multiple indices with the same sum, the hashtable will store the smaller index.
The steps are as follows:-
function getLongestSubarray(vector<int>& nums, int k):
- Declare a hashtable 'prefixSumMap'.
- Initialize a variable 'ANS' with 0.
- Initialize a variable 'SUM' with 0.
- Assign -1 to 'prefixSumMap[ 0 ]'.
- Run a loop from 'i' = 0....'N' - 1:
- Add the value of 'NUMS[ i ]' in variable 'SUM'.
- If the value 'SUM' - 'K' is already present in the hashtable then update the value of 'ANS' with the maximum of 'ANS' and 'i' - 'prefixSumMap[ SUM - K ]' + 1.
- If the value of 'SUM' is not present in the hashtable then do 'prefixSumMap[ SUM ]' = 'i'.
- Return the value of variable 'ANS'.