# 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.

## Java

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.

## Java

Output:

[2, 5]

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

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

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. 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.. 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. Guest
Redwan Ahsan

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? Guest
Redwan Ahsan

Figure it out actually. Sorry for the stupid question. Guest
Mridul Ranjan

[spoiler title=” “]