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

Two-Pointer ư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-Pointer đạ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-Pointer
- Mảng KHÔNG sorted + cần O(n) → Hash Map
- Cần O(1) space và mảng sorted → Two-Pointer
- Cần đếm tần suất → Hash Map (Two-Pointer 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-Pointer / 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.