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 🙂