9. Indexes of Subarray Sum

The problem can be found at the following link: Problem Link

Problem Description

You are given an array arr[] containing only non-negative integers and a target sum target. Your task is to find the first continuous subarray (a contiguous sequence of elements) whose sum equals the specified value target. If such a subarray exists, return the 1-based indices of the leftmost and rightmost elements of this subarray. Otherwise, return [-1].

Examples

Input:

arr[] = [1, 2, 3, 7, 5] target = 12

Output: [2, 4]

Explanation: The sum of elements from the 2nd to 4th positions (2, 3, and 7) 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 the 1st to 5th positions (1, 2, 3, 4, and 5) is 15.

Input:

arr[] = [5, 3, 4] target = 2

Output: [-1]

Explanation: No subarray exists with a sum equal to 2.

Constraints

• $( 1 \leq \text{arr.size()} \leq 10^6 ) $

• $( 0 \leq \text{arr}[i] \leq 10^3 ) $

• $( 0 \leq \text{target} \leq 10^9 ) $

My Approach

1. Sliding Window Technique (Two-Pointer Approach):

   • Utilize a variable curr to keep track of the sum of elements in the current subarray.

   • Use two pointers:

     • A start pointer s that marks the beginning of the current subarray.

     • A moving end pointer e that iterates through the array.

   • Expand the window by adding the current element (arr[e]) to curr.

   • Shrink the window from the start by incrementing s while curr > target. Subtract elements from the sum during this process.

   • If curr == target, return the indices [s + 1, e + 1].

   • If no subarray with the target sum exists, return [-1].

2. Edge Cases:

   • If the array contains only one element: check if it equals the target.

   • If target == 0: return [-1] since all elements are non-negative.

Time and Auxiliary Space Complexity

• Expected Time Complexity: ( O(n) ), where ( n ) is the size of the array. The algorithm traverses the array only once, using the sliding window technique.

• Expected Auxiliary Space Complexity: ( O(1) ), as the solution uses a constant amount of additional space.

Code (C++)

class Solution {
public:
    vector<int> subarraySum(vector<int>& arr, int target) {
        int s = 0, curr = 0;
        for (int e = 0; e < arr.size(); ++e) {
            curr += arr[e];
            while (curr > target && s <= e) curr -= arr[s++];
            if (curr == target) return {s + 1, e + 1};
        }
        return {-1};
    }
};

Code (Java)

class Solution {
    static ArrayList<Integer> subarraySum(int[] arr, int target) {
        int s = 0, curr = 0;
        for (int e = 0; e < arr.length; e++) {
            curr += arr[e];
            while (curr > target && s <= e) curr -= arr[s++];
            if (curr == target) return new ArrayList<>(Arrays.asList(s + 1, e + 1));
        }
        return new ArrayList<>(Arrays.asList(-1));
    }
}

Code (Python)

class Solution:
    def subarraySum(self, arr, target):
        s, curr = 0, 0
        for e in range(len(arr)):
            curr += arr[e]
            while curr > target and s <= e:
                curr -= arr[s]
                s += 1
            if curr == target:
                return [s + 1, e + 1]
        return [-1]

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count