Subarray With Given Sum — Medium Problem & Solution

Given an array arr of positive integers and an integer target, find the contiguous subarray that adds up to target.

Difficulty: Medium
Topics: Arrays, Two Pointers, Sliding Window
Asked at: Amazon, Flipkart, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array arr of positive integers and an integer target, find the contiguous subarray that adds up to target.

Return its [start, end] positions using 1-based indexing. If several subarrays qualify, return the one that ends earliest. If none does, return [-1].

Example 1

Input: arr = [1,2,3,7,5], target = 12
Output: [2,4]
Explanation: arr[2..4] is 2 + 3 + 7 = 12.

Example 2

Input: arr = [1,2,3,4,5,6,7,8,9,10], target = 15
Output: [1,5]
Explanation: 1 + 2 + 3 + 4 + 5 = 15.

Example 3

Input: arr = [5,3,4], target = 2
Output: [-1]

Constraints

1 <= arr.length <= 100000
1 <= arr[i] <= 1000
1 <= target <= 1000000000

How to solve Subarray With Given Sum

With strictly positive values the window sum is monotone in both directions, so one window that only ever moves right finds the answer in a single pass.

Approach

Keep start at the window's left edge and a running sum.
Add arr[i] for each new right edge i.
While sum > target and the window holds more than one element, drop arr[start] and advance start.
If sum == target, return [start + 1, i + 1] — the 1-based bounds.

Why it works

For a fixed right end there is at most one left end that hits the target, because shrinking strictly decreases the sum. The loop reports the first right end for which such a left end exists, which is the earliest-ending subarray.

Complexity

Time — O(n) — each index enters and leaves the window once
Space — O(1)

Pitfalls

Returning 0-based indices; the classic statement of this problem is 1-based.
The start < i guard stops the window from collapsing to nothing when a single element already exceeds the target.
This shortcut relies on positivity — with negatives you need prefix sums and a hash map instead.

Reference solution

Python

from typing import List

def subarrayWithSum(arr: List[int], target: int) -> List[int]:
    total = 0
    start = 0
    for i, x in enumerate(arr):
        total += x
        while total > target and start < i:
            total -= arr[start]
            start += 1
        if total == target:
            return [start + 1, i + 1]
    return [-1]

JavaScript

var subarrayWithSum = function(arr, target) {
    var sum = 0, start = 0;
    for (var i = 0; i < arr.length; i++) {
        sum += arr[i];
        while (sum > target && start < i) { sum -= arr[start]; start++; }
        if (sum === target) return [start + 1, i + 1];
    }
    return [-1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue