Longest subarray with sum as K

Posted in

Longest subarray with sum as K
vinaykhatri

Vinay Khatri
Last updated on March 28, 2024

    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 .

    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 Comment on this Post

    0 Comments