Hai Tổng Trên Mảng Sắp XếpTwo Sum II - Input Array Is Sorted

Two Pointers ưu thế khi mảng đã được sắp xếp — không cần extra space, đạt O(n) time, O(1) space.

Hash Map cần O(n) space để đổi lấy O(1) lookup. Trên mảng sorted, Two Pointers đạt cùng O(n) time mà không cần buffer.

Phân biệt:
- Mảng sorted + tìm cặp tổng = target → Two Pointers
- Mảng KHÔNG sorted + cần O(n) → Hash Map
- Cần O(1) space và mảng sorted → Two Pointers
- Cần đếm tần suất → Hash Map (Two Pointers không phù hợp)

Code (Two Sum Sorted):

function twoSumSorted(nums: number[], target: number) {
  let left = 0, right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) return [left, right]
    if (sum < target) left++
    else right--
  }
  return null
}

Top edge case dễ miss:

1. Input rỗng: [] hoặc "" — return null/empty hay throw?
2. Single element: [1] — nhiều thuật toán giả định ≥ 2
3. Toàn bộ trùng: [5, 5, 5, 5] — duplicate handling
4. Đã sorted vs reverse sorted: worst case của quick sort
5. Negative numbers: quên handle khi đề chỉ ví dụ dương
6. Max int / overflow: sum của large numbers
7. Pointer null/undefined: trong linked list / tree
8. Off-by-one: < vs <=, length vs length-1
9. Cycle trong graph: infinite loop nếu không có visited set
10. Concurrent modification: thay đổi mảng đang duyệt

Cách hỏi clarify trong phỏng vấn:
- "Mảng có thể rỗng không?"
- "Có duplicate không?"
- "Có negative không?"
- "Range của giá trị?" (để check overflow)
- "Cần return [] hay null khi không có?"

Mẹo: trình bày edge case xong viết test ngay — chứng minh handle đúng.

Flow chuẩn 8 bước:

1. Nhắc lại đề bằng lời mình. Confirm hiểu đúng.
2. Hỏi constraints: size input, sorted chưa, có duplicate, edge case range.
3. Brute force trước. Đưa ra cách thô O(n²) chứng minh logic đúng.
4. Chỉ ra bottleneck. "Vòng for lồng nhau làm O(n²)".
5. Suggest pattern tối ưu. Hash Map / Two Pointers / Sliding Window / Binary Search...
6. Code rõ ràng, vừa viết vừa giải thích. Identifier có nghĩa (leftPointer, seen, không phải x, tmp).
7. Dry-run với ví dụ. Chạy code bằng tay trên 1-2 input.
8. Test edge cases + chốt Big-O. Time O(?) Space O(?).

Anti-patterns:
- Im lặng quá 30s
- Code ngay khi chưa hiểu đề
- Optimize sớm khi chưa có baseline
- Bỏ qua edge case rồi mới handle khi interviewer hỏi

Vàng: "Em chưa từng gặp pattern này, nhưng nhìn cấu trúc input em nghĩ có thể thử X..." — interviewer thích thấy bạn reason, không phải trả bài học thuộc.