How to find the shortest subarray with sum = k in the given array efficiently ?

Question

N is the length of array .

1<=N<=1000000

1<=A[i]<=100000

Giving explanation is mandatory , giving code depends on your choice . Also add your name at the bottom of answer so you get the due credits. Direct libraries in python are not allowed to be used as they skip the lagorithm parts sometimes.

Answer 1

Basically, you were told to find a subarray in an array whose sum is k .

Solution : Create prefix sum of the array . pref[i] means a[1]+a[2]+a[3]+....a[i].    Now, say you are at index 'i' , and pref[i]-k did occur as a prefix sum earlier..it means you have found a subarray with sum equal to "k" . You can store all pref[i] in a hashmap to do the easy lookup.  Shortest subarray can be selected by knowing the last index which had sum : pref[i]-k , in the hashmmap during lookup .

Answer 2

Approach :

1. Used Two pointer i.e i and j  
2. j pointer is used to add an upcoming event and I pointer is used for removing the initial valued element if my sum goes out of range of targets.

Complexity

• Time Complexity : O(n*n)
• Space complexity: O(1)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    // smallest subarray with sum K
    public static int subArraylen(int arr[], int n, int k)
    {
        int sumsofar = 0;
        int i=-1,j=-1,indexi=0,indexj=0;
        int minlen  = Integer.MAX_VALUE;
        while(i<arr.length && j<arr.length) {
            if(i==-1 && j==-1) {
                i=0;
                j=0;
            }
            sumsofar+=arr[j];
            while(sumsofar > k) {
                sumsofar-=arr[i];
                i++;
            }
            if(sumsofar == k) {
                minlen =Math.min(minlen, j-i+1);
                indexi=i;
                indexj=j;
            }
            j++;
        }

        return minlen;
    }
    public static void main(String[] args)
    {
        int arr[] = { 11, 22, 23, 41,12,12,32,13,23,24,24,2,1,2,2,3,4 };
        int n = arr.length;

        int K = 7;

        int len = subArraylen(arr, n, K);

        if (len == Integer.MAX_VALUE)
        {
            System.out.println("Subarray doesnt exits");
        }
        else
        {
            System.out.println("len ="+len + "\n");
        }
    }
    }

Answer 3

//Time = O(n)
//space = O(n)
//we will store the prefix sum as key, and the index as value in a map(index denotes the prefix sum till that point
//we will iterate the array,calculate the prefix sum till that point, if (prefixsum-k) is present in the map, then find the index of prefixsum-k, subtract the current counter and find the minimum length

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0,k,x,j;
    cin>>n>>k;
    vector<int> a(n);
    map<int,int> mp;
    
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        
    }
    int mx=INT_MAX;
    mp[0]=0;
    for(int i=0;i<n;i++)
    {
    
        sum+=a[i];
        if(mp.find(sum-k)!=mp.end())
        {
            j=mp[sum-k];
            mx=min(mx,i-j);
        }
        mp[sum]=i+1;
    }
    if(mx<n)
        cout<<++mx;
    else
        cout<<" no subarray where sum= k";
}

Answer 4

arr=list(map(int,input().split()))  # array as space saperated integers
k=int(input()) # K
n=len(arr)
minn=n
ind=0
lastInd=0
summ=0
while(ind<n):
    summ+=arr[ind]
    if summ==k:
        minn=min(minn,ind-lastInd+1)
    if summ>k:
        while(summ>k):
            summ-=arr[lastInd]
            lastInd+=1
        if summ==k:
            minn=min(minn,ind-lastInd+1)
    ind+=1
print(minn)