Indexes of Subarray Sum

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find starting and ending index of first subarray with sum equal to target (non-negative array). Sliding window.

Algorithm

1Sliding window: expand right, contract left when sum > target. When sum == target: return [left+1, right+1] (1-indexed).

Common Pitfalls

•Works for non-negative elements only. For negative elements: prefix sum + hashmap. Return 1-indexed result.

Indexes of Subarray Sum.java

Java

// Approach: Sliding window with two pointers. Expand right until sum >= target, shrink left when sum > target.
// Time: O(n) Space: O(1)

class Solution {
    static ArrayList<Integer> subarraySum(int[] arr, int target) {
        ArrayList<Integer> obj = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                if (sum == target) {
                    obj.add(i + 1);
                    obj.add(j + 1);
                    return obj;
                }
                if (sum > target)
                    break;
            }
        }
        obj.add(-1);
        return obj;// code here
    }
}

Was this solution helpful?