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