Maximum size subarray sum equals k

Difficulty Level Medium
Frequently asked in Facebook Microsoft
Array Hash HashingViews 2357

In Maximum size subarray sum equals k we have given an array of integers and a value k. You have to find the length of the longest subarray whose sum is equal to k. If no such subarray exists then return 0.

One approach is to use hashtable and check if the sum is equal to k and return the length of that subarray whose length is equal to k.

Example:

Input:

A[]={10, 5, 2, 7 , 1, 9};

k = 15;

Output:

4

Explanation:

There are multiple sub-arrays whose sum could be 15 like {10, 5}, {5, 1,  9}, {5, 2, 7, 1} but the longest subarray with sum 15 is {5, 2, 7, 1} whose length is 4.

Maximum size subarray sum equals k

Algorithm

  1. Tek two variables suppose summation and length and set them to zero i.e., summation=0, lengths=0.
  2. Declare key-value pair (map or hash-table)
  3. Iterate through the loop from index =0 to index-1 and proceed further with the following ways-
  4. Sum up the array and summation into summation.
  5. If summation found to be equal with the k, then make the value of lengths increased by 1.
  6. Proceed further with the check of summation is present or not, if not then add it as key-value pair.
  7. If (summation – k) finds a presence in hashtable then get the index.
  8. If above line satisfies,then update the value of lengths, if lengths<index-storeVal[summation -k] then set lengths=index-storeVal[summation -k].

Explanation For Maximum size subarray sum equals k

This is going to be an effective way in which we can implement this code with efficient time complexity. So our main idea is to use a HashMap and some variables which are going to store different values in it.

This code uses for loop which goes on till the length of array reached. First, it going to sums up the value of arr[i] and add it to summation and make the summation updated. If the value of summation finds to be equal with the value of k then it will update and increase the value of lengths by 1.

The very next if block is going to check whether the storeVal(which is a HashMap variable) contains the value of summation in a map and if it does not contain summation as a key in a map it will make an entry in map and put the value of summation and index in map.

The next if block going to check if storeVal contains the key in the form of ( summation – k ) and if it so then it will compare the lengths with ( index – storeVal (summation – k ) ) and if the length is less than ( index – storeVal (summation – k ) ) then it will make the lengths = ( index – storeVal (summation – k ) ), and it goes on till we find our maximum length of subarray with a summation equal to k and at last returns lengths.

Suppose array given:

arr={10, 5, 2, 7, 1, 9 }

i=0; summation=10, // summation+=arr[i]

summation==k // ( check summation equal to k ) // here not

if (!storeVal.containsKey(sum))

storeVal.put(sum,i) /* everytime it will put the values of summation and index as key value pair in the map*/

if ( storeVal.containsKey(summation – k))// here not

And it will continues up and does not enter in if block till it satisfies the condition and it will satisfies at index=4 and the some operations performs and we get the correct answer.

Implementation in C++ for Maximum size subarray sum equals k

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int lenOfSubArray(int arr[], int n, int k)
{
  int summation = 0, lengths = 0;
  map<int, int> storeVal;
  for (int index = 0; index < n; index++)
  {
    //sums up the array
    summation += arr[index];
    //check if summation is equals to k
    if (summation == k)
    {
      lengths = index + 1;
    }

    if (storeVal.find(summation) == storeVal.end())
    {
      //store the values as a key value pair in
      //map
      storeVal[summation] = index;
    }

    if (storeVal.find(summation - k) != storeVal.end())
    {
      //updation of lengths
      if (lengths < (index - storeVal[summation - k]))
      {
        lengths = index - storeVal[summation - k];
      }
    }
  }

  return lengths;
}

int main()
{
  int arr[] = { 2, 5, 7, 3, 7, 9, 1 };
  int k = 17;
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << "Length of Longest Substring is:" << lenOfSubArray(arr, n, k);
  return 0;
}
Length of Longest Substring is: 4

Implementation in java for Maximum size subarray sum equals k

import java.util.*;
import java.io.*;
class findMaxSubArray {
    public static int lenOfSubArray(int arr[], int n, int k) {
        int summation = 0, lengths = 0;
        HashMap<Integer, Integer> storeVal = new HashMap<>();
        for (int index = 0; index<n; index++) {
            //sums up the array
            summation += arr[index];
            //check if summation is equals to k
            if (summation == k) {
                lengths = index + 1;
            }
            if (!storeVal.containsKey(summation)) {
                //store the values as a key value pair in
                //map
                storeVal.put(summation, index);
            }
            if (storeVal.containsKey(summation - k)) {
                //updation of lengths
                if (lengths<(index - storeVal.get(summation - k))) {
                    lengths = index - storeVal.get(summation - k);
                }
            }
        }
        return lengths;
    }
    //Driver code
    public static void main(String args[]) {
        int arr[] = { 2, 5, 7, 3, 7, 9, 1 };
        int k = 17;
        int n = arr.length;
        System.out.println("Length of Longest Substring is:" + lenOfSubArray(arr, n, k));
    }
}
Length of Longest Substring is:4

Complexity Analysis

Time complexity

 O(n) where n is the size of the array.

Auxiliary Space

 O(n) where n is the size of the array.

References

Translate »