Two indices walking through an array, either converging from the ends or sliding forward together. These techniques turn O(n²) brute-force into O(n) elegance.
🟡 IntermediateTwo pointers is a technique where you use two index variables to traverse a data structure — usually an array or string — in a way that avoids checking every possible pair. Instead of the O(n²) nested loop approach ("for each element, check every other element"), the pointers move strategically so each element is visited a small constant number of times.
The technique isn't a specific algorithm — it's more of a pattern that shows up across dozens of different problems. What unites them is the core insight: by being clever about which direction to move each pointer, you can skip work that wouldn't lead to a better answer.
The "sliding window" name has roots in networking. TCP (Transmission Control Protocol, the protocol that makes reliable internet communication possible) uses a sliding window for flow control — a range of sequence numbers representing packets that can be "in flight." The sender's window slides forward as acknowledgments arrive. The algorithmic technique borrows both the name and the mental model: a window of elements that slides through the data.
The sliding window variant deserves its own name because it's that common. The idea: maintain a window [left, right] that expands by advancing right and contracts by advancing left. You grow the window when you need more elements to satisfy a condition, and shrink it when the window violates a constraint.
There's a related technique where two pointers move at different speeds through a linked list. The slow pointer advances one node at a time; the fast pointer advances two nodes. If there's a cycle, the fast pointer laps the slow pointer and they meet. If there's no cycle, the fast pointer reaches the end. This is Floyd's Cycle Detection Algorithm (also called the tortoise and hare algorithm), published by Robert Floyd in 1967. It also finds the middle of a linked list in one pass — when fast reaches the end, slow is at the midpoint.
Start with left = 0, right = n-1. Check some condition involving arr[left] and arr[right]. Based on the result, move one pointer inward:
This works because the array is sorted. Moving left can only increase the left value. Moving right can only decrease the right value. You never need to revisit a discarded pointer position, so the total work is O(n).
Why can't we skip solutions? Consider two sum on a sorted array. If arr[left] + arr[right] < target, every pair (left, right'), where right' < right, also sums to less than the target (since arr[right'] ≤ arr[right]). So moving left forward is safe — we haven't skipped any valid answer. A symmetric argument works for the too-large case.
For "max sum of subarray of size k": start with a window covering the first k elements. Compute its sum. Slide the window one step right — add the new element entering from the right edge, subtract the element leaving from the left edge. Each slide is O(1) work, so the whole thing is O(n).
The fixed window approach works whenever the window size is given (or can be determined) ahead of time. You're essentially computing a rolling aggregate — sum, average, max, min, or count.
For "smallest subarray with sum ≥ target": expand right until the window satisfies the condition (sum ≥ target). Then shrink from left while the condition still holds, recording the minimum length along the way. When the condition breaks, expand right again.
The key insight people miss: left never moves backward, and right never moves backward. Each pointer traverses the array at most once. Even though there's an inner while loop for shrinking, the total number of left-advances across the entire algorithm is at most n. So the total work is O(n), not O(n²).
The variable window is trickier because you need to decide when to expand and when to contract. The general template:
How do you know whether to use converging or sliding?
Toggle between Two Pointers mode (finding a pair that sums to a target) and Sliding Window mode (finding the maximum sum subarray of a given size).
while loop, not an if. The window might need to shrink by multiple elements before the constraint is restored. Writing if only shrinks once and can leave the window in an invalid state.
right - left + 1 elements, not right - left. This off-by-one error is incredibly common and leads to answers that are consistently off by 1.
Both techniques achieve O(n) by ensuring each pointer only moves forward — never backward. You're visiting each element at most twice (once by each pointer).
| Pattern | Time | Space | When To Use |
|---|---|---|---|
| Two Sum (sorted) | O(n) | O(1) | Pair finding on sorted data |
| Three Sum | O(n²) | O(1) | Sort + nested two pointers |
| Fixed-size window | O(n) | O(1) | Max/min sum of size k |
| Variable-size window | O(n) | O(1)* | Smallest subarray with sum ≥ S |
| Window + hash map | O(n) | O(k) | Distinct chars, frequency constraints |
| Remove duplicates | O(n) | O(1) | In-place array manipulation |
| Fast/slow pointers | O(n) | O(1) | Cycle detection, linked list middle |
* Some sliding window problems need a hash map or counter inside the window, adding O(k) space where k is the alphabet/value size.
def two_sum_sorted(numbers, target):
"""Find two numbers in a sorted array that sum to target.
Returns 1-indexed positions. O(n) time, O(1) space."""
left, right = 0, len(numbers) - 1
while left < right:
current = numbers[left] + numbers[right]
if current == target:
return [left + 1, right + 1] # 1-indexed result
elif current < target:
left += 1 # Sum too small — need a bigger left value
else:
right -= 1 # Sum too large — need a smaller right value
return [] # No pair found
def max_area(height):
"""Find two lines that form a container holding the most water.
The greedy insight: always move the shorter side inward.
Moving the taller side can only decrease width without
increasing the limiting height, so it can never help."""
left, right = 0, len(height) - 1
best = 0
while left < right:
# Area = width × min(left_height, right_height)
w = right - left
h = min(height[left], height[right])
best = max(best, w * h)
# Move the shorter side — it's the bottleneck
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
def max_sum_subarray(arr, k):
"""Find the maximum sum of any contiguous subarray of size k.
O(n) time — each element is added once and removed once."""
# Build the first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide: add the new right element, drop the old left element
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
def min_subarray_len(target, nums):
"""Find the shortest subarray with sum >= target.
Variable-size sliding window. O(n) time."""
left = 0
current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right] # Expand window
# Shrink from left while condition holds
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1 # Contract window
return min_len if min_len != float('inf') else 0
def length_of_longest_substring(s):
"""Find the longest substring with all unique characters.
Window tracks the current duplicate-free range.
Hash map remembers each character's most recent index."""
seen = {} # char → most recent index
left = 0
max_len = 0
for right, char in enumerate(s):
# If char was seen and is inside our current window, shrink
if char in seen and seen[char] >= left:
left = seen[char] + 1 # Jump left past the duplicate
seen[char] = right
max_len = max(max_len, right - left + 1)
return max_len
function lengthOfLongestSubstring(s) {
const seen = new Map();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
// Shrink window if duplicate found inside it
if (seen.has(char) && seen.get(char) >= left) {
left = seen.get(char) + 1;
}
seen.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
def has_cycle(head):
"""Detect if a linked list has a cycle using Floyd's algorithm.
Slow pointer moves 1 step, fast moves 2 steps.
If they meet, there's a cycle. O(n) time, O(1) space."""
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow is fast:
return True # They met — cycle exists
return False # fast hit the end — no cycle
def find_cycle_start(head):
"""Find the node where the cycle begins.
After detection, reset one pointer to head and advance both
at speed 1. They meet at the cycle start. (Math: look up
Floyd's algorithm proof for why this works.)"""
slow = fast = head
# Phase 1: detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # No cycle
# Phase 2: find entry point
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next # Both move at speed 1 now
return slow
APIs often limit requests to "at most N requests per T seconds." This is a sliding window problem. You maintain a window of timestamps for recent requests and check whether adding a new one would exceed the limit.
from collections import deque
import time
class SlidingWindowRateLimiter:
"""Allow at most max_requests in window_seconds.
Uses a deque (double-ended queue) as a sliding window
of request timestamps."""
def __init__(self, max_requests, window_seconds):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.timestamps = deque() # Sorted by time (oldest first)
def allow_request(self):
now = time.time()
# Shrink window: remove timestamps outside the window
# This is the "slide left" operation
while self.timestamps and now - self.timestamps[0] > self.window_seconds:
self.timestamps.popleft()
if len(self.timestamps) < self.max_requests:
self.timestamps.append(now) # Expand window: add new request
return True
return False # Rate limited
# Usage: 5 requests per 10 seconds
limiter = SlidingWindowRateLimiter(max_requests=5, window_seconds=10)
for i in range(8):
allowed = limiter.allow_request()
print(f"Request {i+1}: {'✓ Allowed' if allowed else '✗ Rate limited'}")
# First 5 pass, next 3 are blocked (until 10 seconds elapse)
The deque acts as the sliding window. Old timestamps "fall off" the left as they age out of the window. New timestamps enter from the right. At any moment, the deque length tells you how many requests are in the current window. This is exactly the same pattern as a variable-size sliding window on an array — just applied to timestamps instead of indices.
while the window violates a constraint, increment left. Don't overthink — the "while" loop handles it. If you're writing "if" instead of "while" for the shrink step, you probably have a bug.