Find subarrays with a given sum in an array

Posted in

Find subarrays with a given sum in an array
maazbinasad

Maaz Bin Asad
Last updated on May 30, 2024

    Problem

    Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number. Print the starting and ending indices of the subarray.

    Sample Input

    [1, 4, 20, 3, 10, 5] k = 33

    Sample Output

    2 4

    Approach

    We can initialize two pointers as left and right both to index 0 and a variable sum=0 to track sum of subarrays. When we see that the sum is greater than k , we decrement the sum by the element at left index and increment left . When the sum of the subarray is smaller than k , we add an element at right index to sum and increment right . The time complexity of this approach is O(N).

    C++

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    int a[4]={10, 4, 22, 4}, k = 22;
    int n = sizeof(a)/sizeof(a[0]);
    int l=0, r=0;
    int sum = 0;
    while(r<n)
     {
     if(sum==k) break;
     //we found the subarray
     if(sum>k) sum-=a[l++]; //decrement from left
     if(sum<k) sum+=a[r++]; //increment from right
    }
    cout<<l<<" "<<r-1;
    }
    

    Output

    2 2

    C

    #include<stdio.h>
    void main(){
    int a[4]={10, 4, 22, 4}, k = 22;
    int n = sizeof(a)/sizeof(a[0]);
    int l=0, r=0;
    int sum = 0;
    while(r<n)
     {
     if(sum==k) break; //we found the subarray
     if(sum>k) sum-=a[l++]; //decrement from left
     if(sum<k) sum+=a[r++]; //increment from right
    }
    printf("%d %d",l,r-1);
    }
    

    Output

    2 2

    Python

    a=[10, 4, 22, 4]
    k = 22
    n = 4
    l = 0
    r = 0
    sum = 0
    while r<n:
     if(sum==k):
     break #we found the subarray
     if(sum>k):
     sum-=a[l] #decrement from left
     l+=1
     if(sum<k):
     sum += a[r] #increment from right
     r+=1
    print(l,r-1)

    Output

    2 2

    People are also reading:

    Leave a Comment on this Post

    0 Comments