The two data structures that appear in 70% of interview problems. Two-pointer and sliding window patterns — the techniques that take O(n²) string solutions to O(n) in a single pass.
Know how to implement two-pointer for palindrome and pair-sum problems. Understand why nested loops are O(n²) and recognise when they can be replaced.
Apply sliding window to substring problems without prompting. Know when to sort first vs when sorting changes the problem. Handle edge cases: empty array, single element, duplicates.
Recognise two-pointer and sliding window in disguised forms: rate limiting, stream deduplication, time-series windowing. Know the preconditions that make each pattern applicable.
The two data structures that appear in 70% of interview problems. Two-pointer and sliding window patterns — the techniques that take O(n²) string solutions to O(n) in a single pass.
Crosby & Wallach publish "Denial of Service via Algorithmic Complexity Attacks" — theoretical hash collision attack
Attack demonstrated practically against PHP, Java, and Python web frameworks at CCC conference
WARNINGCVE-2012-1150 filed — Python dict confirmed vulnerable to hash flooding DoS
CRITICALPython 3.3 releases with PYTHONHASHSEED: random per-process salt making crafted collisions impossible
Django and Flask add POST field count limits (default 1,000) as defence-in-depth
The question this raises
If the data structure your language uses for everything can be weaponised by controlling input — what does that tell you about how hash tables really work?
You have a string of 10,000 characters and want to check if it is a palindrome (reads the same forwards and backwards). What is the fewest number of character comparisons you could possibly need?
Lesson outline
The two people walking toward each other
A sorted row of 10 lockers. Two people stand at opposite ends. The left person walks right, the right person walks left. They check their lockers, compare, and communicate — "too high, move me left." They meet in the middle. One pass. That's two-pointer. Instead of every person checking every locker (n²), they work together and cover the whole row in n steps.
Two-Pointer Pattern
let left = 0, right = arr.length - 1;
while (left < right) { /* compare and move */ }Use for: Reach for this when: the array is sorted and you need pairs/triplets that satisfy a condition, or when you need to check if a string is a palindrome
The key insight: sorted order lets you make decisions. In a sorted array, if the sum of two numbers is too big, the right pointer must move left (to a smaller number). If the sum is too small, the left pointer must move right (to a bigger number). No guessing — every comparison tells you exactly which pointer to move.
How this concept changes your thinking
Find two numbers in a sorted array that sum to 100
“I would check every possible pair — for each number, scan the rest of the array. That's n*(n-1)/2 pairs to check.”
“The array is sorted. I put one pointer at the smallest number, one at the largest. If their sum is 100, done. If too big, move the right pointer left. If too small, move the left pointer right. O(n) instead of O(n²).”
Check if a string is a palindrome
“I would build a reversed copy and compare. That's O(n) space for the reversed string.”
“Two pointers: left starts at index 0, right starts at the last character. Compare. If they match, move both inward. If they don't match, it's not a palindrome. O(1) extra space.”
Find the longest substring without repeating characters
“I would check every possible substring — for each start position, scan forward until I find a repeat. O(n²).”
“Sliding window: expand right until I find a repeat, then shrink from the left until the repeat is gone. One pass. O(n).”
Two-pointer palindrome check on "racecar"
01
We have the word "racecar" (7 letters). We want to check if it reads the same forwards and backwards.
02
Set up two pointers: left points to "r" (position 0), right points to "r" (position 6). They start at opposite ends.
03
Step 1 — compare: "r" and "r" match. Move both pointers inward: left moves to position 1, right moves to position 5.
04
Step 2 — compare: position 1 is "a", position 5 is "a". They match. Move both inward: left to 2, right to 4.
05
Step 3 — compare: position 2 is "c", position 4 is "c". They match. Move both inward: left to 3, right to 3.
06
Step 4 — pointers have met: left equals right — we are at the middle character. No more pairs to check.
07
Result: every mirror pair matched — "racecar" is a palindrome. We checked 3 pairs instead of all 7 characters twice. left and right are the variable names in the actual code.
We have the word "racecar" (7 letters). We want to check if it reads the same forwards and backwards.
Set up two pointers: left points to "r" (position 0), right points to "r" (position 6). They start at opposite ends.
Step 1 — compare: "r" and "r" match. Move both pointers inward: left moves to position 1, right moves to position 5.
Step 2 — compare: position 1 is "a", position 5 is "a". They match. Move both inward: left to 2, right to 4.
Step 3 — compare: position 2 is "c", position 4 is "c". They match. Move both inward: left to 3, right to 3.
Step 4 — pointers have met: left equals right — we are at the middle character. No more pairs to check.
Result: every mirror pair matched — "racecar" is a palindrome. We checked 3 pairs instead of all 7 characters twice. left and right are the variable names in the actual code.
The two-pointer palindrome check — exactly as described above, in code:
1function isPalindrome(s) {2let left = 0;left starts at the first character — position 0.3let right = s.length - 1;right starts at the LAST character — s.length - 1, not s.length.4while (left < right) {We stop when left meets or passes right — the middle has been reached. This is the termination condition beginners miss.6if (s[left] !== s[right]) {If any mirror pair does not match, it cannot be a palindrome — return false immediately.7return false;8}Move left inward (right) and right inward (left) simultaneously — this is the "two pointers walking toward each other" in code.9left++;10right--;11}12return true;14}15// isPalindrome("racecar") => true17// isPalindrome("hello") => false
When asked to find a pair of numbers that sum to a target in a sorted array, most people use two nested loops — quadratic time.
O(n²) nested loops vs O(n) two-pointer
// Naive — checks every pair
// O(n²) time, fails on large arrays
function twoSumSorted_slow(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
return [i, j];
}
}
}
return null;
}// Two-pointer — one pass
// O(n) time, O(1) space
function twoSumSorted(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right--;
}
return null;
}The left version tries every pair: n items means roughly n²/2 comparisons. At 10,000 items: 50 million comparisons. The right version uses the sorted property: if the sum is too small, move left right (get a bigger number); if too large, move right left (get a smaller number). Every step eliminates one candidate. O(n) total. The array must be sorted — that is the precondition that makes this possible.
Two-pointer or sliding window?
| Operation | What happens | Speed |
|---|---|---|
| Array access by index (arr[7]) | Direct memory address calculation — no searching | Instant (O(1)) |
| Two-pointer pass over sorted array | Both pointers together visit each element once | Fast (O(n)) |
| Sliding window over string | Right pointer advances, left catches up — each element visited at most twice | Fast (O(n)) |
| Nested loop over array | Each element compared with every other element | Slow (O(n²)) |
| Sorting the array first, then two-pointer | Sort costs O(n log n); two-pointer costs O(n); total O(n log n) | Acceptable (O(n log n)) |
Two-pointer technique
📖 What the exam expects
Two-pointer uses two index variables that start at different positions and move toward each other (or in the same direction at different speeds). It reduces O(n²) brute-force pair-checking to O(n) by using the sorted property to eliminate candidates.
Toggle between what certifications teach and what production actually requires
Two-pointer appears in roughly 40% of LeetCode medium problems: palindromes, pair sums, container with most water, remove duplicates from sorted array. Sliding window appears in substring problems: longest substring without repeating characters, minimum window substring, maximum sum subarray of size k.
Common questions:
Strong answer: identifies the pattern name before starting / states the pointer movement logic before writing a line / handles edge cases out loud: empty string, single character, all-same characters / explains WHY each pointer moves in each direction
Red flags: reaches for nested loops immediately / cannot articulate WHEN to use two-pointer vs sliding window / does not consider whether the array needs to be sorted first / misses edge cases: empty input, single element, all duplicates
💡 Analogy
An array is a row of numbered lockers. Locker 7 is always the 7th from the left — you walk directly there, no searching. Access is instant because the position IS the address. The two-pointer technique is two people standing at opposite ends of the row, walking toward each other and comparing lockers as they go. One pass, done. The sliding window is like a magnifying glass that slides along the row — you grow it right when you need more, shrink it left when you have too much.
⚡ Core Idea
Arrays give random access in O(1) because index arithmetic converts a position to a memory address directly. Two-pointer works because it reduces two nested loops (O(n²)) to a single coordinated pass (O(n)) by moving pointers based on comparison results. Sliding window works by maintaining a running state across the window rather than recomputing from scratch each time.
🎯 Why It Matters
Two-pointer and sliding window are the patterns behind a huge fraction of interview problems. Recognising these patterns — "two numbers that sum to target," "longest substring without repeat," "container with most water" — turns an O(n²) brute force into an O(n) solution every time.
Ready to see how this works in the cloud?
Switch to Career Paths for structured paths (e.g. Developer, DevOps) and provider-specific lessons.
View role-based pathsSign in to track your progress and mark lessons complete.
Questions? Discuss in the community or start a thread below.
Join DiscordSign in to start or join a thread.