Indexes of Subarray Sum

Problem Description

Given an array of non-negative integers, find the indices of the first subarray whose sum equals a specified target. If no such subarray exists, return [-1].

Example:

• Input: arr[] = [1, 2, 3, 7, 5], target = 12
• Output: [2, 4]
• Explanation: The sum of elements from the 2nd to the 4th position is 2 + 3 + 7 = 12.

Solution Code

class Solution {
    static ArrayList<Integer> subarraySum(int[] arr, int target) {
        ArrayList<Integer> result = new ArrayList<>();
        int n = arr.length;
        int left = 0;
        int currentSum = 0;

        for (int right = 0; right < n; right++) {
            currentSum += arr[right];

            while (currentSum > target && left <= right) {
                currentSum -= arr[left];
                left++;
            }

            if (currentSum == target) {
                result.add(left + 1); // 1-based index
                result.add(right + 1); // 1-based index
                return result;
            }
        }

        result.add(-1);
        return result;
    }
}

Hint

• Use a sliding window approach to maintain a window of elements whose sum is less than or equal to the target. Adjust the window by moving the left pointer if the sum exceeds the target.

Approach Name

Sliding Window Technique

Intuition

The sliding window technique is efficient for problems involving subarrays or substrings. By maintaining a window that expands and contracts based on the sum of elements within it, we can efficiently find the subarray that meets the target sum.

Algorithm

1. Initialize two pointers, left and right, to the start of the array.
2. Use a variable currentSum to keep track of the sum of elements within the current window.
3. Iterate through the array with the right pointer, adding each element to currentSum.
4. If currentSum exceeds the target, move the left pointer to the right and subtract the element at the left pointer from currentSum.
5. If currentSum equals the target, return the 1-based indices of the left and right pointers.
6. If no such subarray is found by the end of the array, return [-1].

Test Input

1 2 3 7 5, 12

Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the array. Each element is processed at most twice (once when expanding the window and once when contracting it).
• Space Complexity: O(1), as we are using a constant amount of extra space.

This solution efficiently finds the first subarray that sums to the target using a sliding window approach, ensuring optimal performance even for large arrays.