Sliding window and two pointers: problem patterns with examples
Sliding window and two pointers explained with 6 tested Python problems, when each pattern applies, and how both cut O(n^2) brute force to O(n).
The sliding window technique keeps a contiguous range of an array or string and updates its result as the range moves, instead of recomputing it from scratch. The two pointer technique moves two indices through the data, either towards each other from opposite ends of a sorted array or in the same direction. Both usually turn an O(n^2) brute force into an O(n) pass.
What is the sliding window technique?
A sliding window is a constant-size subarray that moves from left to right through an array, and at each position some information about the elements inside it is computed. That definition comes from the Competitive Programmer's Handbook by Antti Laaksonen. The saving comes from the update. When the window moves one step, one element enters and one leaves, so the answer changes by a small amount instead of being rebuilt.
The first classic problem is the largest sum of k consecutive items. The code keeps a running window sum, adds the new item and subtracts the one that left.
def max_sum_window(a, k):
"""Largest sum of k consecutive items (fixed window)."""
window = sum(a[:k])
best = window
for right in range(k, len(a)):
window += a[right] - a[right - k] # add the new item, drop the old one
best = max(best, window)
return best
print(max_sum_window([2, 1, 5, 1, 3, 2], 3))9The window sums for [2, 1, 5, 1, 3, 2] with k = 3 are 8, 7, 9 and 6, so the best is 9. Brute force re-adds k items for every window. For 1,000 items and k = 100 that is 901 windows and 90,100 element reads. The sliding window reads 100 items once and then two per move, 1,900 reads in total.
How does a variable-size sliding window work?
A variable window grows and shrinks, with both ends only ever moving right. The USACO Guide, quoting the Handbook, says the subarray need not have constant size as long as both endpoints only move to the right. The right end expands the window until a condition breaks or is met. The left end then advances to restore the condition. Since each pointer moves at most n times, the whole scan is O(n).
Two standard problems follow this shape. The first asks for the longest substring without a repeated character. The second asks for the shortest subarray of positive numbers whose sum reaches a target.
def longest_unique(s):
"""Length of the longest substring without a repeated character (variable window)."""
last_seen, left, best = {}, 0, 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # shrink past the earlier copy
last_seen[ch] = right
best = max(best, right - left + 1)
return best
def shortest_at_least(a, target):
"""Length of the shortest subarray with sum >= target (all items positive)."""
left, total, best = 0, 0, float("inf")
for right, x in enumerate(a):
total += x
while total >= target:
best = min(best, right - left + 1)
total -= a[left]
left += 1
return 0 if best == float("inf") else best
print(longest_unique("abcabcbb"), longest_unique("pwwkew"))
print(shortest_at_least([2, 3, 1, 2, 4, 3], 7))3 3
2For "abcabcbb" the longest unique run is "abc", length 3. For "pwwkew" it is "wke", also 3. In [2, 3, 1, 2, 4, 3] with target 7, the shortest qualifying window is 4 followed by 3, length 2.
What is the two pointer technique?
The two pointers method iterates two pointers across an array to track indices satisfying some condition. The USACO Guide describes two common variations: pointers that start at different ends and move towards each other, and pointers that move in the same direction at different speeds, a variation it calls the sliding window algorithm. The Handbook describes the method as two pointers that can each move in one direction only, which is what keeps the algorithm efficient.
The reasoning behind both variations is the same. Every pointer move discards candidates that can no longer be the answer, so no position is revisited, and each pointer moves at most once per array position. The Handbook phrases it for the subarray-sum problem: the right pointer moves a total of O(n) steps because it only moves right.
How do opposite-end pointers work?
Opposite-end pointers start at the first and last positions of a sorted array and move inwards, using the order to decide which end to move. The USACO Guide explains why this works for pair sum: moving the left pointer right never decreases the sum, and moving the right pointer left never increases it. If the current sum is too small, the left pointer moves. If it is too large, the right pointer moves.
Two problems show the pattern. The first finds two values in a sorted list that add up to a target. The second, most water, takes bar heights and finds the pair of bars that holds the largest area, width times the shorter height. Moving the taller bar inward can never improve the area, because the width shrinks while the shorter bar still caps the height, so the shorter bar is the one to move.
def pair_with_sum(sorted_a, target):
"""Opposite ends: indices of two values summing to target in a sorted list."""
left, right = 0, len(sorted_a) - 1
while left < right:
s = sorted_a[left] + sorted_a[right]
if s == target:
return left, right
if s < target:
left += 1
else:
right -= 1
return None
print(pair_with_sum([2, 3, 5, 8, 11, 15], 16))(2, 4)The second problem uses the same two pointers with a different rule for which one moves.
def most_water(heights):
"""Opposite ends: largest area between two bars; move the shorter bar inward."""
left, right, best = 0, len(heights) - 1, 0
while left < right:
best = max(best, (right - left) * min(heights[left], heights[right]))
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return best
print(most_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))49In [2, 3, 5, 8, 11, 15] with target 16, the pointers start at 2 and 15 (sum 17, too large), move to 2 and 11 (13, too small), then 3 and 11 (14), then 5 and 11, which is 16. Those are indices 2 and 4. A brute-force pair search over 1,000 items examines 499,500 pairs, while two pointers need at most 999 steps. The sorting step costs O(n log n), so the Handbook gives the whole 2SUM solution as O(n log n), and notes that the same idea solves 3SUM in O(n^2).
How do same-direction pointers work?
Same-direction pointers move through the data together at different speeds, usually one reading and one writing. Removing duplicates from a sorted list in place is the standard case. The read pointer scans every item. The write pointer marks where the next unique item goes, so the front of the list fills with unique values while the read pointer runs ahead.
def dedupe_in_place(a):
"""Same direction: a read pointer scans, a write pointer keeps the unique values."""
write = 0
for read in range(len(a)):
if read == 0 or a[read] != a[write - 1]:
a[write] = a[read]
write += 1
return write
a = [1, 1, 2, 2, 2, 3, 5, 5]
n = dedupe_in_place(a)
print(n, a[:n])4 [1, 2, 3, 5]The function returns the new length, 4, and the first four slots hold 1, 2, 3 and 5. It makes one pass and uses no extra list, so it is O(n) time and O(1) extra space.
What is the difference between sliding window and two pointers?
A sliding window is a special case of two pointers in which the two pointers bound a contiguous range whose summary is maintained as it moves. The USACO Guide states the relationship directly: the sliding window is the variation where the pointers move in the same direction to maintain a range. Not every two-pointer problem has a window. Pair sum on a sorted array has pointers but no window state to maintain.
| Pattern | How the pointers move | What it needs | Typical problems | Time |
|---|---|---|---|---|
| Fixed window | Both move right, a fixed gap apart | An update that adds one item and removes one | Largest sum of k items | O(n) |
| Variable window | Both move right, independently | A condition that advancing the left end restores | Longest unique substring, shortest subarray reaching a sum | O(n) |
| Opposite ends | Towards each other | Sorted data, or an argument for which end to move | Pair sum, most water | O(n), plus O(n log n) for sorting |
| Read and write | Same direction, different speeds | Data grouped so duplicates sit together | Remove duplicates in place | O(n) |
How do you recognise which pattern a problem needs?
Look at the shape of the answer first. These rules of thumb cover most cases:
- A contiguous subarray or substring that is longest, shortest, largest or smallest under some condition points to a window.
- A target pair or triple in sorted data points to opposite-end pointers.
- An in-place rewrite of an array points to read and write pointers.
- A brute force that examines all pairs or all subarrays, and so costs O(n^2), is the usual sign that one of these patterns can replace it.
A fixed window is the right choice when the window length is given. A variable window fits when the length is what the problem asks for. Broader data structure questions are covered in Cracking Data Structure and Algorithm Interviews.
What are the limits and common mistakes?
The shrinking window depends on a monotone condition. For the shortest-subarray problem, the condition holds only because every number is positive: adding items can never lower the sum. With a negative value the method can give wrong answers.
a = [1, -1, 5]
print(shortest_at_least(a, 5)) # window answer
print(min(j - i + 1 for i in range(3) for j in range(i, 3) if sum(a[i:j+1]) >= 5)) # brute force3
1The window reports 3, but the single item 5 already reaches the target, so the true answer is 1. This sample reuses shortest_at_least from the earlier block. When values can be negative, a different technique is needed.
Other limits apply too. Opposite-end pair search needs sorted input, and sorting costs O(n log n), as covered in sorting algorithms explained. A running sum cannot give the maximum or minimum of a window. The Handbook handles the sliding window minimum with a queue that keeps increasing elements, and Python's collections.deque supports appends and pops at both ends in O(1), which suits that job. Common slips include moving the wrong pointer, using if where the shrinking step needs while, and forgetting to update the answer before shrinking.
Where do these patterns fit for working engineers?
Sliding windows and pointer scans are standard tools for processing sequences of data. The Forward Deployed Engineer (FDE) Cohort is a Leap by Masai programme for engineers with hands-on technical experience, run as an in-person start in Goa, an online build phase and an in-person hackathon in Bangalore for qualifying participants, covering production Python, APIs, cloud deployment, LLMs, retrieval, agents, security and client engagement.
Its content includes production-ready Python and data pipelines, APIs and access. Details are on the Forward Deployed Engineer cohort page.
Frequently asked questions
What is the sliding window technique?
The sliding window technique maintains a contiguous range of an array or string, a window, and updates a running result as the window moves, adding the entering item and removing the leaving one. This avoids recomputing the result for every window and typically brings an O(n times k) or O(n^2) brute force down to O(n).
When should you use two pointers?
Use two pointers when the data is sorted and the task involves a pair or triple, when an array must be rewritten in place, or when a condition on a contiguous range can be fixed by moving one end. The common signal is a brute force over all pairs that costs O(n^2), where each pointer move can discard candidates.
What is the difference between sliding window and two pointers?
Two pointers is the broader idea of moving two indices through data. A sliding window is the variation where both pointers move in the same direction and bound a contiguous range whose summary is updated as it moves. Pair sum on a sorted array uses two pointers but has no window.
Does the sliding window technique work with negative numbers?
For some problems, such as the largest sum of k consecutive items, it does. For shrinking-window problems on sums, such as the shortest subarray reaching a target, it does not, because the shrinking step relies on the sum never decreasing as items are added. On [1, -1, 5] with target 5 the window answer is 3 against a true answer of 1.
What is the time complexity of the two pointer technique?
It is O(n) for the pointer scan, because each pointer moves at most n times and never goes back. When the data must first be sorted, as for pair sum on unsorted input, the total becomes O(n log n). The Competitive Programmer's Handbook gives the 2SUM solution as O(n log n) and 3SUM as O(n^2).
How do you find the maximum of every sliding window?
A running sum cannot do it, because removing the leaving item does not reveal the new maximum. The Competitive Programmer's Handbook uses a queue of increasing elements for the sliding window minimum, and a mirrored queue gives the maximum. Each element enters and leaves once, so the whole scan stays O(n).
Next step
Solve each of the six problems again without looking, then write a brute-force version and compare the answers on random inputs. If production Python is the next skill to strengthen, see the Forward Deployed Engineer cohort from Leap by Masai. Readers wondering what to call themselves once these skills are in place can read coder vs programmer vs developer vs software engineer.