01: Introduction
In this guide, you’ll learn how the sliding window technique works step by step, when it breaks down, what the alternative is, and how to write clean Python code for it — all with a visual walkthrough.
02: Problem Statement
Given an array of integers and a target sum, find a contiguous subarray whose elements add up to exactly the target. Return the start and end indices if found, otherwise return -1.
Example 1
Input: arr = [1, 4, 20, 3, 10, 5], target = 33
Output: Subarray found from index 2 to 4 → [20, 3, 10]
Sum = 20 + 3 + 10 = 33 ✓Example 2
Input: arr = [1, 2, 3, 7, 5], target = 12
Output: Subarray found from index 2 to 4 → [3, 7, 5]
Sum = 3 + 7 + 5 = 12 ✓03: Input / Output & Constraints
Input Format
- An array arr of n integers
- A single integer target (the desired sum)
Output Format
- Starting and ending index of the subarray (0-based)
- Or -1 if no such subarray exists
The classic sliding window approach assumes all elements are positive (≥ 1). This is not just a small detail — it’s the entire reason the algorithm works. With positive numbers, adding an element always increases the sum and removing one always decreases it. This predictability is what lets the window expand and shrink logically.
Standard constraints:
- 1 ≤ n ≤ 10⁷
- 1 ≤ arr[i] ≤ 10⁵ (for basic sliding window version)
- 1 ≤ target ≤ 10¹²
04: Naive Approach — Brute Force O(n²)
The obvious approach: check every possible subarray. For each starting index i, extend to every ending index j and calculate the sum.
def subarray_brute(arr, target):
n = len(arr)
for i in range(n):
current_sum = 0
for j in range(i, n):
current_sum += arr[j]
if current_sum == target:
return i, j # found!
if current_sum > target:
break # no need to go further
return -1, -1Time: O(n²) — For a 10 million element array, that’s 100 trillion operations. Completely impractical. Space: O(1).
05: Sliding Window Approach — O(n)
Instead of recalculating sums from scratch, we use a window that slides across the array. Think of it like a rubber band — you stretch it right to add elements, and shrink it from the left when the sum gets too big.
Core Idea
- Start with both left and right pointers at index 0
- Expand the window right — add arr[right] to current sum
- Shrink the window left — subtract arr[left] when sum exceeds target
- Stop when sum equals target or right reaches the end
Each element is added at most once and removed at most once. So even though we have two nested actions (expand + shrink), the total work done is O(n). This is the beauty of sliding window.
06: Critical Concept — Why Positive Numbers Matter
The Monotonic Property
Sliding window works because with all positive integers:
- Adding an element always increases the sum → safe to expand right
- Removing an element always decreases the sum → safe to shrink left
- The sum is monotonically controllable — we always know which direction to move
Without this property, you can’t know whether to expand or shrink. A negative number could make the sum jump in an unexpected direction, and the window logic breaks completely.
07: When Sliding Window Fails
Try this array: [2, -1, 2], target = 3
Window starts: [2] → sum = 2, too small, expand
Window now: [2, -1] → sum = 1, still small, expand
Window now: [2, -1, 2] → sum = 3, MATCH? Yes!
But wait — what if target = 2?
Window: [2] → sum = 2, MATCH... but we'd miss it
Window: [2, -1, 2] → sum = 3, too big, shrink left
Window: [-1, 2] → sum = 1, too small, expand again...
The shrink/expand logic fails with negatives!Arrays with negative numbers or zeros break the sliding window. Use the Prefix Sum + HashMap approach instead — it handles all cases correctly.
08: Alternative — Prefix Sum + Hashing
For arrays with negative numbers, use a HashMap to track prefix sums. The idea: if prefix_sum[j] – prefix_sum[i] = target, then elements from index i+1 to j form the target subarray.
def subarray_prefix(arr, target):
prefix_map = {0: -1} # maps prefix_sum → index
current_sum = 0
for i, num in enumerate(arr):
current_sum += num
# Check if (current_sum - target) was seen before
if (current_sum - target) in prefix_map:
start = prefix_map[current_sum - target] + 1
print(f"Subarray found: index {start} to {i}")
return start, i
prefix_map[current_sum] = i
return -1, -1| Aspect | Sliding Window | Prefix Sum |
|---|---|---|
| Works on negatives? | ❌ No | ✅ Yes |
| Time Complexity | O(n) | O(n) |
| Space Complexity | O(1) | O(n) |
| Simplicity | Simpler | More complex |
09: Interactive Sliding Window Visualizer
Click Next Step to walk through the sliding window on [1, 2, 3, 7, 5] with target 12.
10: Flowchart
11: Pseudocode
FUNCTION findSubarrayWithSum(arr, target):
left ← 0
right ← 0
sum ← 0
WHILE right < length(arr):
sum ← sum + arr[right] // expand window
WHILE sum > target AND left < right:
sum ← sum - arr[left] // shrink window
left ← left + 1
IF sum == target:
RETURN (left, right) // found!
right ← right + 1
RETURN (-1, -1) // not found12: Python Program
def subarray_sliding_window(arr, target):
"""
Find subarray with given sum using sliding window.
Works ONLY for arrays with positive integers.
Time: O(n), Space: O(1)
"""
n = len(arr)
left = 0
current_sum = 0
for right in range(n):
# Expand window by adding right element
current_sum += arr[right]
# Shrink window from left while sum exceeds target
while current_sum > target and left < right:
current_sum -= arr[left]
left += 1
# Check if we found our target
if current_sum == target:
print(f"Subarray found: index {left} to {right}")
print(f"Subarray: {arr[left:right+1]}")
return left, right
print("No subarray found with given sum")
return -1, -1
# ── Driver Code ──
if __name__ == "__main__":
arr = [1, 2, 3, 7, 5]
target = 12
subarray_sliding_window(arr, target)
# Output: Subarray found: index 2 to 4 → [3, 7, 5]Prefix Sum Solution (Handles Negatives)
def subarray_prefix_sum(arr, target):
"""
Find subarray with given sum using prefix sum + hashing.
Works for ANY array including negative numbers.
Time: O(n), Space: O(n)
"""
prefix_map = {0: -1} # prefix_sum → index mapping
current_sum = 0
for i, num in enumerate(arr):
current_sum += num # accumulate prefix sum
# If (current_sum - target) was seen before → subarray exists
needed = current_sum - target
if needed in prefix_map:
start = prefix_map[needed] + 1
print(f"Subarray found: index {start} to {i}")
print(f"Subarray: {arr[start:i+1]}")
return start, i
# Store this prefix sum for future lookups
prefix_map[current_sum] = i
print("No subarray found")
return -1, -113: Dry Run — Step by Step
Array: [1, 2, 3, 7, 5] | Target: 12
| Right | Left | Sum | Action | Status |
|---|---|---|---|---|
| 0 | 0 | 1 | Add arr[0]=1 | 1 < 12, expand |
| 1 | 0 | 3 | Add arr[1]=2 | 3 < 12, expand |
| 2 | 0 | 6 | Add arr[2]=3 | 6 < 12, expand |
| 3 | 0 | 13 | Add arr[3]=7 | 13 > 12, shrink |
| 3 | 1 | 12 | Remove arr[0]=1 | 12 == 12 ✓ |
| 3 | 1 | 12 | — | 🎯 FOUND! [1..3] = [2,3,7] |
Note: The problem may have multiple valid answers. Sliding window returns the first one found.
14: Time & Space Complexity
| Method | Time Complexity | Space Complexity | Handles Negatives |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | ✅ Yes |
| Sliding Window | O(n) | O(1) | ❌ No |
| Prefix Sum + HashMap | O(n) | O(n) | ✅ Yes |
15: Test Cases
16: Edge Cases to Handle
Empty Array
If len(arr) == 0, return -1 immediately. The loop never runs so this is handled automatically, but add an explicit check for clarity.
Negative Numbers in Array
Sliding window will give wrong results. Use the prefix sum approach instead. Always ask your interviewer: “Can elements be negative?”
Multiple Valid Subarrays
The sliding window returns the first match. If you need all subarrays, you’ll need a modified approach that continues after finding one match.
Target = 0
With positive integers, no subarray sums to 0 (unless the array has 0s, which breaks the positive assumption). Handle this as a special case.
17: Common Interview Questions
- Q1. Find the maximum length subarray with sum equal to k (use prefix sum).
- Q2. Count the number of subarrays with sum equal to k (classic LeetCode #560).
- Q3. Find the smallest subarray with sum ≥ target (minimum window sum).
- Q4. Find all subarrays with sum equal to a given value.
- Q5. Given a binary array, find the maximum length subarray with equal 0s and 1s.
- Q6. Why does sliding window fail with negative numbers? Explain with an example.
18: Real World Applications
Financial Tracking
Find the exact period where expenses matched a budget — salary analysis, spending windows.
Resource Allocation
Find a time window where CPU or memory usage matches a threshold for load balancing.
Network Monitoring
Detect a burst of packets with total size equal to a buffer limit in streaming data.
Genomics
Find a contiguous gene segment with a specific expression level sum in DNA arrays.
Logistics
Find consecutive days where shipment weights match a truck’s carry capacity exactly.
Stock Analysis
Identify periods where daily stock gains sum to a specific profit target.
19: Common Mistakes Beginners Make
Using sliding window on arrays with negative numbersThis is the biggest mistake. Sliding window only works for positive integers. Always check for negatives first.
Forgetting to shrink the windowJust expanding right isn’t enough. When sum exceeds target, you must subtract from the left until it’s back in range.
Wrong shrink conditionUsing left <= right instead of left < right — the window must have at least one element. Check your loop boundary carefully.
Off-by-one errors in result indicesWhen returning the subarray, use arr[left:right+1] — Python’s slice is exclusive on the right end.
Not handling the case where sum never equals targetAlways add a return statement for the “not found” case. Don’t assume the subarray always exists.
Conclusion
The Sliding Window algorithm is one of the cleanest examples of how the right data structure thinking eliminates redundant work. By maintaining a live window and adjusting it dynamically, we reduce an O(n²) problem to O(n) — a massive win for large inputs.
Remember the golden rule: positive integers → sliding window. Negatives → prefix sum + HashMap. Master both, and you’ll handle almost every subarray sum variant thrown at you in interviews.
21: FAQ
pro.technaga.com
If you want more, follow
If you are more into programming, follow
If you want to see this in a good, stylish way, click thissubarray-given-sum-sliding-window