Let's say you have given an array of size N, which can have a positive and a negative number. we need to return the length of the largest subarray of sum equal to k. I tried to use the sliding window algorithm but soon I found out it won't work here since the array element can have a positive and negative integer.
For E.g:
arr=[-20,-38,-4,-7,10,4] and k = 3 It's obvious, there are two possible subarray ([-4,-7,10,4] and [-7,10]) whose sum will equal to given k. So the output will be 4(Length of largest subarray)
The brute force approach will take O(n^2) is there any better way to do the same problem?
CodePudding user response：
Make a hashtable.
Walk through array, calculating cumulative sum (from 0th item upto i-th one), and put result in hash table with current sum as key and for value -insert index into pair of the first ans last occurence like this: {13:[2,19]} sum 13 is met first at index 2 and rightmost position for this sum is 19.
Then scan array again. For index i with sum S look hashtable for key S k and choose the farthest index. For example, having index 5, sum 6, k=7 we can find the farthest index 19 in example above.
CodePudding user response：
You can find more information about the question in geekforgeeks, "Longest sub-array having sum k".
Naive Approach: Consider the sum of all the sub-arrays and return the length of the longest sub-array having the sum ‘k’.
Time Complexity is of O(n^2).
Efficient Approach would be(using hash table):
- Initialize sum = 0 and maxLen = 0.
- Create a hash table having (sum, index) tuples.
- For i = 0 to n-1, perform the following steps:
- Accumulate arr[i] to sum
- If sum == k, update maxLen = i 1.
- Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
- Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
- Return maxLen.
Time Complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(N), for storing the maxLength in the HashMap.
Another Approach
This approach won’t work for negative numbers The approach is to use the concept of the variable-size sliding window using 2 pointers Initialize i, j, and sum = k. If the sum is less than k just increment j, if the sum is equal to k compute the max and if the sum is greater than k subtract the ith element while the sum is less than k.
Time Complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(1).