How Do You Find a Subarray With a Given Sum?
Learn sliding-window and prefix-sum approaches to find a contiguous subarray summing to a target in O(n) time.
Expected Interview Answer
For arrays of non-negative integers, a sliding window expands and shrinks two pointers over the array to find a contiguous subarray summing to a target in O(n) time and O(1) space; for arrays with negative numbers, a running-sum-plus-hash-map approach is required instead.
The sliding window keeps a running sum between a left and right pointer: expand right and add its value while the sum is below target, and shrink from the left while the sum exceeds target, checking for equality at each step. This only works correctly when all numbers are non-negative, because shrinking the window is guaranteed to decrease the sum monotonically. When negative numbers are allowed, the sum is no longer monotonic with window size, so the standard fix is to track a running prefix sum and store each prefix sum seen so far in a hash map; if runningSum minus target has been seen before, the subarray between those two points sums to target. Both approaches run in O(n) time, but the technique choice depends entirely on whether negative values are possible.
- O(n) time using only one pass over the array
- O(1) space for the non-negative sliding-window case
- Hash-map prefix-sum variant handles negative numbers correctly
- Directly generalizes to counting subarrays or finding the longest one
AI Mentor Explanation
Picture scanning a sequence of overs’ runs scored, expanding your window of overs to the right while the running total is below the target score, then shrinking from the left once the total overshoots it, since every over adds non-negative runs. Because runs never subtract from the total, shrinking the window is guaranteed to lower the sum, which is exactly what makes the two-pointer slide valid here. If a wicket-maiden over (zero runs) or a negative-run scenario existed, this monotonic shrink would break, and you would instead need to remember every running total seen so far, similar to tracking cumulative scores at each ball to spot a matching gap later. Landing the window sum exactly on target marks the overs that produced that score.
Step-by-Step Explanation
Step 1
Check for negative numbers
Decide whether all values are non-negative (sliding window works) or negatives are possible (need prefix-sum hash map).
Step 2
Non-negative case: expand and shrink
Move right forward adding to a running sum; while sum exceeds target, move left forward subtracting from it.
Step 3
Check for equality at each step
After each adjustment, compare the running sum to target and return the current window bounds on a match.
Step 4
Negative case: prefix sum plus hash map
Track cumulative sum and a map of {prefix sum -> index}; if runningSum - target exists in the map, a matching subarray is found.
What Interviewer Expects
- Distinguish the non-negative sliding-window case from the general prefix-sum-with-hash-map case
- Explain why shrinking the window is only valid when all values are non-negative
- State O(n) time for both variants and O(1) vs O(n) space respectively
- Handle the target-sum-of-zero-from-the-start edge case (seed the map with {0: -1})
Common Mistakes
- Using the sliding window on arrays that contain negative numbers, producing wrong answers
- Forgetting to seed the prefix-sum map with {0: -1} for subarrays starting at index 0
- Shrinking the window before checking for a match, skipping a valid answer
- Confusing "subarray" (contiguous) with "subsequence" (not necessarily contiguous)
Best Answer (HR Friendly)
“If every number is non-negative, I use a sliding window that expands and shrinks based on whether the running sum is below or above the target, which runs in a single pass. If negative numbers are possible, sliding the window is not reliable anymore, so instead I track running sums in a hash map and look for a previous sum that differs from the current one by exactly the target.”
Code Example
def subarray_sum_nonneg(nums, target):
left = 0
running_sum = 0
for right, value in enumerate(nums):
running_sum += value
while running_sum > target and left <= right:
running_sum -= nums[left]
left += 1
if running_sum == target:
return (left, right)
return None
def subarray_sum_general(nums, target):
prefix_index = {0: -1}
running_sum = 0
for i, value in enumerate(nums):
running_sum += value
if (running_sum - target) in prefix_index:
start = prefix_index[running_sum - target] + 1
return (start, i)
if running_sum not in prefix_index:
prefix_index[running_sum] = i
return NoneFollow-up Questions
- How would you count the total number of subarrays that sum to target, rather than finding just one?
- How would you find the longest subarray summing to target instead of any matching one?
- Why does seeding the prefix-sum map with {0: -1} matter for correctness?
- How would this change if you needed the smallest subarray with sum at least target?
MCQ Practice
1. The sliding-window technique for subarray sum requires which condition to be correct?
Non-negative values guarantee that shrinking the window from the left can only decrease or keep the running sum the same, which is required for the two-pointer logic to be valid.
2. What is the purpose of seeding the prefix-sum hash map with {0: -1}?
Without a prefix sum of 0 mapped to index -1, a subarray starting at index 0 whose sum equals target would never be detected.
3. What is the time complexity of the prefix-sum hash map approach for subarray sum with possible negative numbers?
A single pass computing running sums and hash map lookups/insertions, each O(1) on average, gives O(n) overall.
Flash Cards
When is the sliding-window approach valid for subarray sum? — Only when all array values are non-negative, so shrinking the window is monotonic.
What technique handles subarray sum when negative numbers are allowed? — A running prefix sum combined with a hash map of {prefix sum: index}.
Why seed the prefix-sum map with {0: -1}? — To correctly detect subarrays that start from index 0.
What is the time complexity of both subarray-sum approaches? — O(n), a single linear pass over the array.