GeeksforGeeks: Indexes of Subarray Sum

 

Indexes of Subarray Sum

Difficulty: Medium

Given an array arr[] containing only non-negative integers, your task is to find a continuous subarray (a contiguous sequence of elements) whose sum equals a specified value target. You need to return the 1-based indices of the leftmost and rightmost elements of this subarray. You need to find the first subarray whose sum is equal to the target.

Note: If no such array is possible then, return [-1].

Examples:

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

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

Input: arr[] = [5, 3, 4], target = 2
Output: [-1]
Explanation: There is no subarray with sum 2.

Constraints:
1 <= arr.size()<= 106
0 <= arr[i] <= 103
0 <= target <= 109

To solve this problem efficiently, we can use a sliding window technique with the two-pointer approach. This is a very efficient way to find the subarray with a target sum in linear time, as it avoids checking all possible subarrays (which would be inefficient for large arrays).

Approach: Sliding Window (Two Pointers)

1. Start with two pointers: Begin with both pointers (start and end) at the start of the array. The end pointer will iterate over the array, and the start pointer will help in maintaining the subarray sum that matches the target.
2. Expand the window: As end moves forward, accumulate the sum of elements between the start and end pointers.
3. Shrink the window if necessary: If the sum exceeds the target, increment the start pointer to reduce the sum.
4. Check for match: If at any point the sum equals the target, return the 1-based indices of the start and end pointers.
5. Edge Case: If no subarray is found that matches the target, return [-1].

Code Implementation:

public class Solution {
    public int[] SubarraySum(int[] arr, int target) {
        int n = arr.Length;
        int start = 0, currentSum = 0;
        
        for (int end = 0; end < n; end++) {
            currentSum += arr[end];
            
            // Shrink the window from the left if the sum exceeds target
            while (currentSum > target && start <= end) {
                currentSum -= arr[start];
                start++;
            }
            
            // If current sum equals target, return the 1-based indices
            if (currentSum == target) {
                return new int[] { start + 1, end + 1 }; // 1-based index
            }
        }
        
        // If no subarray found
        return new int[] { -1 };
    }
}

Explanation:

1. Initialize start and currentSum: start is the left pointer of the window, and currentSum keeps track of the sum of elements between start and end.
2. Iterate through the array: The end pointer moves through each element, and we add the value to currentSum.
3. Shrink the window if necessary: If currentSum exceeds the target, we increment the start pointer and subtract the value at start from currentSum to reduce the sum.
4. Check for a match: Whenever currentSum equals the target, we return the 1-based indices (start + 1 and end + 1).
5. Return [-1] if no match is found: If the loop ends without finding a subarray whose sum equals the target, we return [-1].

Time Complexity:

• Time Complexity: $O(n)$, where n is the size of the array. Each element is processed at most twice (once when adding to currentSum and once when removing from currentSum).
• Space Complexity: $O(1)$ because we are only using a few variables (start, currentSum, etc.) and not using any extra space proportional to the input size.

Example Walkthrough:

Example 1:

• Input: arr[] = [1, 2, 3, 7, 5], target = 12
• Iteration steps:
  • start = 0, end = 0, sum = 1
  • start = 0, end = 1, sum = 3
  • start = 0, end = 2, sum = 6
  • start = 0, end = 3, sum = 13 → shrink the window (start = 1)
  • start = 1, end = 3, sum = 12 → found the subarray.
• Output: [2, 4] (1-based indices).

Example 2:

• Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 15
• Iteration steps:
  • start = 0, end = 4, sum = 15 → found the subarray.
• Output: [1, 5] (1-based indices).

Example 3:

• Input: arr[] = [5, 3, 4], target = 2
• No subarray with sum 2.
• Output: [-1].

This approach is optimal and ensures that we efficiently find the required subarray in linear time.