Subarray with Given Sum – Two Pointers Solution

Introduction :

Subarrays are a basic concept in array-based programming challenges, and they are frequently used in a variety of methods and data structures.

This blog post will cover a frequent subarray problem: locating a continuous subarray in an array that adds up to a specific value.

The “Subarray with given sum” problem comes up frequently in technical interviews and is a common topic in computer science and data structures.

The challenge is to identify the continuous subarray that adds up to the given target sum ,given an array of integers and a target sum.

Return any subarray that adds up to the target total if there are multiple subarrays that do so. Return an empty array if none of the subarrays add up to the desired total.

Sliding Window approach :

• Using a sliding window method is one way to deal with this issue.
• This method uses two pointers, one to maintain track of the beginning of the subarray and the other of the subarray’s end.
• The two pointers are first assigned to the array’s first element.
• The total of the elements in the window, which is the subarray between the two pointers, is updated as we traverse through the array.
• If the total exceeds the desired total, we narrow the window and lower the total by moving the left cursor to the right.
• If the total falls short of the desired total, we move the right cursor to the right to increase the window’s size.
• This step is repeated until the desired sum is obtained or until all subarrays have been examined, whichever comes first.
• Here is some sample code to show how to use the sliding window method to find a subarray with a certain sum.

Question :

Below question is picked from GeeksForGeeks and it is listed under top 50 array questions.

• In case of multiple subarrays, return the subarray indexes which comes first on moving from left to right.
• Note:- Both the indexes in the array should be according to 1-based indexing. You have to return an arraylist consisting of two elements left and right. In case no such subarray exists return an array consisting of element -1.

Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements 
from 2nd position to 4th position 
is 12.

Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements 
from 1st position to 5th position
is 15.

Your Task:
You don’t need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N, and S as input parameters and returns an arraylist containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the array should be according to 1-based indexing.

If no such subarray is found, return an array consisting of only one element that is -1.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 10⁵
1 <= A_i <= 10⁹

//Solution by technoname.com

class Solution {
    //Function to find a continuous sub-array which adds up to a given number.
    static ArrayList<Integer> subarraySum(int[] a, int n, int s) {
        int i, j;
        int sum = 0;
        int start=0;
        ArrayList<Integer> al = new ArrayList<>();

        for (i = 0; i < n; i++) {
            
                sum=sum+a[i];
                while(sum>s){
                    sum=sum-a[start];
                    start++;
                }
                if(sum==s && s!=0){
                    al.add(start+1);
                    al.add(i+1);
                    return al;
                }
            
    }
    al.add(-1);
    return al;
}
}

Subarray with given sum using Sliding Window code Explanation :

The code is defining a class called “Solution” that contains a function named “subarraySum”. The function takes in three parameters: an array “a”, an integer “n”, and an integer “s”.

The function is used to find a continuous subarray in the given array “a” that adds up to the given integer “s”.

Steps :

• The function begins by setting up a number of variables:
• The variable “sum” has a starting value of 0, and it will be used to track the subarray’s current sum.
• The variable “start” has an initial value of 0, and it will be used to record the subarray’s starting index.
• The starting and ending indices of the subarray will be kept in “al,” an ArrayList.
• A for loop that iterates across the array “a” is then started by the function. The loop runs until I n, starting with i=0.
• The current array element is added to the “sum” variable inside the for loop.
• Beginning with the specified integer “s,” the while loop determines whether the sum is greater.
• If so, the code deducts the subarray’s first element (the one with index “start”) from the total and raises the “start” variable by one.
• Until the sum is less than or equal to “s,” the loop continues to run.
• Following the while loop, the code determines whether the total equals “s” and whether “s” is not equal to 0.
• The starting and ending indices of the subarray are added to the ArrayList “al” and the ArrayList is returned if both conditions are true.
• The code adds -1 to the ArrayList and returns it if the for loop ends without finding a subarray that adds up to “s”.
• This code is trying to find a subarray with a given sum “s” in the array “a” and returns the subarray indices in ArrayList.
• The while loop is used to find the subarray by sliding the window of size (end-start) through the array and keeping track of the current sum and start index.

Thank you !!

Thank you for reading this article so far, if you know some other way to write above programs then you can leave a comment here or mail us at technonamecontact@gmail.com, So anyone can a get chance to publish their code on our website. As a result, one can improve knowledge and spread it to others

Please check most asked programming questions of strings with examples by clicking here, after that you might get a deep knowledge about string operations, in short, it will be helpful in clearing the interview.

For understanding the most important concept of data structures in an easy way you can check this article on our website.

If you like this article, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.

You can also follow us on Twitter for daily updates.