Find maximum length sub-array having given sum

Given an array of integers, find maximum length sub-array having given sum.


 

For example, consider below array


A[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }
Sum = 8
 

Sub-arrays with sum 8 are

{ -5, 5, 3, 5 }
{ 3, 5 }
{ 5, 3 }

The longest subarray is { -5, 5, 3, 5 } having length 4

 

Naive solution would be to consider all sub-arrays and find their sum. If sub-array sum is equal to given sum, we update maximum length sub-array. The time complexity of naive solution is O(n3) as there are n2 sub-arrays and it takes O(n) time to find sum of its elements. The method can be optimized to run in O(n2) time by calculating sub-array sum in constant time.

C

Download   Run Code

Java

Download   Run Code



Output:


[2, 5]

 

We can use map to solve this problem in linear time. The idea is to create an empty map to store ending index of first sub-array having given sum. We traverse the given array, and maintain sum of elements seen so far.

  • If sum is seen for first time, insert the sum with its index into the map.
     
  • If (sum – S) is seen before, there exists a sub-array with given sum which ends at current index and we update maximum length sub-array having sum S if current sub-array has more length.

C++

Download   Run Code

Java

Download   Run Code



Output:


[2, 5]

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Manohar
Guest

I think unordered_multimap should be used , because there may exist multiple sums.

Vaibhavi
Guest

This is a maximisation problem. So, as soon as we come across any instance where both sum and (sum-k) have occured, then we only need to consider the leftmost or the first seen instance of (sum-k) for the maximum length window.

I’ll give you an example. Consider an arr = [3, 1, 2, 3, -3, 3, 4, -4, 3].

Here, k = 6.

We’ll use 1-based indexing.
Sum = 9 occurs at pos = 4 and also at, pos = 6, and at pos = 8, and finally at, pos=9.

Sum = 3 occurs at pos = 1.

Required ans = 8.
You can clearly see that the max length subarray(l, r) is the one with the least index l which is (1, 8), the rest of the subarrays with the same sum=6 like (4, 8) and (6, 8) etc. produce the non-optimal solution.

Amith
Guest

Hi,
What is importance if map.find(sum – S)?I did not understand the logic behind that.Why it should be (sum – S), why not (S – sum)?This helps me understanding better than remembering the code..

cz21
Guest

Just consider if we current at index i, calculate the sum is X, and loop goes on, at index j, calculate the sum is Y, and Y – S = X –> Y – X = S. In other words, the diff between i and j’ sum is S. Also, we already put the sum’s index in the map, and can get the length.

Redwan Ahsan
Guest

How is sum seen for the first time with (map.find(sum) == map.end())? The first time around the map is empty so it won’t find anything. map.end() will also just return the last item’s iterator. So this condition wouldn’t ever be fulfilled would it?

Where am I mistaken?

Redwan Ahsan
Guest

Figure it out actually. Sorry for the stupid question.

Mridul Ranjan
Guest

[spoiler title=” “]