Two Pointers: Hai Vận Động Viên Chạy Trên Đường Đua
Hãy tưởng tượng một đường đua thẳng. Có hai vận động viên:
Kiểu 1 — Từ hai đầu tiến vào giữa:
Một người đứng ở vạch xuất phát (index 0)
Một người đứng ở vạch đích (index n-1)
Họ chạy về phía nhau cho đến khi gặp nhau
Ứng dụng: 2Sum (sorted array), Container With Most Water, trapping rain water
Kiểu 2 — Rùa và Thỏ (Fast & Slow):
Rùa đi từng bước
Thỏ đi 2 bước mỗi lần
Nếu có vòng tròn, thỏ sẽ đuổi kịp rùa
Ứng dụng: Detect cycle in linked list, find middle of linked list
Sliding Window: Khung Cửa Tàu Hỏa
Hãy tưởng tượng bạn đang ngồi trên tàu hỏa, nhìn qua cửa sổ ra cánh đồng. Khung cửa sổ có kích thước cố định, và tàu di chuyển về phía trước — bạn thấy một “window” của khung cảnh, luôn luôn thay đổi, nhưng cùng một lúc chỉ thấy được một đoạn nhất định.
Fixed window: Khung cửa không thay đổi kích thước. Ứng dụng: Maximum sum subarray of size K.
Variable window: Khung cửa co giãn được. Bạn mở rộng khi cần (thêm phần tử vào window) và thu hẹp khi vi phạm điều kiện. Ứng dụng: Longest substring without repeating chars, minimum window substring.
Tại sao quan trọng?
Two Pointers và Sliding Window là cặp đôi hoàn hảo biến các bài toán O(N²) brute force thành O(N). Đây là hai trong những pattern phổ biến nhất tại FAANG — xuất hiện trong ít nhất 20–30% các bài Medium-level.
2. The FAANG Standard
Tại sao Big Tech coi trọng hai pattern này?
Cả hai đều thể hiện khả năng tư duy tối ưu hóa — từ brute force naive đến elegant linear solution. Đây chính xác là điều interviewer muốn thấy:
Brute force (O(N²)) → Nhận ra pattern → Optimal (O(N))
Hai Pointers giải quyết:
Bài toán pair/triplet thoả điều kiện (2Sum sorted, 3Sum)
Container/area problems (cần maximize với 2 boundaries)
Palindrome checking (so sánh từ hai đầu)
Merge hai sorted arrays
Sliding Window giải quyết:
Bất kỳ bài nào hỏi về subarray/substring “với điều kiện X”
“Longest/Shortest subarray where…”
“Maximum/Minimum sum of subarray of size K”
“Minimum window containing all characters of T”
Nhận dạng nhanh trong phỏng vấn
Nếu đề bài có từ “subarray”, “substring”, “window”, “consecutive” → nghĩ ngay đến Sliding Window.
Nếu đề bài có “sorted array”, “pair”, “sum equals target” → nghĩ ngay đến Two Pointers.
3. Visual Thinking (Mermaid)
Two Pointers — From Both Ends
graph LR
subgraph "Two Pointers: Container With Most Water"
A0["0"] --- A1["1"] --- A2["8"] --- A3["6"] --- A4["2"] --- A5["5"] --- A6["4"] --- A7["8"] --- A8["3"] --- A9["7"]
end
L["left=0<br/>height=1"] -->|"move right<br/>(smaller side)"| L2["left=1<br/>height=8"]
R["right=9<br/>height=7"] -->|"move left<br/>(smaller side)"| R2["right=8<br/>height=3"]
flowchart TD
Start([Start: left=0, right=n-1]) --> Cond{left < right?}
Cond -->|No| End([Return result])
Cond -->|Yes| Calc[Calculate area/sum with current pair]
Calc --> Compare{height[left] < height[right]?}
Compare -->|Yes - left is bottleneck| MoveLeft[left++]
Compare -->|No - right is bottleneck| MoveRight[right--]
MoveLeft --> Cond
MoveRight --> Cond
flowchart LR
subgraph Linked List with Cycle
N1[1] --> N2[2] --> N3[3] --> N4[4] --> N5[5] --> N6[6] --> N3
end
Slow["slow (moves 1 step)"] -.->|"after 3 steps: at node 4"| N4
Fast["fast (moves 2 steps)"] -.->|"after 3 steps: at node 6"| N6
4. TypeScript Templates
Template 1: Two Sum II (Sorted Array)
// LeetCode #167 — Two Sum II (Input Array Is Sorted)// Pattern: Two pointers from both ends// Time: O(N) | Space: O(1)function twoSumSorted(numbers: number[], target: number): number[] { let left = 0; let right = numbers.length - 1; while (left < right) { const sum = numbers[left] + numbers[right]; if (sum === target) { return [left + 1, right + 1]; // 1-indexed per problem requirement } else if (sum < target) { left++; // Need larger sum → move left pointer right } else { right--; // Need smaller sum → move right pointer left } } return []; // Guaranteed to have a solution per problem}console.log(twoSumSorted([2, 7, 11, 15], 9)); // [1, 2]console.log(twoSumSorted([2, 3, 4], 6)); // [1, 3]console.log(twoSumSorted([-1, 0], -1)); // [1, 2]
Template 2: 3Sum (O(N²) with Sorting + Deduplication)
// LeetCode #15 — 3Sum// Pattern: Sort + Two Pointers + Skip duplicates// Time: O(N²) | Space: O(1) extra (O(N) for output)function threeSum(nums: number[]): number[][] { nums.sort((a, b) => a - b); // Sort first — critical step const result: number[][] = []; for (let i = 0; i < nums.length - 2; i++) { // Skip duplicate values for the first element if (i > 0 && nums[i] === nums[i - 1]) continue; // Early termination: smallest possible sum > 0 if (nums[i] > 0) break; let left = i + 1; let right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([nums[i], nums[left], nums[right]]); // Skip duplicates for left and right pointers while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < 0) { left++; // Need larger sum } else { right--; // Need smaller sum } } } return result;}console.log(threeSum([-1, 0, 1, 2, -1, -4]));// [[-1,-1,2],[-1,0,1]]console.log(threeSum([0, 1, 1])); // []console.log(threeSum([0, 0, 0])); // [[0,0,0]]
Deduplication — Điểm dễ sai nhất
Có 3 chỗ cần skip duplicates:
i (outer loop): if (i > 0 && nums[i] === nums[i-1]) continue
left (inner): sau khi tìm được triplet, skip while nums[left] === nums[left+1]
right (inner): sau khi tìm được triplet, skip while nums[right] === nums[right-1]
Thứ tự: skip TRƯỚC khi left++ và right--.
Template 3: Container With Most Water
// LeetCode #11 — Container With Most Water// Pattern: Greedy Two Pointers// Time: O(N) | Space: O(1)function maxArea(height: number[]): number { let left = 0; let right = height.length - 1; let maxWater = 0; while (left < right) { const width = right - left; const h = Math.min(height[left], height[right]); const water = width * h; maxWater = Math.max(maxWater, water); // Greedy: move the shorter wall inward // (Moving taller wall can only decrease or maintain width AND height) if (height[left] < height[right]) { left++; } else { right--; } } return maxWater;}console.log(maxArea([1,8,6,2,5,4,8,3,7])); // 49console.log(maxArea([1,1])); // 1
Tại sao Greedy đúng?
Giả sử height[left] < height[right]. Nếu ta di chuyển right vào (giảm width), water chỉ có thể bằng hoặc nhỏ hơn (bounded by height[left]). Vậy không có lý do gì để di chuyển right. Di chuyển left — side ngắn hơn — mới có cơ hội tìm được container lớn hơn.
Template 4: Longest Substring Without Repeating
// LeetCode #3 — Longest Substring Without Repeating Characters// Pattern: Variable Sliding Window with HashMap// Time: O(N) | Space: O(min(N, Σ))function lengthOfLongestSubstring(s: string): number { const charIndex = new Map<string, number>(); // char -> last seen index let maxLen = 0; let left = 0; for (let right = 0; right < s.length; right++) { const char = s[right]; // If char is in current window, jump left past its last occurrence if (charIndex.has(char) && charIndex.get(char)! >= left) { left = charIndex.get(char)! + 1; } charIndex.set(char, right); maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}
// LeetCode #76 — Minimum Window Substring// Pattern: Variable Sliding Window with need/have counters// Time: O(|s| + |t|) | Space: O(|s| + |t|)function minWindow(s: string, t: string): string { if (s.length === 0 || t.length === 0) return ""; // Count required characters from t const need = new Map<string, number>(); for (const char of t) { need.set(char, (need.get(char) ?? 0) + 1); } const required = need.size; // Number of unique chars in t that need to be in window // Window character counts const windowCounts = new Map<string, number>(); let formed = 0; // Number of unique chars in window matching required count // Result: [window length, left, right] let ans: [number, number, number] = [-1, 0, 0]; let left = 0; for (let right = 0; right < s.length; right++) { // Add character from right side const char = s[right]; windowCounts.set(char, (windowCounts.get(char) ?? 0) + 1); // Check if current char's frequency matches what's needed if (need.has(char) && windowCounts.get(char) === need.get(char)) { formed++; } // Try to shrink window from left while it's valid while (formed === required && left <= right) { // Update answer if this window is smaller const windowLen = right - left + 1; if (ans[0] === -1 || windowLen < ans[0]) { ans = [windowLen, left, right]; } // Remove leftmost character from window const leftChar = s[left]; windowCounts.set(leftChar, windowCounts.get(leftChar)! - 1); // If we removed a necessary character, formed decreases if (need.has(leftChar) && windowCounts.get(leftChar)! < need.get(leftChar)!) { formed--; } left++; } } // Return the minimum window or "" if not found return ans[0] === -1 ? "" : s.substring(ans[1], ans[2] + 1);}// Test casesconsole.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"console.log(minWindow("a", "a")); // "a"console.log(minWindow("a", "aa")); // "" (impossible)console.log(minWindow("aa", "aa")); // "aa"// Walkthrough for "ADOBECODEBANC", t="ABC":// need = {A:1, B:1, C:1}, required = 3//// Expand right until formed === 3:// right=0 A: window={A:1}, formed=1 (A matched)// right=1 D: window={A:1,D:1}// right=2 O: window={A:1,D:1,O:1}// right=3 B: window={...,B:1}, formed=2// right=4 E: ...// right=5 C: window={...,C:1}, formed=3 ← VALID WINDOW "ADOBEC"//// Shrink left:// left=0 A: remove A, formed drops to 2 → stop shrinking// ans = [6, 0, 5] → "ADOBEC"//// Continue expanding... eventually find "BANC" at [4, 9, 12]
Giải thích formed counter
formed đếm số ký tự trong t (unique) đã được thỏa mãn trong window hiện tại. “Thỏa mãn” nghĩa là windowCount[char] >= need[char]. Khi formed === required, window valid — bắt đầu shrink. Khi shrink làm windowCount[char] < need[char] → formed-- → stop shrinking.
Template 6: Max Sliding Window (Preview of Monotonic Deque)
// LeetCode #239 — Sliding Window Maximum// Pattern: Sliding Window + Monotonic Deque// Time: O(N) | Space: O(k)// Note: Full coverage in next session on Monotonic Stack/Queuefunction maxSlidingWindow(nums: number[], k: number): number[] { const result: number[] = []; // Deque stores indices, front (deque[head]) = max element's index. // Dùng `head` index pointer thay cho .shift() (O(1) vs O(N)). const deque: number[] = []; let head = 0; for (let i = 0; i < nums.length; i++) { // Remove elements outside window if (head < deque.length && deque[head] < i - k + 1) { head++; } // Remove smaller elements from back (they can never be the max) while (head < deque.length && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } deque.push(i); // Start adding results once we have a full window if (i >= k - 1) { result.push(nums[deque[head]]); } } return result;}console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)); // [3,3,5,5,6,7]console.log(maxSlidingWindow([1], 1)); // [1]
5. Complexity Deep-dive
Two Pointers
Algorithm
Time
Space
Note
Two Sum (sorted)
O(N)
O(1)
One pass, two pointers
3Sum
O(N²)
O(1) extra
Sort O(N log N) + N × two pointer O(N)
Container With Most Water
O(N)
O(1)
One pass
Remove Duplicates (sorted)
O(N)
O(1)
In-place modification
Sliding Window
Algorithm
Time
Space
Note
Longest Substring No Repeat
O(N)
O(Σ)
Σ = alphabet size
Max Sum Subarray Size K
O(N)
O(1)
Fixed window
Minimum Window Substring
O(|S| + |T|)
O(|S| + |T|)
Two maps
Sliding Window Maximum
O(N)
O(k)
Monotonic deque
So sánh với Brute Force
Problem
Brute Force
Optimized
Improvement
Two Sum (sorted)
O(N²)
O(N)
N× faster
Longest No Repeat
O(N²) to O(N³)
O(N)
N² faster
Minimum Window
O(N² × M)
O(N + M)
Massive
3Sum
O(N³)
O(N²)
N× faster
6. Edge Cases & Pitfalls
Pitfall 1: 3Sum — Skip Duplicates sai chỗ
// WRONG: skip after i++ → will miss valid combinationsfor (let i = 0; i < n - 2; i++) { i++; if (nums[i] === nums[i-1]) continue; // BUG: i đã tăng rồi}// CORRECT: skip at top of loopfor (let i = 0; i < n - 2; i++) { if (i > 0 && nums[i] === nums[i-1]) continue; // check i > 0!}
Pitfall 2: Sliding Window — while vs if khi shrink
// WRONG for variable window: sử dụng if → chỉ shrink 1 lầnif (windowSize > k) { left++; }// CORRECT: shrink toàn bộ cho đến khi validwhile (windowSize > k) { left++; /* update state */ }
Pitfall 3: Map — decrement to 0 vs delete (khác nhau!)
// Behavior difference:const map = new Map([['a', 1]]);map.set('a', map.get('a')! - 1); // map.has('a') === true, get = 0map.delete('a'); // map.has('a') === false// In Minimum Window Substring: decrement to 0, do NOT delete// because need.has(char) check uses the presence of the key
vs Map
// WRONG for Unicode: assumes ASCIIconst freq = new Array(128).fill(0);freq[char.charCodeAt(0)]++;// CORRECT for general case: use Mapconst freq = new Map<string, number>();freq.set(char, (freq.get(char) ?? 0) + 1);
Pitfall 5: Empty string và single character
// Always handle upfront:if (s.length === 0) return 0; // or "" or []if (s.length === 1) return ...; // often trivial answer// In Two Pointers: left < right (not <=) to avoid same-element pairwhile (left < right) { ... }
7. Pattern Recognition
Khi đọc đề bài, nhận ra ngay pattern cần dùng:
Two Pointers — Keywords
“sorted array” + “two elements sum to…”
“find a pair/triplet that satisfies…”
“maximize/minimize something with two boundaries”
“palindrome” (compare from both ends)
“in-place removal” (fast/slow pointer variant)
“cycle in linked list”
Sliding Window — Keywords
“subarray/substring of size k”
“longest subarray where…”
“shortest subarray/window containing…”
“maximum/minimum sum of consecutive elements”
“all characters of t must appear”
Quick Decision Tree
Bài hỏi về array/string:
├── "sorted array" + "two elements" → Two Pointers
├── "subarray/substring" + "condition" → Sliding Window
│ ├── Fixed size k → Fixed Window
│ └── "longest/shortest" → Variable Window
├── "linked list" + "cycle/middle" → Fast/Slow Pointers
└── "pair/triplet sum" → Two Pointers (sort first for 3Sum)
8. Top LeetCode Problems
Essential (Must Solve)
#
Problem
Difficulty
Pattern
Time
167
Two Sum II — Input Array Is Sorted
Easy
Two Pointers
O(N)
15
3Sum
Medium
Sort + Two Pointers
O(N²)
11
Container With Most Water
Medium
Greedy Two Pointers
O(N)
3
Longest Substring Without Repeating Characters
Medium
Sliding Window
O(N)
76
Minimum Window Substring
Hard
Variable Sliding Window
O(N)
Recommended (Practice More)
#
Problem
Difficulty
Pattern
125
Valid Palindrome
Easy
Two Pointers
283
Move Zeroes
Easy
Fast/Slow (two pointers)
18
4Sum
Medium
Sort + Two Pointers
209
Minimum Size Subarray Sum
Medium
Variable Sliding Window
424
Longest Repeating Character Replacement
Medium
Sliding Window
567
Permutation in String
Medium
Fixed Sliding Window
239
Sliding Window Maximum
Hard
Sliding Window + Monotonic Deque
42
Trapping Rain Water
Hard
Two Pointers / Stack
141
Linked List Cycle
Easy
Fast/Slow Pointers
287
Find the Duplicate Number
Medium
Fast/Slow (Floyd’s)
Pattern-by-Pattern Ordering
Bắt đầu với:
#167 Two Sum II → hiểu two pointers cơ bản
#15 3Sum → học deduplication
#3 Longest No Repeat → sliding window cơ bản
#209 Min Size Subarray Sum → variable window
Sau khi nắm vững:
5. #11 Container With Most Water → greedy insight
6. #424 Longest Repeating Char → window shrink strategy
7. #76 Minimum Window → hardest, need/have pattern
8. #42 Trapping Rain Water → two pointers on “height” array
9. Self-Assessment Checklist
Two Pointers
Có thể implement Two Sum II không cần nhìn gợi ý (< 5 phút)
Hiểu tại sao sorted array là điều kiện cần cho two pointers từ hai đầu
Có thể implement 3Sum với deduplication đúng (< 20 phút)
Giải thích được tại sao greedy trong Container With Most Water đúng
Biết phân biệt khi nào dùng left < right vs left <= right
Sliding Window
Có thể implement Longest No Repeat từ đầu (< 10 phút)
Hiểu sự khác biệt giữa fixed window và variable window
Biết cấu trúc chung: expand right → update state → shrink left if violated
Có thể implement Minimum Window Substring (< 30 phút)
Hiểu need vs have (hay required vs formed) counter pattern
Edge Cases
Luôn handle empty string/array
Biết dùng Map thay array cho Unicode
Không bị nhầm decrement-to-0 vs delete trong frequency map
Shrink bằng while, không phải if trong variable window
Overall Readiness
Giải được 5/5 problems trong phần Essential trong 1 buổi
Có thể giải thích Two Pointers và Sliding Window bằng analogy (không cần code)
Nhận ra pattern từ đề bài trong vòng 30 giây
Khi hoàn thành checklist này
Bạn đã nắm vững một trong những pattern quan trọng nhất của FAANG interviews. Tiếp tục với 02-Bit-Manipulation để mở rộng toolkit của mình.