Longest subarray with sum as K

By | October 6, 2021

Problem statement

Given an n-dimensional array of integers, arr[].

The task is to determine the length of the longest subarray with a total equal to the supplied value K.

Vamware

Sample Input

[1, 2, 3, 4, 0]      K=7

Sample output

3

Explanation

The longest subarray with sum as 7 is [3, 4, 0]

Brute Force approach

Consider the total of all subarrays and return the length of the longest subarray with sum K.

The time complexity is O(n2).

Efficient approach

Set sum to 0 and maxLen to 0.

Make a hash table that contains sum as its keys and vectors of indices as values.

Perform the following steps for i = 0 to n-1:

Add arr[i] together to get the total.

If total equals K, set maxLen to i+1.

Check to see if the sum-K is contained in the hash table.

If it’s present, then iterate the respective vector and keep updating the maxLen with the maximum length of the subarray.

Insert the current sum into the map.

 

An optimization

Instead of storing the vector of indices, you could create a pair of (sum,i) where i will store the earliest index with a given sum. Insert the sum as key only if it is not present in the map. 

Let’s look at these approaches.

C++

#include<bits/stdc++.h>
using namespace std;
int lenOfLongSubarr(int a[],  int N, int K)
	{
    	long long int sum=0;
    	int ans=0;
    	unordered_map<long long int,vector<int>>mp;
    	for(int i=0;i<N;i++){
        	sum+=a[i];
        	if(sum==K){
            	    ans=max(ans,i+1);
        	}
        	if(mp.find(sum-K)!=mp.end()){
            	    for(auto itr:mp[sum-K]){
                	ans=max(ans,i-itr);
            	}
        	}
        	mp[sum].push_back(i);
    	}
    	return ans;
	}
int main(){
int arr[5] = {1, 2, 3, 4, 0};
int K = 7;
lenOfLongSubarr(arr, 5, K);
}

Python

def findLongestSubarray(arr, n, k):

    my_dictionary = dict()

    # Initialize sum and maxLen with 0
    sum = 0
    maxLen = 0

    # traverse the given array
    for i in range(n):

   	 # accumulate the sum
   	 sum += arr[i]

   	 # when subArray starts from index '0'
   	 if (sum == k):
   		 maxLen = i + 1

   	 elif (sum - k) in my_dictionary:
   		 maxLen = max(maxLen, i - my_dictionary[sum - k])

   	 if sum not in my_dictionary:
   		 my_dictionary[sum] = i

    return maxLen

l = [1, 2, 3, 4, 0]
K = 7
print(findLongestSubarray(l, 5, K))

C#

using System;
using System.Collections.Generic;

class Solution
{

static int longestSubarray(int[] arr, int n, int k)
{
    Dictionary<int, int> map_sum = new Dictionary<int,int>();
    int sum = 0, maxLen = 0;

    // traverse the array
    for (int i = 0; i < n; i++)
    {
   	 
   	 // accumulate sum
   	 sum += arr[i];
   	 
   	 if (sum == k)
   		 maxLen = i + 1;

   	 if (!map_sum.ContainsKey(sum))
   	 {
   		 map_sum.Add(sum, i);
   	 }

   	 // check if 'sum-k' is present in 'map_sum'
   	 if (map_sum.ContainsKey(sum - k))
   	 {
   		 // update maxLength
   		 if (maxLen < (i - map_sum[sum - k]))
   			 maxLen = i - map_sum[sum - k];
   	 }
    }
    
    return maxLen;   	 
}
public static void Main(String []args)
	{
    	int[] arr = {1, 2, 3, 4, 0};
    	int n = arr.Length;
    	int K = 7;
    	Console.WriteLine(longestSubarray(arr, n, K));

}
}

People are also reading:

Leave a Reply

Your email address will not be published. Required fields are marked *