Subarray With Given Sum

Medium
612.

Subarray With Given Sum

Subarray With Given Sum is a medium coding problem on arrays, two pointers and sliding window, asked in Amazon, Flipkart and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number[]}
 */
var subarrayWithSum = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subarray With Given Sum — Solution in Python, Java & C++

Subarray With Given Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Subarray With Given Sum is a medium coding problem on arrays, two pointers and sliding window, asked in Amazon, Flipkart and Zoho interviews.

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

Hints for Subarray With Given Sum

  1. Hint 1

    All values are positive, so growing the window can only increase the sum and shrinking it can only decrease it.

  2. Hint 2

    That monotonicity is exactly what a sliding window needs — no prefix-sum hash map required.

  3. Hint 3

    Extend on the right; while the sum overshoots, contract from the left.

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

  1. Keep start at the window's left edge and a running sum.
  2. Add arr[i] for each new right edge i.
  3. While sum > target and the window holds more than one element, drop arr[start] and advance start.
  4. 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]

Java

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

C++

vector<int> subarrayWithSum(vector<int>& arr, int target) {
    long long sum = 0;
    int start = 0;
    for (int i = 0; i < (int) arr.size(); i++) {
        sum += arr[i];
        while (sum > target && start < i) { sum -= arr[start]; start++; }
        if (sum == 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique