Subarray with given sum

First and foremost we need to understand what is Subarray first What is Subarray:

A subarray is a contiguous (consecutive) portion of an array. In other words, a subarray is a portion of an array that consists of consecutive elements of the array, where the first and last elements of the subarray are chosen based on a specified range of indices.

For example, consider the following array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Some examples of subarrays of this array include:

• [1, 2, 3]

• [4, 5, 6, 7]

• [8, 9, 10]

• [2, 3, 4, 5]

• [7]

Note that a subarray must consist of consecutive elements of the array. For example, [1, 3, 5] is not a subarray of the above array, because it skips over elements. To find all subarrays of an array in Java, you can use nested loops to iterate over all possible start and end indices of each subarray. Here's an example implementation:

public static void findAllSubarrays(int[] arr) {
    // Iterate over all possible start indices
    for (int i = 0; i < arr.length; i++) {
        // Iterate over all possible end indices
        for (int j = i; j < arr.length; j++) {
            // Print the subarray from i to j
            for (int k = i; k <= j; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();
        }
    }
}

This implementation uses three nested loops. The outermost loop iterates over all possible start indices of each subarray. The middle loop iterates over all possible end indices of each subarray, starting from the current start index. The innermost loop prints out each element of the current subarray.

To use this method, you can call findAllSubarrays and pass in an array of integers:


int[] arr = {1, 2, 3};
findAllSubarrays(arr);

This will output all possible subarrays of the array [1, 2, 3]:

1
1 2
1 2 3
2
2 3
3

But now the question is subarray with given sum

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

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

Note:- 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.

Example 1:

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

Example 2:

Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,7,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 takes arr, N, and S as input parameters and returns 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 <= 105 1 <= Ai <= 109 1st Approach To find a subarray with a given sum in an array, you can use a sliding window technique. Here's an example implementation in Java:

public static int[] findSubarrayWithSum(int[] arr, int sum) {
    int left = 0; // left endpoint of the window
    int right = 0; // right endpoint of the window
    int currentSum = 0; // sum of the current window
    
    while (right < arr.length) {
        // expand the window to the right
        currentSum += arr[right];
        while (currentSum > sum && left <= right) {
            // shrink the window from the left if the sum exceeds the target
            currentSum -= arr[left];
            left++;
        }
        if (currentSum == sum) {
            // found a subarray with the target sum
            int[] subarray = Arrays.copyOfRange(arr, left, right + 1);
            return subarray;
        }
        right++; // expand the window to the right
    }
    
    // no subarray with the target sum was found
    return null;
}

Time Complexity : O(n^2) This implementation uses two pointers, left and right, to create a window that slides over the array. The currentSum variable keeps track of the sum of the elements in the current window.

The algorithm starts with the window consisting of only the first element. If the sum of the current window exceeds the target sum, the window is shrunk from the left by incrementing left and subtracting the corresponding element from currentSum. If the sum of the current window equals the target sum, a subarray with the target sum has been found and returned. To use this method, you can call findSubarrayWithSum and pass in an array of integers and a target sum:

int[] arr = {1, 4, 20, 3, 10, 5};
int sum = 33;
int[] subarray = findSubarrayWithSum(arr, sum);
System.out.println(Arrays.toString(subarray));

This will output the subarray [20, 3, 10], which is the subarray with the target sum of 33. If no subarray with the target sum is found, the method will return null. Optimal Approach

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> list = new ArrayList<>();
        int start = 0;
        int end = 0;
        long sum = arr[0];
        
        if(n == 1)
        {
             list.add(1);
		        list.add(1);
		        return list;
        }
        if(s == 0)
        {
            list.add(-1);
		return list;
        }
		
		while(end<n-1)
		{
		    
		    if(sum+arr[end+1] <= s)
		    {
		        sum += arr[end+1];
		        end++;
		    }
		    else
		    {
		        sum -= arr[start];
		        start++;
		    }
		    if(sum == s)
		    {
		        list.add(start+1);
		        list.add(end+1);
		        return list;
		    }
		}
		
		list.add(-1);
		return list;
        
    }
}

Time Complexity: O(n)