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

Notify of
avatar
Sort by:   newest | oldest | most voted
Manohar
Guest
Manohar

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

Amith
Guest
Amith

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
cz21
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,… Read more »
wpDiscuz