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.
- 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 <= 1000001 <= arr[i] <= 10001 <= target <= 1000000000
Hints for Subarray With Given Sum
Hint 1
All values are positive, so growing the window can only increase the sum and shrinking it can only decrease it.
Hint 2
That monotonicity is exactly what a sliding window needs — no prefix-sum hash map required.
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
- Keep
startat the window's left edge and a runningsum. - Add
arr[i]for each new right edgei. - While
sum > targetand the window holds more than one element, droparr[start]and advancestart. - 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 < iguard 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