Subarray with given sum Solution In Java

Given an unsorted array A of size N that contains only non-negative integers, find a continuous sub-array which adds to a given number S and return the left and right index of that subarray.

In case of multiple subarrays, return the subarray indexes which comes first on moving from left to right.

Algorithm:

The given code finds a continuous subarray in an input array arr of size n that adds up to a given number s. Here is a step-by-step algorithm to explain the code:

1. Create an empty ArrayList al to store the output subarray indices.
2. Initialize two pointers i and j to 1 and 0 respectively.
3. Initialize a variable sum to the first element of the input array arr[0].
4. Use a for loop that iterates from i = 1 to i <= n.
5. Inside the loop, use a while loop to keep removing elements from the start of the subarray until the sum is greater than s. This is done using the pointer j, which keeps track of the start of the subarray.
6. If the sum is equal to s, add the start and end indices of the subarray to the ArrayList al and break out of the loop.
7. If the sum is less than s, and there are still elements left in the input array, add the next element to the sum.
8. After the loop, if al is still empty, add -1 to al.
9. Return the ArrayList al.

The overall time complexity of this algorithm is O(n), as it uses only one loop to iterate through the input array. The space complexity is also O(n), as the ArrayList al can store up to n/2 elements in the worst case.

Subarray with given sum Solution In Java:

class Solution
{
    //Function to find a continuous sub-array which adds up to a given number.
    static ArrayList<Integer> subarraySum(int[] arr, int n, int s) 
    {
        // Your code here
        ArrayList<Integer> al=new ArrayList<Integer>();
        int i=1;
        int j=0;
        int sum=arr[0];
        for(i=1;i<=n;i++){
            
            while(sum>s&& j<i-1){
                sum-=arr[j];
                j++;
            }
            if(sum==s) {
                al.add(j+1);
                al.add(i);
                break;
                
            }
            
            if(i<n){
                sum+=arr[i];
                
            }
            
            
            
            
        }
        if(al.size()==0) al.add(-1);
        return al;
    }
}

Disclaimer: This problem(Subarray with given Sum) is originally created by GeeksforGeeks. Codesagar only provides a solution for it. This solution is only for Educational and learning purposes.