Phỏng vấn DSA tại Big Tech — 288 bài tập kèm lời giải Python

Phạm Ngọc Lâm — ex-Senior Software Engineer @ TikTok / Grab, co-founder EngineerPro

Lê Quang Hoà — ex-Tech Lead @ TikTok, co-founder EngineerPro

2026

Mục tiêu project: tổng hợp các câu hỏi DSA coding interview tiêu biểu nhất ở các công ty Big Tech, kèm lời giải Python 3, phân tích độ phức tạp, bẫy phỏng vấn thường gặp, và bài tự luyện liên quan để bạn đọc luyện tập có hệ thống theo pattern, không phải học vẹt từng bài.

Quy mô: 288 bài tập (267 bài giải đầy đủ + 21 bài recap cross-reference qua các chương) · 44 pattern · Lời giải Python 3 chuẩn LC. Bản web miễn phí: 14 chương đầu; bản đầy đủ mua trên Gumroad.

📚 Cuốn sách dựa trên nội dung khoá học — các topic được biên soạn theo lộ trình của khoá DSA Coding Interview đang được giảng dạy tại EngineerPro.

Tuy nhiên, cuốn sách không thể thay thế việc rèn luyện tư duy thuật toán cũng như cách thức học và hiểu sâu về thuật toán mà bạn có được khi tham gia khoá học trực tiếp tại EngineerPro.

Các bạn quan tâm về khoá học vui lòng nhắn tin qua fanpage để được tư vấn:

📖 Chi tiết khoá DSA 🎓 Tất cả khoá luyện phỏng vấn (DSA, System Design, CS, Behavior) 💬 Nhắn Inbox Messenger

🎯 Cần mentor 1:1 đồng hành đến khi có offer?

MentorPro — chương trình mentor 1-1 cá nhân hoá từ engineer đang/từng làm tại các Big Tech (NVIDIA, TikTok, Google, Meta, AWS). Là đối tác chiến lược của EngineerPro, đồng hành cùng bạn từ screening CV → luyện thuật toán → mock interview → cho đến khi nhận được job offer.

✅ 30+ học viên đã nhận offer tại Grab, NAB, IBM, ANT Group, VinBigData, Cognizant, SAP, Deputy… kể từ 7/2025. Học viên MentorPro còn được tham gia miễn phí 100% các khoá EngineerPro do mentor chỉ định.

🌐 Xem chi tiết MentorPro 💬 Nhắn Fanpage MentorPro

Project này được bảo trợ bởi EngineerPro.

EngineerPro là cộng đồng và nền tảng đào tạo hướng đến việc giúp kỹ sư phần mềm Việt Nam bứt phá vào Big Tech và các công ty quốc tế — từ phỏng vấn coding, system design, đến career growth. Cuốn sách này là một trong những đóng góp của chúng tôi vào hệ sinh thái học tập tiếng Việt cho engineers.

How to find us:

📖 Bản miễn phí trên web: 14 chương đầu (Array → Interval). Đây là bản preview để bạn đọc thử và luyện theo pattern.

Muốn đọc toàn bộ 44 chương + phụ lục (288 bài kèm lời giải Python 3 đầy đủ)? Mua sách đầy đủ tại Gumroad:

🛒 Mua sách đầy đủ trên Gumroad

Về tác giả

Phạm Ngọc Lâm

Phạm Ngọc Lâm

ex-Senior Software Engineer @ TikTok · Grab

Co-founder EngineerPro

in LinkedIn 🌐 Portfolio

Lê Quang Hoà

Lê Quang Hoà

ex-Tech Lead @ TikTok

Co-founder EngineerPro

in LinkedIn

Cả hai tác giả đã trải qua hàng trăm cuộc phỏng vấn technical với vai trò cả interviewer lẫn interviewee tại TikTok, Grab và các công ty công nghệ hàng đầu khác. Cuốn sách này là chắt lọc từ những trải nghiệm thật ở cả hai phía của bàn phỏng vấn.

🙏 Lời cảm ơn

Cuốn sách này lấy cảm hứng từ các chủ đề DSA mà nhiều mentor xuất sắc tại EngineerPro đã giảng dạy trong các khoá học và mentor session suốt nhiều năm qua. Hai tác giả xin gửi lời cảm ơn chân thành đến đội ngũ giảng viên đã đồng hành cùng cộng đồng:

  • Chị Lam Đỗ — ex-Software Engineer @ Meta
  • Anh Lê Chương — Senior Software Engineer @ Google
  • Anh Trần Khánh Hiệp — Software Engineer @ Spotify
  • Anh Tùng Trần — Senior SWE @ Pendle · ex-Senior SWE @ Shopee
  • Anh Quang Hoàng — Senior Software Engineer @ Google
  • Anh Kyle Nguyễn — Senior Engineer @ Citadel
  • Anh Tùng Lâm — Senior Software Engineer @ Shopee
  • Anh Hiếu — Senior Software Engineer @ Acronis · ex-SWE @ Shopee
  • … và nhiều anh/chị giảng viên khác trong cộng đồng EngineerPro.

Nếu cuốn sách này giúp ích cho bạn, một phần công lao thuộc về những người thầy, người mentor đã không ngừng chia sẻ kiến thức cho thế hệ kỹ sư trẻ Việt Nam. 💙

Phần mở đầu

Video: ví dụ một buổi phỏng vấn coding

Trước khi đi vào nội dung chính, mời bạn xem một buổi phỏng vấn coding mẫu do EngineerPro thực hiện. Video giúp bạn hình dung luồng diễn ra thực tế của một vòng phỏng vấn: cách interviewer đặt câu hỏi, cách ứng viên clarify, phân tích, code và trao đổi follow-up.

Ví dụ một buổi phỏng vấn coding — EngineerPro Xem trên YouTube

▶ Xem cả playlist các buổi phỏng vấn mẫu khác trên kênh YouTube EngineerPro.

Mẹo xem: lần đầu xem hãy quan sát cách ứng viên trình bày, không cần hiểu hết thuật toán. Lần thứ 2 quay lại sau khi đã đọc xong Chương 1–5, bạn sẽ nhận ra rất nhiều pattern quen thuộc.

0.1 Lời nói đầu

Chào mừng bạn đến với Coding DSA Interview At Big Tech kèm lời giải.

Cuốn sách này được viết với một niềm tin đơn giản: phỏng vấn coding ở Big Tech không phải là cuộc thi đố vui — đó là một bộ kỹ năng có thể học và rèn luyện một cách có hệ thống.

Hầu hết các tài liệu phỏng vấn hiện có thường rơi vào 1 trong 2 thái cực: - Quá học thuật (textbook DSA), thiếu thực tế phỏng vấn. - Quá “mẹo vặt” (300 LeetCode), thiếu khung tư duy hệ thống.

Cuốn sách này cố gắng đứng ở giữa: học PATTERN, không học bài. Mỗi chương tập trung vào 1 pattern, 5-18 bài tiêu biểu, kèm cách trình bày trên whiteboard và bẫy thường gặp khi phỏng vấn thật. Khi bạn nắm được pattern, bài mới chỉ là biến thể.

Đối tượng độc giả: - Sinh viên CNTT chuẩn bị thực tập / new-grad ở Big Tech. - Lập trình viên đã đi làm muốn chuyển việc lên FAANG-tier. - Người tự học LeetCode đang bí cách tiếp cận có hệ thống.

Chúc bạn pass mọi vòng phỏng vấn!

Cách dùng cuốn sách này

Có 3 cách tiếp cận tuỳ thời gian + kinh nghiệm:

Đọc tuần tự (khuyến nghị cho người mới): Chương 1 → 44 theo thứ tự. Mỗi chương bạn phải tự code trước khi xem lời giải. Hết Level 1 (Chương 1–20) bạn đã có nền tảng tốt cho phỏng vấn entry-level Big Tech.

Đọc theo pattern (nếu đã có nền): lướt mục lục, đọc chương nào còn yếu. Mỗi chương đứng độc lập, có tham chiếu chéo (cross-reference) sang chương khác rõ ràng.

Ôn gấp trước onsite: xem Roadmap học dưới đây.

Roadmap học

📖 Bản web miễn phí: chỉ công khai 14 chương đầu (Array → Interval). Chương 15–44 và phụ lục nằm trong sách đầy đủ trên Gumroad. Các roadmap bên dưới vẫn mô tả toàn bộ sách để bạn lập kế hoạch học.

Roadmap 1 tuần (chuẩn bị onsite gấp): - Ngày 1-2: Frontmatter (0.1-0.5) + Phụ lục D (50 bài must-do). - Ngày 3: Ôn Chương 1, 2, 5, 6 (Array, String, Binary Search, Hash) — toàn bộ Easy/Medium tier. - Ngày 4: Chương 7, 9, 10, 11 (Linked List, Graph, BFS, DFS). - Ngày 5: Chương 17, 18, 27 (D&C, Monotonic, Sliding Window). - Ngày 6: Chương 28, 29 (Backtracking, DP) — 2 chương dài và quan trọng nhất. - Ngày 7: Mock interview + đọc Phụ lục E (Behavioral).

Roadmap 2 tuần (đã biết DSA, refresh): - Tuần 1: Level 1 (Chương 1-20) — 3 chương/ngày. - Tuần 2: Level 2 (Chương 21-32) — 2 chương/ngày + mock interview cuối tuần.

Roadmap 6 tuần (người mới): - Tuần 1-2: Frontmatter + Level 1 (Ch 1-10) — 1 chương/ngày, tự code mỗi bài. - Tuần 3-4: Level 1 (Ch 11-20) — 1 chương/ngày. - Tuần 5: Level 2 (Ch 21-32) — 2 chương/ngày, đọc kỹ pattern. - Tuần 6: Level 3 (Ch 33-44) — 2 chương/ngày, không cần thuộc hết — biết tồn tại.

Skip nếu thiếu thời gian (priority chương quan trọng): bỏ qua Ch 20 (Prime), Ch 31 (Game Theory), Ch 33-36 (MST/Hash/KMP/Z) — niche pattern, hiếm trong phỏng vấn entry/mid.

Tự đánh giá level: - Easy < 30 phút mỗi bài → Level 1 đủ. - Medium 30-60 phút → đọc tới Level 2. - Hard > 60 phút hoặc bí thường xuyên → đọc cả Level 3.

⚠️ Đừng đọc code trước khi tự lên kế hoạch. Sách trình bày lời giải sau mục “Hướng tiếp cận” có lý do — bạn phải vật lộn với bài trước khi xem đáp án; đó là cách não bộ hấp thu pattern hiệu quả nhất.

0.2 Quy trình một buổi phỏng vấn coding (UMPIRE)

UMPIRE = framework 6 bước giúp bạn không “đóng băng” khi nhận đề:

U — Understand (5 phút)

M — Match (2 phút)

P — Plan (5 phút)

I — Implement (15 phút)

R — Review (3 phút)

E — Evaluate (2 phút)

Mẹo tâm lý: Interviewer muốn thấy quá trình tư duy, không phải lời giải hoàn hảo ngay từ đầu. Hãy nói thành lời (think out loud).

0.3 Big-O trong 30 phút

Bài giảng Big-O — anh Lê Chương — EngineerPro Big-O — EngineerPro

🎥 Xem thêm bài giảng video về Big-O — trình bày bởi anh Lê Chương, Senior Software Engineer @ Google, giảng viên từ team EngineerPro.

Định nghĩa nhanh

f(n) = O(g(n)) ↔︎ tồn tại c > 0, n₀ sao cho f(n) <= c·g(n) với mọi n >= n₀.

Trong phỏng vấn: bỏ qua hằng số, bỏ qua thành phần thấp hơn. 3n² + 100n + 5 = O(n²).

Bảng “cheatsheet”

Notation Tên Ví dụ
O(1) Constant Hash lookup, push/pop stack
O(log n) Logarithm Binary search
O(n) Linear Duyệt mảng
O(n log n) Linearithmic Sort, segment tree build
O(n²) Quadratic Brute force 2 vòng for
O(2^n) Exponential Subset bruteforce
O(n!) Factorial Permutation bruteforce

Quy tắc tính toán

  1. Sequential (a();b();): O(a + b), lấy max.
  2. Nested loops: O(n × n) = O(n²).
  3. Recursion:
  4. Master theorem cho T(n) = aT(n/b) + f(n):

Amortized analysis

Một số op đôi khi chậm, trung bình nhanh: - list.append() Python: O(1) amortized (mặc dù dynamic resize). - Hash table với open addressing: O(1) amortized.

Bẫy thường gặp

Các bound thực tế trong phỏng vấn

n Cho phép
n ≤ 10 O(n!) brute force
n ≤ 20 O(2^n) bitmask
n ≤ 5000 O(n²) OK
n ≤ 10^5 O(n log n) hoặc O(n)
n ≤ 10^7 O(n) strict
n ≤ 10^9 O(log n) (search on answer)

0.4 Python 3 cheat-sheet cho phỏng vấn

Data structures

# List
lst = [1, 2, 3]
lst.append(x); lst.pop()      # O(1) cả 2
lst.insert(0, x); lst.pop(0)  # O(n) - tránh!
sorted_lst = sorted(lst)      # O(n log n), trả về list mới
lst.sort()                    # in-place
lst[::-1]                     # reverse, O(n)
lst[a:b]                      # slicing, O(b-a) copy

# Dict
d = {}; d[k] = v               # O(1) amortized
from collections import defaultdict, Counter
dd = defaultdict(list)
cnt = Counter("anagram")       # {'a':3, 'n':1, 'g':1, 'r':1, 'm':1}
cnt.most_common(2)             # [('a',3), ('n',1)]

# Set
s = {1, 2, 3}
s.add(x); s.discard(x)         # O(1)
s & t; s | t; s - t            # giao/hợp/hiệu

# Deque (double-ended queue) — dùng cho BFS, sliding window
from collections import deque
dq = deque()
dq.append(x); dq.appendleft(x)
dq.pop(); dq.popleft()         # tất cả O(1)

# Heap (min-heap)
import heapq
h = []
heapq.heappush(h, x)
heapq.heappop(h)              # O(log n)
heapq.heapify(lst)            # O(n)
heapq.nsmallest(k, lst)       # O(n log k)

Idioms quan trọng

# Enumerate
for i, x in enumerate(lst):
    pass

# Zip
for a, b in zip(lst1, lst2):
    pass

# Comprehension
[x*2 for x in lst if x > 0]
{x: i for i, x in enumerate(lst)}

# Bisect
from bisect import bisect_left, bisect_right
idx = bisect_left(sorted_lst, x)

# Functools
from functools import cache, reduce
@cache
def f(n):
    ...
reduce(lambda a, b: a + b, lst, 0)

# Itertools
from itertools import combinations, permutations, product
list(combinations([1,2,3], 2))    # [(1,2),(1,3),(2,3)]

Pitfalls (CRITICAL — đọc kỹ!)

Số học & division: - dict[k] raise KeyError nếu k không có → dùng dict.get(k, default) hoặc defaultdict. - int / int = float; phải dùng // cho integer division. - -7 // 2 = -4 (floor), không phải -3 (truncate toward 0). Truncate: int(-7/2). - -7 % 2 = 1 trong Python (luôn ≥ 0), khác với C/C++/Java. Cẩn thận khi modulo số âm trong prefix sum.

Heap & comparison: - heapq Python chỉ có min-heap. Muốn max-heap → push -x. - Heap so sánh tuple element-by-element: (priority, idx, payload) — idx làm tiebreaker khi priority bằng nhau (vì payload có thể không hashable / comparable, ví dụ ListNode). - heappush heap với tuple chứa object không comparable (như ListNode) sẽ raise TypeError khi priority bằng nhau.

Recursion & cache: - Python recursion limit mặc định ~1000. Set sys.setrecursionlimit(10**6) cho graph/tree lớn. - Python không có tail call optimization → đệ quy đệ quy đệ quy ⇒ stack overflow. Chuyển sang iterative khi n > 10^5. - @functools.cache chỉ work với arguments hashable. list / dict / set → không cache được. Dùng tuple(...) / frozenset(...) để wrap. - @cache trên self.method lưu cache global (qua mọi instance). Dùng @cached_property nếu cache theo instance.

Mutable defaults & references: - Default mutable argument: def f(x=[]) — bug nghiêm trọng (mọi call share cùng list). Dùng def f(x=None): x = x or []. - result.append(path) — append reference, không copy. Cần result.append(path.copy()) hoặc result.append(path[:]).

Sort & stability: - sorted() Python là Timsort, stable, O(n log n). Tận dụng stability để sort multi-key bằng nhiều lần sort. - Sort custom: Python 3 không có cmp= arg. Dùng key=... hoặc functools.cmp_to_key(...).

Integer & overflow: - Python int vô hạn → không cần lo overflow như Java/C++. Nhưng cố ý truncate (32-bit) khi đề yêu cầu (LC 7, LC 8, LC 50).

0.5 Cách trình bày code trên whiteboard / CoderPad

Nguyên tắc vàng

  1. Nói thành lời (“think out loud”). Im lặng khiến interviewer khó theo dõi tư duy của bạn — họ cần nghe được luồng suy nghĩ để giúp khi bạn bí, và để đánh giá cách bạn tiếp cận vấn đề chứ không chỉ kết quả cuối.
  2. Bắt đầu từ ví dụ cụ thể. Vẽ input ra giấy, chạy thuật toán bằng tay từng bước.
  3. Code theo hướng top-down. Viết hàm chính def solve(...) trước, gọi tới các hàm phụ (helper), rồi mới cài đặt hàm phụ sau.
  4. Đặt tên biến rõ ràng:
  5. Đừng cố viết ngắn cho ngắn. Code rõ ràng quan trọng hơn 1 dòng “thông minh”.

Khi bí

Sau khi xong

Lưu ý về tác phong khi phỏng vấn

Mẫu lời nói cho từng giai đoạn

Giai đoạn Câu mẫu
Làm rõ đề “Cho em xác nhận lại đề: input là …, output là …, có ràng buộc gì thêm không?”
Brute force “Trước hết em mô tả cách trực tiếp: duyệt mọi cặp, độ phức tạp O(n²)…”
Tối ưu “Em thấy có thể dùng hash map để giảm thao tác tra cứu xuống O(1)…”
Bí “Em đang lưỡng lự giữa hash map và sorted array. Anh/chị có gợi ý nào không?”
Xong “Lời giải chạy O(n) thời gian và O(n) bộ nhớ. Để em chạy thử vài edge case…”

Chương 1 — Array

Array (mảng) là cấu trúc dữ liệu cơ bản nhất nhưng cũng là pattern xuất hiện nhiều nhất trong phỏng vấn coding ở Big Tech. Phần lớn các kỹ thuật ở chương sau (two pointers, sliding window, prefix sum, monotonic stack, …) đều bắt nguồn từ việc thao tác trên array. Mục tiêu của chương: thành thạo các thao tác in-place, two-pass, và bắt đầu hình thành thói quen “nghĩ về index thay vì nghĩ về phần tử”.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Template code

from typing import List

def two_pass_pattern(nums: List[int]) -> List[int]:
    """Mẫu 2-lượt: pass 1 gom thông tin, pass 2 dùng thông tin đó."""
    n = len(nums)
    aux = [0] * n
    # pass 1: tính prefix / suffix / count
    for i in range(n):
        aux[i] = ...   # tuỳ bài
    # pass 2: dùng aux để ra kết quả
    out = [0] * n
    for i in range(n):
        out[i] = ...   # tuỳ bài
    return out


def two_pointers_in_place(nums: List[int]) -> int:
    """Mẫu two pointers in-place: slow = vị trí ghi, fast = vị trí đọc."""
    slow = 0
    for fast in range(len(nums)):
        if condition(nums[fast]):
            nums[slow] = nums[fast]
            slow += 1
    return slow  # độ dài phần "hợp lệ" sau khi nén

Bài tự luyện cuối chương

1.1 Two Sum (LC 1)

Đề bài

Cho một mảng số nguyên nums và một số nguyên target. Hãy trả về chỉ số của hai phần tử trong nums sao cho tổng của chúng bằng target.

Bạn có thể giả định mỗi input có đúng một đáp án, và không được dùng cùng một phần tử hai lần.

Ví dụ

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Giải thích: nums[0] + nums[1] == 9.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). Duyệt mọi cặp (i, j) với i < j và kiểm tra nums[i] + nums[j] == target. Dễ code nhưng sẽ TLE khi n lớn.

Tối ưu — Hash map một lượt — O(n). Khi đứng tại chỉ số i, ta cần tìm xem có j < i nào để nums[j] == target - nums[i] hay không. Dùng dict để lưu {giá_trị: chỉ_số} của các phần tử đã thấy.

Mẹo trình bày: Luôn bắt đầu bằng brute force, nói rõ độ phức tạp của nó, sau đó nói: “Em nghĩ có thể thay phép tìm tuyến tính O(n) bằng hash map tra cứu O(1), nhờ đó tổng độ phức tạp giảm từ O(n²) xuống O(n)…” — interviewer rất thích luồng tư duy này.

Code Python 3

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}
        for i, x in enumerate(nums):
            complement = target - x
            if complement in seen:
                return [seen[complement], i]
            seen[x] = i
        return []  # theo đề bài, dòng này không bao giờ chạy

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

1.2 Best Time to Buy and Sell Stock (LC 121)

Đề bài

Cho mảng prices với prices[i] là giá cổ phiếu vào ngày thứ i. Bạn được mua một lần rồi bán một lần sau đó (không được bán trước khi mua). Hãy trả về lợi nhuận lớn nhất có thể, hoặc 0 nếu không có giao dịch nào có lãi.

Ví dụ

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5
Giải thích: mua ngày 2 (giá 1), bán ngày 5 (giá 6), lợi nhuận = 6 - 1 = 5.

Input:  prices = [7, 6, 4, 3, 1]
Output: 0
Giải thích: giá giảm liên tục, không có giao dịch nào có lãi.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). Duyệt mọi cặp (i, j) với i < j và lấy max(prices[j] - prices[i]). TLE với n = 10^5.

Tối ưu — một lượt, O(n). Khi đứng tại ngày i và quyết định “sẽ bán hôm nay”, lợi nhuận tối ưu là prices[i] - min(prices[0..i-1]). Vậy ta chỉ cần duy trì min_so_far khi duyệt và cập nhật best mỗi bước.

Hình minh hoạ với prices = [7, 1, 5, 3, 6, 4]:

day        :   0    1    2    3    4    5
prices     :   7    1    5    3    6    4
                    │              │
                    │ mua ở đây    │ bán ở đây
                    ▼              ▼
min_so_far :   7    1    1    1    1    1
profit_now :   0    0    4    2    5    3   (= prices[i] - min_so_far)
best       :   0    0    4    4    5    5   ← đáp án = 5
                              ▲
                              giữ nguyên vì 2 < 4

Mindset: Đây là DP một biến. State min_so_far chính là cách rút gọn mảng dp[i] = min(prices[0..i]) về O(1) space — kỹ thuật sẽ gặp đi gặp lại ở các chương DP sau.

Code Python 3

from typing import List
import math

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_so_far = math.inf
        best = 0
        for p in prices:
            min_so_far = min(min_so_far, p)
            best = max(best, p - min_so_far)
        return best

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

1.3 Product of Array Except Self (LC 238)

Đề bài

Cho một mảng nums có n số nguyên, trả về mảng answer cùng độ dài, sao cho answer[i] là tích của tất cả phần tử của nums trừ nums[i].

Ràng buộc đặc biệt: - Không được dùng phép chia. - Phải chạy trong O(n) time.

Ví dụ

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Giải thích:
  answer[0] = 2*3*4 = 24
  answer[1] = 1*3*4 = 12
  answer[2] = 1*2*4 = 8
  answer[3] = 1*2*3 = 6

Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). Với mỗi i, duyệt lại toàn mảng để tính tích — đề bài đã cấm sẵn.

Phép chia — O(n) nhưng bị cấm. Tính total = product(nums) rồi answer[i] = total / nums[i]. Cấm vì khi nums[i] == 0 ta chia cho 0; hơn nữa, nhiều ngôn ngữ không có integer-exact division.

Tối ưu — Prefix product + Suffix product — O(n) time, O(1) extra space (không tính output).

Quan sát: answer[i] = (∏ nums[0..i-1]) * (∏ nums[i+1..n-1]). Gọi 2 lượng: - left[i] = tích nums[0..i-1] (left product, left[0] = 1). - right[i] = tích nums[i+1..n-1] (right product, right[n-1] = 1). Khi đó answer[i] = left[i] * right[i].

Để đạt O(1) extra space, ta dùng chính mảng answer: - Lượt 1 (trái → phải): điền answer[i] = left[i]. - Lượt 2 (phải → trái): nhân answer[i] *= right, vừa duyệt vừa cập nhật biến right.

Hình minh hoạ với nums = [1, 2, 3, 4]:

              i=0     i=1     i=2     i=3
nums      :  [  1  ,   2  ,   3  ,   4  ]

                 ┌─────────────┐
                 │  prefix →   │   (tích các phần tử BÊN TRÁI i)
                 ▼             ▼
left[i]   :  [  1  ,   1  ,   2  ,   6  ]
              (rỗng) (1)   (1·2) (1·2·3)

                         ┌─────────────┐
                         │   ← suffix  │  (tích các phần tử BÊN PHẢI i)
                         ▼             ▼
right[i]  :  [ 24  ,  12  ,   4  ,   1  ]
            (2·3·4)(3·4)  (4)  (rỗng)

                         ↓  nhân từng vị trí  ↓

answer[i] :  [ 24  ,  12  ,   8  ,   6  ]
              1·24   1·12   2·4    6·1

Trong code thực, ta không lưu cả 2 mảng left và right — chỉ dùng answer cho lượt prefix, rồi dùng 1 biến right rolling từ phải sang trái để nhân vào answer ngay tại chỗ.

Code Python 3

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # Lượt 1: answer[i] = tích các phần tử ở bên trái i.
        left = 1
        for i in range(n):
            answer[i] = left
            left *= nums[i]

        # Lượt 2: nhân thêm tích bên phải, dùng biến right rolling.
        right = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right
            right *= nums[i]

        return answer

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

1.4 Move Zeroes (LC 283)

Đề bài

Cho mảng nums, hãy di chuyển tất cả số 0 về cuối mảng, giữ nguyên thứ tự tương đối của các phần tử khác 0. Phải làm in-place, không được tạo mảng phụ.

Ví dụ

Input:  nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Input:  nums = [0]
Output: [0]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n) time, O(n) extra space. Tạo mảng phụ chứa các số khác 0, sau đó pad số 0 cho đủ n. Đề bài cấm dùng mảng phụ — bị loại.

Tối ưu — Two pointers — O(n) time, O(1) extra space. Dùng 2 con trỏ: - slow = vị trí tiếp theo để ghi một số khác 0. - fast = vị trí đang đọc trong mảng.

Pass 1: với mỗi fast, nếu nums[fast] != 0 → nums[slow] = nums[fast], tăng slow. Pass 2: từ slow đến hết mảng, gán 0.

Hình minh hoạ với nums = [0, 1, 0, 3, 12]:

                    Lượt 1: dồn các số khác 0 về đầu
                    ──────────────────────────────────

Khởi tạo :  [ 0 , 1 , 0 , 3 , 12]      slow=0  fast=0
              S
              F

fast=0:  nums[0]=0, bỏ qua
         [ 0 , 1 , 0 , 3 , 12]         slow=0  fast=1
           S
               F

fast=1:  nums[1]=1≠0 → ghi nums[0]=1, slow++
         [ 1 , 1 , 0 , 3 , 12]         slow=1  fast=2
               S
                   F

fast=2:  nums[2]=0, bỏ qua             slow=1  fast=3
fast=3:  nums[3]=3≠0 → ghi nums[1]=3, slow++
         [ 1 , 3 , 0 , 3 , 12]         slow=2  fast=4
                   S
                       F

fast=4:  nums[4]=12≠0 → ghi nums[2]=12, slow++
         [ 1 , 3 ,12 , 3 , 12]         slow=3  fast=hết

                    Lượt 2: từ slow đến hết, gán 0
                    ──────────────────────────────────

         [ 1 , 3 ,12 , 0 , 0 ]    ← đáp án
                       ▲   ▲
                   gán 0  gán 0

Cách này tối thiểu hoá số phép ghi về đúng n (vì mỗi ô được ghi đúng 1 lần). Có một biến thể dùng swap ngay khi đi qua, code ngắn hơn nhưng số ghi gấp đôi.

Code Python 3

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        # Lượt 1: dồn các số khác 0 về đầu.
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        # Lượt 2: phần còn lại gán 0.
        for i in range(slow, len(nums)):
            nums[i] = 0

Phân tích độ phức tạp

Bình luận

slow = 0
for fast in range(len(nums)):
    if nums[fast] != 0:
        nums[slow], nums[fast] = nums[fast], nums[slow]
        slow += 1

Bài tự luyện liên quan

1.5 Container With Most Water (LC 11)

Đề bài

Cho mảng height với height[i] là chiều cao của cột thứ i. Hãy chọn ra 2 cột i < j sao cho lượng nước chứa được giữa chúng là lớn nhất.

Lượng nước = min(height[i], height[j]) * (j - i).

Ví dụ

Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Giải thích: chọn cột 1 (cao 8) và cột 8 (cao 7) → 7 * (8-1) = 49.

Input:  height = [1, 1]
Output: 1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). Duyệt mọi cặp (i, j) và lấy max. TLE với n = 10^5.

Tối ưu — Two pointers, O(n). Đặt l = 0, r = n - 1. Tại mỗi bước, diện tích hiện tại = min(height[l], height[r]) * (r - l).

Câu hỏi cốt lõi: dịch con trỏ nào? — Dịch con trỏ ở bên thấp hơn.

Tại sao? Diện tích bị giới hạn bởi cột thấp hơn. Nếu dịch con trỏ ở cột cao hơn vào trong, khoảng cách giảm và cột thấp vẫn là bottleneck → diện tích chỉ có thể giảm hoặc bằng. Còn nếu dịch con trỏ ở cột thấp hơn, ta có cơ hội (không bảo đảm) gặp một cột cao hơn để diện tích tăng.

Proof bằng “loại trừ”: Khi cố định cột thấp (giả sử bên trái) và dịch cột bên phải vào, mọi cặp (l, r' < r) đều có diện tích ≤ height[l] * (r - l). Do đó các cặp này không thể là đáp án nếu chưa tốt hơn cái hiện tại — ta “loại trừ” chúng cùng lúc và chỉ cần dịch l.

Hình minh hoạ với height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

         ▓                                ▓
   8     ▓       ▓                        |          ← chiều cao 8
   7     ▓       ▓                        ▓
   6     ▓   ▓   ▓               ▓        ▓
   5     ▓   ▓   ▓       ▓       ▓        ▓
   4     ▓   ▓   ▓       ▓   ▓   ▓        ▓
   3     ▓   ▓   ▓       ▓   ▓   ▓    ▓   ▓
   2     ▓   ▓   ▓   ▓   ▓   ▓   ▓    ▓   ▓
   1 ▓   ▓   ▓   ▓   ▓   ▓   ▓   ▓    ▓   ▓
       └─┴───┴───┴───┴───┴───┴───┴────┴───┴─
index: 0   1   2   3   4   5   6    7   8
       L                                  R

Bảng trace (★ = đáp án tốt nhất tại thời điểm đó):

  bước │  L   R │ min(h[L], h[R]) │ width │  area │ move
  ─────┼────────┼─────────────────┼───────┼───────┼──────────────
   1   │  0   8 │       1         │   8   │    8  │ h[L]<h[R] → L++
   2   │  1   8 │       7         │   7   │  49 ★ │ h[L]>=h[R] → R--
   3   │  1   7 │       3         │   6   │   18  │ → R--
   4   │  1   6 │       8         │   5   │   40  │ → R--
   5   │  1   5 │       4         │   4   │   16  │ → R--
   6   │  1   4 │       5         │   3   │   15  │ → R--
   7   │  1   3 │       2         │   2   │    4  │ → R--
   8   │  1   2 │       6         │   1   │    6  │ → R--
   ─── │  1   1 │       stop      │       │       │

Đáp án: 49 (cặp cột index 1 và 8, cao 8 và 7).

Code Python 3

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0
        while l < r:
            h = min(height[l], height[r])
            best = max(best, h * (r - l))
            # Luôn dịch con trỏ ở phía thấp hơn.
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return best

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

1.6 Rotate Array (LC 189)

Đề bài

Cho mảng nums và một số nguyên không âm k. Hãy xoay mảng sang phải k bước.

Ví dụ

Input:  nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Giải thích: xoay phải 1 bước → [7,1,2,3,4,5,6]; 2 bước → [6,7,1,2,3,4,5]; 3 bước → [5,6,7,1,2,3,4].

Input:  nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — Xoay 1 bước, lặp k lần — O(n·k). TLE.

Mảng phụ — O(n) time, O(n) space. new[(i + k) % n] = nums[i], rồi copy new về nums. Đơn giản nhưng vi phạm follow-up O(1) space.

Tối ưu — Three Reverses, O(n) time, O(1) extra space. Quan sát ví dụ với n = 7, k = 3: - Reverse toàn bộ: [7, 6, 5, 4, 3, 2, 1]. - Reverse [0..k-1]: [5, 6, 7, 4, 3, 2, 1]. - Reverse [k..n-1]: [5, 6, 7, 1, 2, 3, 4]. ✓

Trực giác: Khi reverse toàn bộ, phần “đáng lẽ ra cuối” giờ đứng đầu nhưng bị đảo ngược. Hai lần reverse con tiếp theo “sửa” lại thứ tự bên trong mỗi khối.

Hình minh hoạ với n = 7, k = 3:

Input         :  [ 1   2   3   4 │ 5   6   7 ]
                                  ▲
                  k=3 phần tử cuối cần "nhảy" lên đầu

──────────────────────────────────────────────────

Bước 1: reverse toàn bộ [0..6]
                  ◀═══════════════════════════▶
                 [ 7   6   5   4   3   2   1 ]
                   ↑               ↑
                  (5,6,7 đảo)     (1,2,3,4 đảo)

Bước 2: reverse [0..k-1] = [0..2]   (sửa lại 3 phần tử đầu)
                  ◀═══════▶
                 [ 5   6   7 │ 4   3   2   1 ]
                                ↑
                  3 phần tử đầu  4 phần tử cuối vẫn đảo
                  đã đúng        cần sửa tiếp

Bước 3: reverse [k..n-1] = [3..6]   (sửa lại 4 phần tử cuối)
                              ◀═══════════════▶
                 [ 5   6   7 │ 1   2   3   4 ]   ← đáp án ✓

Code Python 3

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n  # luôn normalize trước

        def reverse(left: int, right: int) -> None:
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n - 1)        # đảo toàn bộ
        reverse(0, k - 1)        # đảo phần đầu (k phần tử)
        reverse(k, n - 1)        # đảo phần đuôi

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Array decision checklist (trước khi viết code)

Câu hỏi Nếu YES Nếu NO
Cho phép mutate input không? In-place (Move Zeroes, Rotate) Tạo array kết quả
Cần giữ thứ tự gốc? Two-pointer cùng chiều Có thể swap tự do
Trả về index hay value? Cẩn thận khi sort: lưu (value, index) —
Có số 0 / số âm? Product Except Self không dùng được division Có thể prefix×suffix bình thường
Cần O(1) bộ nhớ? 3-reverse trick, in-place marker Có thể dùng hash/extra array

Cửa ngõ sang pattern khác

Recap Rotate Array — so sánh 3 cách

Cách Time Space Khi nào chọn
Extra array O(n) O(n) Dễ viết, ít bug nhất; khi RAM dư
3-reverse O(n) O(1) Mặc định trong phỏng vấn — đẹp & ngắn
Cyclic replacement (GCD) O(n) O(1) Khi interviewer hỏi follow-up “không reverse”

Chương 2 — String

Chuỗi thực ra là mảng các ký tự — tất cả kỹ thuật ở Chương 1 (two pointers, in-place, prefix) đều áp dụng được. Tuy nhiên, string có 2 đặc thù riêng: (i) phải xử lý bảng mã (chỉ ASCII hay full Unicode?), và (ii) trong Python, chuỗi là immutable — không sửa được tại chỗ, mọi thao tác “đổi ký tự” thực ra phải chuyển sang list rồi ''.join.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Template code

from collections import Counter
from typing import List

def two_pointers_in_string(s: str) -> bool:
    """Mẫu two pointers: kiểm tra điều kiện đối xứng / cặp."""
    l, r = 0, len(s) - 1
    while l < r:
        if not check(s[l], s[r]):
            return False
        l += 1
        r -= 1
    return True


def count_chars(s: str) -> dict[str, int]:
    """Bảng đếm ký tự — gần như mọi bài string đều dùng."""
    return Counter(s)

Bài tự luyện cuối chương

2.1 Valid Anagram (LC 242)

Đề bài

Cho hai chuỗi s và t. Trả về True nếu t là anagram của s (cùng các ký tự, cùng số lần xuất hiện, chỉ khác thứ tự), ngược lại False.

Ví dụ

Input:  s = "anagram", t = "nagaram"
Output: True

Input:  s = "rat", t = "car"
Output: False

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — sắp xếp, O(n log n). sorted(s) == sorted(t). Code 1 dòng, nhưng O(n log n) về thời gian và O(n) về bộ nhớ (vì sorted trả về list).

Tối ưu — Counter một lượt, O(n). Đếm ký tự trong s, sau đó duyệt t và trừ. Nếu có ký tự nào âm hoặc kết thúc với mọi count = 0 → đúng anagram.

Tối ưu hơn nữa — bảng cố định 26 phần tử, O(1) extra space (theo bảng mã). Vì chỉ có 26 chữ cái, ta dùng int[26] (hoặc list 26 phần tử) thay cho dict. Bộ nhớ thực tế là O(1) (không phụ thuộc n).

Code Python 3

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return Counter(s) == Counter(t)


class SolutionFast:
    """Bảng cố định 26 chữ cái — O(1) bộ nhớ thực tế."""
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        for ch in t:
            count[ord(ch) - ord('a')] -= 1
            if count[ord(ch) - ord('a')] < 0:
                return False
        return True

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

2.2 Valid Palindrome (LC 125)

Đề bài

Cho chuỗi s. Coi là palindrome nếu sau khi chuyển toàn bộ chữ in hoa → thường và bỏ tất cả ký tự không phải chữ-và-số thì chuỗi đọc xuôi và ngược giống nhau. Trả về True / False.

Ví dụ

Input:  s = "A man, a plan, a canal: Panama"
Output: True
Giải thích: sau lọc → "amanaplanacanalpanama" — đọc xuôi và ngược giống nhau.

Input:  s = "race a car"
Output: False
Giải thích: sau lọc → "raceacar" — không palindrome.

Input:  s = " "
Output: True
Giải thích: chuỗi rỗng coi là palindrome.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — lọc rồi so sánh đảo ngược — O(n) time, O(n) space. filtered = ''.join(ch.lower() for ch in s if ch.isalnum()), rồi filtered == filtered[::-1]. Đơn giản, nhưng tốn O(n) bộ nhớ phụ.

Tối ưu — Two pointers in-place — O(n) time, O(1) space. Hai con trỏ l (đầu) và r (cuối), bỏ qua ký tự không phải alphanumeric ở mỗi bên, rồi so sánh s[l].lower() == s[r].lower(). Nếu khác → False.

Code Python 3

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

2.3 Longest Common Prefix (LC 14)

Đề bài

Cho mảng các chuỗi strs. Hãy trả về tiền tố chung dài nhất. Nếu không có tiền tố chung, trả về "".

Ví dụ

Input:  strs = ["flower", "flow", "flight"]
Output: "fl"

Input:  strs = ["dog", "racecar", "car"]
Output: ""
Giải thích: không có ký tự nào chung ngay từ vị trí đầu.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Vertical scan, O(S) với S là tổng độ dài. Duyệt từng vị trí cột i = 0, 1, 2, .... Tại mỗi i, kiểm tra ký tự strs[0][i] có khớp với strs[j][i] cho mọi j không. Nếu có chuỗi nào hết hoặc khác → trả về strs[0][:i].

Cách 2 — Horizontal scan. Lấy prefix = strs[0], sau đó với mỗi chuỗi tiếp theo, rút ngắn prefix cho đến khi nó là tiền tố của chuỗi đó.

Cách 3 — Sort + so sánh 2 đầu, O(n log n · L). Sort mảng theo thứ tự lexicographic. Tiền tố chung dài nhất chính là tiền tố chung của strs[0] và strs[-1]. Hay nhưng không tối ưu time.

Mình giới thiệu vertical scan vì nó là cách dễ nhất để diễn đạt trên whiteboard và có thể early-exit ngay khi gặp mismatch đầu tiên.

Code Python 3

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        for i, ch in enumerate(strs[0]):
            for s in strs[1:]:
                if i >= len(s) or s[i] != ch:
                    return strs[0][:i]
        return strs[0]  # toàn bộ strs[0] là tiền tố chung

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

2.4 String to Integer / atoi (LC 8)

Đề bài

Cài đặt hàm atoi (ASCII to Integer) chuyển một chuỗi thành số nguyên 32-bit có dấu. Quy tắc:

  1. Bỏ qua khoảng trắng đầu chuỗi.
  2. Đọc dấu + hoặc - (tuỳ chọn).
  3. Đọc các ký tự số liên tiếp cho đến khi gặp ký tự không phải số.
  4. Áp dấu vào kết quả.
  5. Clamp vào phạm vi int 32-bit: [-2^31, 2^31 - 1].
  6. Trả về 0 nếu không đọc được số nào (ví dụ chuỗi toàn chữ).

Ví dụ

Input:  s = "42"
Output: 42

Input:  s = "   -42"
Output: -42                (bỏ space đầu, đọc dấu '-', rồi đọc "42")

Input:  s = "4193 with words"
Output: 4193               (dừng tại khoảng trắng sau "4193"; phần "with words" bị bỏ)

Input:  s = "words and 987"
Output: 0                  (gặp 'w' đầu tiên ngay sau khi bỏ space → không đọc được số nào)

Input:  s = "-91283472332"
Output: -2147483648        (= INT_MIN, clamp vì -91283472332 < -2^31)

Input:  s = "+-12"
Output: 0                  (đã đọc dấu '+', sau đó gặp '-' không phải digit → fail ngay)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Quy trình tuần tự, dùng index chạy qua chuỗi. 4 bước rõ ràng: skip space → đọc dấu → đọc số → clamp. Mỗi bước có biến trạng thái riêng.

Cách 2 — Finite State Machine (FSM). Mô hình trạng thái giúp code gọn hơn và dễ mở rộng khi đề bài thêm yêu cầu (số thực, scientific notation, …). Rất đáng học vì đây là pattern chung cho mọi bài parser (Chương 32).

Hình minh hoạ FSM:

       blank        sign        digit       khác
   ┌───────────────────────────────────────────────┐
S  │  start  →  start    signed   in_number   end │
T  │  signed →  end      end      in_number   end │
A  │ in_num  →  end      end      in_number   end │
T  │  end    →  end      end      end         end │
E  └───────────────────────────────────────────────┘

Trạng thái:
  start     : đang skip space đầu
  signed    : đã đọc 1 dấu, chờ digit
  in_number : đang đọc các chữ số
  end       : đã kết thúc, mọi ký tự sau bị ignore

Code Python 3

INT_MAX = 2**31 - 1   # 2147483647
INT_MIN = -2**31      # -2147483648

class Solution:
    """Cách 1 — quy trình tuần tự."""

    def myAtoi(self, s: str) -> int:
        i, n = 0, len(s)

        # 1. Bỏ space đầu.
        while i < n and s[i] == ' ':
            i += 1

        # 2. Đọc dấu (tuỳ chọn).
        sign = 1
        if i < n and s[i] in '+-':
            sign = -1 if s[i] == '-' else 1
            i += 1

        # 3. Đọc các chữ số.
        result = 0
        while i < n and s[i].isdigit():
            result = result * 10 + (ord(s[i]) - ord('0'))
            # Tối ưu: có thể early-clamp ngay đây để khỏi overflow.
            if result > 2**31:   # vượt rất nhiều
                break
            i += 1

        # 4. Áp dấu và clamp.
        result *= sign
        return max(INT_MIN, min(INT_MAX, result))


class SolutionFSM:
    """Cách 2 — Finite State Machine. Dễ extend khi đề thêm yêu cầu."""

    table = {
        'start':     {'blank': 'start',  'sign': 'signed',   'digit': 'in_num', 'other': 'end'},
        'signed':    {'blank': 'end',    'sign': 'end',      'digit': 'in_num', 'other': 'end'},
        'in_num':    {'blank': 'end',    'sign': 'end',      'digit': 'in_num', 'other': 'end'},
        'end':       {'blank': 'end',    'sign': 'end',      'digit': 'end',    'other': 'end'},
    }

    @staticmethod
    def _kind(ch: str) -> str:
        if ch == ' ':           return 'blank'
        if ch in '+-':          return 'sign'
        if ch.isdigit():        return 'digit'
        return 'other'

    def myAtoi(self, s: str) -> int:
        state = 'start'
        sign = 1
        result = 0
        for ch in s:
            state = self.table[state][self._kind(ch)]
            if state == 'in_num':
                result = result * 10 + int(ch)
                result = min(result, INT_MAX + 1)  # chặn overflow sớm
            elif state == 'signed':
                sign = -1 if ch == '-' else 1
            elif state == 'end':
                break
        return max(INT_MIN, min(INT_MAX, sign * result))

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

2.5 Group Anagrams (LC 49)

Đề bài

Cho mảng chuỗi strs. Hãy gom các chuỗi là anagram của nhau vào cùng một nhóm. Trả về danh sách các nhóm (thứ tự nhóm và thứ tự trong nhóm không quan trọng).

Ví dụ

Input:  strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Ý tưởng cốt lõi: Hai chuỗi là anagram ↔︎ có cùng “chữ ký”. Ta dùng dict {chữ_ký: list các chuỗi} để gom.

Cách 1 — Chữ ký = sorted(s), O(n · k log k). key = ''.join(sorted(s)). Hai anagram sẽ có cùng sorted form.

Cách 2 — Chữ ký = tuple count 26 chữ, O(n · k). key = tuple(Counter(s)[ch] for ch in 'abcdefghijklmnopqrstuvwxyz'). Tránh được phép sort O(k log k) nhưng tuple 26 phần tử có overhead.

Hình minh hoạ với ["eat", "tea", "tan", "ate", "nat", "bat"]:

str    sorted_key   bucket
─────  ───────────  ─────────────────────
"eat"   "aet"  ──┐
"tea"   "aet"  ──┤───►  bucket "aet" = ["eat", "tea", "ate"]
"ate"   "aet"  ──┘
"tan"   "ant"  ──┐
"nat"   "ant"  ──┤───►  bucket "ant" = ["tan", "nat"]
"bat"   "abt"  ──────►  bucket "abt" = ["bat"]

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[str, list[str]] = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            groups[key].append(s)
        return list(groups.values())


class SolutionCount:
    """Chữ ký = tuple count 26 chữ — không cần sort."""

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups: dict[tuple, list[str]] = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for ch in s:
                count[ord(ch) - ord('a')] += 1
            groups[tuple(count)].append(s)
        return list(groups.values())

Phân tích độ phức tạp

Cách Time Space
sorted-key O(n · k log k) O(n·k)
count-key O(n · k) O(n·k)

Với n = số chuỗi, k = độ dài chuỗi.

Bình luận

Bài tự luyện liên quan

2.6 Reverse Words in a String (LC 151)

Đề bài

Cho chuỗi s chứa nhiều từ cách nhau bởi ít nhất 1 dấu cách. Hãy đảo thứ tự các từ và trả về chuỗi kết quả, sao cho:

Ví dụ

Input:  s = "the sky is blue"
Output: "blue is sky the"

Input:  s = "  hello world  "
Output: "hello world"   (gọn space đầu/cuối + giữa)

Input:  s = "a good   example"
Output: "example good a"   (gộp nhiều space giữa thành 1)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Pythonic split-reverse-join, O(n). return ' '.join(reversed(s.split())). split() không tham số sẽ tự gộp nhiều space và bỏ space đầu/cuối — chính xác cái ta cần.

Cách 2 — Three Reverses (in-place trên mảng ký tự). Áp dụng đúng ý tưởng của bài Rotate Array (1.6): 1. Reverse toàn bộ chuỗi. 2. Reverse từng “từ” trong chuỗi đã reverse. 3. Dọn space (chỉ giữ 1 space giữa từ, bỏ space đầu/cuối).

Hình minh hoạ với s = "the sky is blue":

Input               :  "the sky is blue"

Bước 1: reverse toàn bộ
                       "eulb si yks eht"

Bước 2: reverse từng từ trong chuỗi đã đảo
                       "blue is sky the"   ← đáp án ✓

So sánh với Rotate Array: Rotate Array reverse trên đơn vị phần tử, Reverse Words reverse trên đơn vị “từ” (substring giữa các space). Same idea, khác mức trừu tượng.

Code Python 3

class Solution:
    """Cách 1 — Pythonic, ngắn gọn nhất."""

    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))


class SolutionInPlace:
    """Cách 2 — Three reverses, in-place trên list ký tự."""

    def reverseWords(self, s: str) -> str:
        chars = list(s.strip())  # Python string immutable → phải chuyển list

        # 1. Reverse toàn bộ.
        self._reverse(chars, 0, len(chars) - 1)

        # 2. Reverse từng từ.
        start = 0
        for i in range(len(chars) + 1):
            if i == len(chars) or chars[i] == ' ':
                self._reverse(chars, start, i - 1)
                start = i + 1

        # 3. Gộp nhiều space giữa các từ thành 1.
        return self._collapse_spaces(chars)

    @staticmethod
    def _reverse(arr: list, l: int, r: int) -> None:
        while l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1

    @staticmethod
    def _collapse_spaces(chars: list) -> str:
        out, prev_space = [], False
        for ch in chars:
            if ch == ' ':
                if not prev_space and out:
                    out.append(' ')
                prev_space = True
            else:
                out.append(ch)
                prev_space = False
        if out and out[-1] == ' ':
            out.pop()
        return ''.join(out)

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Giả thiết về ký tự — làm rõ ngay trước khi viết code

  1. Bảng chữ cái: lowercase a–z (26)? ASCII 128? Unicode? — Mảng đếm [26] chỉ dùng được khi đúng 26 chữ.
  2. Phân biệt hoa thường? — "Aa" có là palindrome không? LC 125 lowercase trước; LC 5 không.
  3. Có ký tự không phải chữ-và-số? — Lọc bằng isalnum(), hay đề bài đã đảm bảo sạch?
  4. Có khoảng trắng đầu/cuối? — Gọi strip() trước khi parse số.

String pattern map

Pattern Khi gặp Chương
Counting (Counter, [26]) Anagram, frequency 02, 06
Two pointers (in/out) Palindrome, reverse 02, 26
Sliding window Substring với ràng buộc động 27
Parsing với stack/FSM atoi, calculator, Decode 08, 32
Pattern matching strStr, anagrams trong text 35, 36, 34
Hashing string Rabin-Karp, Distinct substrings 34

Group Anagrams — chọn key thế nào?

Bridge sang Chương 32 (String Parser)

LC 8 (atoi) là FSM nhỏ (4 trạng thái: start, sign, digits, overflow). Khi đề bài phức tạp hơn (Valid Number, Calculator) → đọc Chương 32.

Chương 3 — Recursion

Recursion (đệ quy) là ngôn ngữ tự nhiên để mô tả bài toán có cấu trúc tự tương tự — giải bài lớn bằng cách kết hợp lời giải của vài bài con nhỏ hơn. Chương này dạy bạn cảm nhận 3 thành phần của một lời giải đệ quy: (i) base case (điều kiện dừng), (ii) recursive case (gọi vào bài con nhỏ hơn), (iii) kết hợp kết quả từ các bài con. Khi 3 cái này “click”, bạn sẽ thấy DP, Backtracking, Tree, Graph DFS đều là cùng một ngôn ngữ.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

3 câu hỏi cần trả lời trước khi code đệ quy: 1. Trạng thái của hàm gồm những biến gì? (Cần đủ để định nghĩa “bài con”.) 2. Base case là gì? (Khi nào trả về luôn?) 3. Bước đệ quy chia bài lớn thành bài con thế nào, kết hợp kết quả ra sao?

Template code

from functools import cache

# 1) Đệ quy "thuần" (có thể chậm vì lặp lại bài con).
def recurse(state):
    if base_condition(state):
        return base_value
    result = combine(recurse(subproblem_1(state)),
                     recurse(subproblem_2(state)))
    return result


# 2) Top-down DP: thêm cache để O(số trạng thái).
@cache
def f(*state):
    if base_condition(*state):
        return base_value
    return combine(f(*sub1(*state)), f(*sub2(*state)))


# 3) Backtracking: liệt kê + undo.
def backtrack(path, choices):
    if is_solution(path):
        results.append(path.copy())
        return
    for c in choices:
        if not valid(c, path):
            continue
        path.append(c)
        backtrack(path, next_choices(choices, c))
        path.pop()              # undo — đặc trưng của backtracking

Bài tự luyện cuối chương

3.1 Fibonacci số thứ n (LC 509)

Đề bài

Tính số Fibonacci thứ n theo định nghĩa: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với n >= 2.

Ví dụ

Input:  n = 2  → 1
Input:  n = 3  → 2
Input:  n = 10 → 55

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Đệ quy thuần, O(2^n). Mỗi F(n) gọi 2 lần đệ quy. Cây gọi có ~2^n node → rất chậm.

Cách 2 — Memoization (top-down DP), O(n) time, O(n) space. Cache lại kết quả → mỗi F(k) tính đúng 1 lần.

Cách 3 — Iterative (bottom-up), O(n) time, O(1) space. Chỉ cần 2 biến prev, curr cuộn từ dưới lên.

Cách 4 — Matrix exponentiation, O(log n). Khi n lên đến 10^18.

Hình minh hoạ — cây gọi đệ quy cho F(5):

                F(5)
              /      \
          F(4)        F(3)
         /    \      /    \
       F(3)  F(2) F(2)   F(1)
       /  \   / \  / \
     F(2) F(1)...   ...   ← F(3), F(2), F(1) bị tính LẠI nhiều lần

→ Nếu memo cache mỗi F(k), số subproblem chỉ là n+1 (n=5 → 6 calls).
→ Nếu không memo, số calls ~ Fibonacci(n+1) ~ φ^n (exponential).

Code Python 3

from functools import cache

class Solution:
    """Cách 3 — iterative O(1) space, đáp án production."""
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        prev, curr = 0, 1
        for _ in range(2, n + 1):
            prev, curr = curr, prev + curr
        return curr


class SolutionMemo:
    """Cách 2 — top-down DP."""
    @cache
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        return self.fib(n - 1) + self.fib(n - 2)


class SolutionMatrix:
    """Cách 4 — Matrix exponentiation, O(log n)."""
    MOD = 10**9 + 7

    def fib(self, n: int) -> int:
        if n < 2:
            return n
        # [[F(n+1), F(n)], [F(n), F(n-1)]] = [[1,1],[1,0]] ^ n
        result, base = [[1, 0], [0, 1]], [[1, 1], [1, 0]]
        while n > 0:
            if n & 1:
                result = self._mul(result, base)
            base = self._mul(base, base)
            n >>= 1
        return result[0][1]  # F(n)

    def _mul(self, a, b):
        return [[(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % self.MOD,
                 (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % self.MOD],
                [(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % self.MOD,
                 (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % self.MOD]]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

3.2 Power(x, n) (LC 50)

Đề bài

Cài đặt hàm tính x^n với x là số thực và n là số nguyên (có thể âm).

Ví dụ

Input:  x = 2.00000, n = 10     → 1024.00000
Input:  x = 2.10000, n = 3      → 9.26100
Input:  x = 2.00000, n = -2     → 0.25

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Nhân tay, O(n). Loop nhân n lần. TLE khi n = 2^31.

Cách 2 — Fast Power (đệ quy / iterative), O(log n).

Quan sát đệ quy: - Nếu n == 0: trả 1. - Nếu n chẵn: x^n = (x^(n/2))^2. - Nếu n lẻ: x^n = x · x^(n-1).

Cho phép n âm: gọi đệ quy với n = -n rồi nghịch đảo.

Hình minh hoạ — cây gọi cho x^10:

                  x^10
                   │ chẵn → (x^5)^2
                   ▼
                  x^5
                   │ lẻ → x · x^4
                   ▼
                  x^4
                   │ chẵn → (x^2)^2
                   ▼
                  x^2
                   │ chẵn → (x^1)^2
                   ▼
                  x^1
                   │ lẻ → x · x^0
                   ▼
                  x^0 = 1

Tổng số phép nhân: ~ 2 log₂(10) ≈ 8  (vs. 10 phép của brute force)

Code Python 3

class Solution:
    """Đệ quy fast power."""

    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / self.myPow(x, -n)
        half = self.myPow(x, n // 2)
        return half * half if n % 2 == 0 else half * half * x


class SolutionIter:
    """Iterative — tránh chiều sâu đệ quy. Đọc bit từ thấp lên cao."""

    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1.0 / x, -n
        result = 1.0
        base = x
        while n > 0:
            if n & 1:
                result *= base
            base *= base
            n >>= 1
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

3.3 Reverse Linked List (đệ quy) (LC 206)

Đề bài

Cho head của một danh sách liên kết đơn. Hãy đảo ngược danh sách và trả về node đầu mới. (Bài này có 2 cách: iterative và đệ quy. Ở chương này tập trung bản đệ quy; bản iterative gặp lại ở Chương 7.)

Ví dụ

Input:  head = 1 → 2 → 3 → 4 → 5 → None  (singly linked list)
Output: 5 → 4 → 3 → 2 → 1 → None

Input:  head = None     (empty list)
Output: None

Ràng buộc

Clarifying questions

Hướng tiếp cận

Ý tưởng đệ quy: - Base case: nếu head là None hoặc head.next là None → trả head. - Đệ quy: gọi reverseList(head.next) để đảo phần đuôi, được node cuối mới (chính là node cuối cũ → đầu mới sau khi đảo). - Kết hợp: lúc này head.next vẫn trỏ tới node cũ ngay sau head (chưa bị thay đổi vì đệ quy chỉ làm với phần đuôi). Ta gán head.next.next = head và head.next = None để khâu head vào cuối danh sách đã đảo.

Hình minh hoạ với 1 → 2 → 3 → None:

Gọi reverseList(1):
  reverseList(2):
    reverseList(3):
      base case → return 3            #  3 → None
    # tại đây head=2, head.next=3
    # phần đuôi đã đảo: 3 → None
    # ta cần khâu 2 vào sau 3:
    head.next.next = head              #  3 → 2
    head.next = None                   #  2 → None
    # giờ chuỗi: 3 → 2 → None, đầu mới = 3
    return 3
  # tại đây head=1, head.next=2
  # phần đuôi đã đảo: 3 → 2 → None
  # khâu 1 vào sau 2:
  head.next.next = head                #  2 → 1
  head.next = None                     #  1 → None
  # giờ chuỗi: 3 → 2 → 1 → None
  return 3

Code Python 3

class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode | None' = None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Phân tích độ phức tạp

Bình luận

prev = None
while head:
    nxt = head.next
    head.next = prev
    prev = head
    head = nxt
return prev

Bài tự luyện liên quan

3.4 Generate Parentheses (LC 22)

Đề bài

Cho số nguyên n, sinh tất cả các chuỗi dấu ngoặc đúng (well-formed) độ dài 2n.

Ví dụ

Input:  n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Input:  n = 1
Output: ["()"]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Ý tưởng: Sinh ký tự ( hoặc ) từng bước. Mỗi bước có 2 lựa chọn, nhưng phải đảm bảo tính hợp lệ: - Số ( đã đặt không vượt quá n. - Số ) đã đặt không vượt quá số ( đã đặt (vì sẽ tạo ngoặc không match).

Đệ quy với 2 counter: open_count, close_count. Khi len(path) == 2n → đẩy vào kết quả.

Hình minh hoạ — cây quyết định cho n = 2:

                       ""
                     /    \
                ( /        \ )  ✗ (close > open)
                   "("
                  /   \
              ( /      \ )
              "(("    "()"
               │        │
            ) ▼     ( / \ )  ✗
              "(()"   "()("
               │       │
            ) ▼     ) ▼
              "(())" ★  "()()" ★

Đáp án: ["(())", "()()"]
(✗ = nhánh bị cắt vì không hợp lệ)

Code Python 3

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result: list[str] = []

        def backtrack(path: list[str], open_cnt: int, close_cnt: int) -> None:
            if len(path) == 2 * n:
                result.append(''.join(path))
                return
            if open_cnt < n:
                path.append('(')
                backtrack(path, open_cnt + 1, close_cnt)
                path.pop()
            if close_cnt < open_cnt:
                path.append(')')
                backtrack(path, open_cnt, close_cnt + 1)
                path.pop()

        backtrack([], 0, 0)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

3.5 Permutations (LC 46)

Đề bài

Cho mảng nums các số phân biệt, trả về tất cả hoán vị có thể của chúng.

Ví dụ

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Ý tưởng: Tại mỗi bước, chọn 1 số chưa dùng đẩy vào path. Khi path đủ n phần tử → 1 hoán vị hoàn chỉnh.

2 cách quản lý “đã dùng”: - Mảng used: bool[n]. - Hoặc dùng set các index đã dùng.

Hình minh hoạ — cây quyết định cho [1, 2, 3]:

                          [ ]
              ┌────────────┼────────────┐
            [1]           [2]          [3]
           /   \         /   \         /  \
        [1,2] [1,3]   [2,1] [2,3]   [3,1] [3,2]
          │     │       │     │       │     │
       [1,2,3][1,3,2] [2,1,3][2,3,1][3,1,2][3,2,1]

Tổng: 3 · 2 · 1 = 6 hoán vị.

Code Python 3

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        n = len(nums)
        used = [False] * n
        path: list[int] = []

        def backtrack() -> None:
            if len(path) == n:
                result.append(path.copy())
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return result


class SolutionSwap:
    """Cách 2 — swap in-place, không cần mảng used."""

    def permute(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []

        def backtrack(start: int) -> None:
            if start == len(nums):
                result.append(nums.copy())
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # undo

        backtrack(0)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

3.6 Subsets (LC 78)

Đề bài

Cho mảng nums các số phân biệt. Trả về tất cả tập con có thể của nums (bao gồm tập rỗng và tập đầy đủ). Tổng cộng 2^n tập con.

Ví dụ

Input:  nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Input:  nums = [0]
Output: [[], [0]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Có 3 cách kinh điển, đều nên biết.

Cách 1 — Backtracking “chọn / không chọn”. Tại mỗi index i, có 2 nhánh: thêm nums[i] vào path hoặc bỏ qua.

Cách 2 — Backtracking “bắt đầu từ start”. Mỗi node trong cây gọi result.append(path.copy()) (mọi prefix đều là tập con hợp lệ), rồi loop for i in range(start, n).

Cách 3 — Bit Mask iteration. Mỗi số từ 0 đến 2^n - 1 đại diện cho 1 tập con: bit i bật ↔︎ nums[i] trong tập. (Xem thêm Chương 21.)

Hình minh hoạ — cây “chọn / không chọn” cho [1, 2, 3]:

                            [ ]
                bỏ 1 /          \ chọn 1
                  [ ]             [1]
            bỏ 2 / \ chọn 2     bỏ 2 / \ chọn 2
                [ ] [2]            [1] [1,2]
          bỏ3/\ ... ...          ...  ...
           [ ] [3]

Mỗi LÁ của cây = 1 tập con. Cây có 2^3 = 8 lá.

Code Python 3

from typing import List

class Solution:
    """Cách 2 — gom mọi prefix là 1 tập con."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            result.append(path.copy())          # mọi state đều là một subset
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result


class SolutionBitmask:
    """Cách 3 — iterate qua 2^n bitmask."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        for mask in range(1 << n):
            subset = [nums[i] for i in range(n) if mask & (1 << i)]
            result.append(subset)
        return result


class SolutionPick:
    """Cách 1 — backtracking chọn / không chọn."""

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def backtrack(i: int) -> None:
            if i == len(nums):
                result.append(path.copy())
                return
            # nhánh không chọn nums[i]
            backtrack(i + 1)
            # nhánh chọn nums[i]
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

        backtrack(0)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Recursion vs DFS vs Backtracking vs Top-down DP

Thuộc tính Recursion DFS Backtracking Top-down DP
Mục tiêu Giải bài con tự gọi lại Duyệt graph/tree Liệt kê tất cả lời giải Giải tối ưu / đếm
Có undo state? Không bắt buộc Hiếm Bắt buộc (choose/unchoose) Không
Có memo? Có thể có Hiếm Hiếm (state phụ thuộc đường đi) Bắt buộc
Ví dụ Factorial, Fibonacci Number of Islands Permutations, N-Queens LCS, Coin Change

Mantra backtracking

def backtrack(path, choices):
    if is_goal(path):
        record(path); return
    for c in choices:
        if not feasible(path, c): continue
        path.append(c)          # choose
        backtrack(path, ...)    # explore
        path.pop()              # unchoose

Python recursion caveats

Chương 4 — Sorting

Sort tự nó là bài toán đã giải. Chương này không dạy bạn cài đặt quicksort — Python đã có sorted() rất tốt (Timsort, O(n log n) worst, stable). Cái cần học là: khi nào sort là tiền đề giải bài, và bí mật nằm ở hàm so sánh (comparator) tuỳ biến và việc duyệt mảng đã sort bằng pattern two pointers / sweep line.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

3 câu hỏi vàng: 1. Sort theo khoá nào? start, end, length, freq, ratio? 2. Sort xong duyệt thế nào? one-pass / two pointers / sweep line / heap? 3. Cần stable không? Python sorted mặc định là stable — đây là tài sản quý.

Template code

from functools import cmp_to_key
from typing import List

# 1) Sort theo khoá đơn giản
nums.sort(key=lambda x: x[0])

# 2) Sort theo nhiều khoá (tie-breaker)
nums.sort(key=lambda x: (x[0], -x[1]))    # x[0] tăng, x[1] giảm

# 3) Sort theo comparator tuỳ biến
def cmp(a, b) -> int:
    if a + b > b + a:   return -1   # a đứng trước
    if a + b < b + a:   return  1   # b đứng trước
    return 0
arr.sort(key=cmp_to_key(cmp))

# 4) Sweep line trên mảng các sự kiện
events = [(start, +1), (end, -1)]
events.sort()

Bài tự luyện cuối chương

4.1 Sort Colors / Dutch National Flag (LC 75)

Đề bài

Cho mảng nums chỉ chứa các giá trị 0, 1, 2 (đại diện cho 3 màu). Hãy sắp xếp nums sao cho cùng màu đứng cạnh nhau theo thứ tự 0 → 1 → 2. Phải làm in-place, không được dùng hàm sort của ngôn ngữ.

Ví dụ

Input:  nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Input:  nums = [2, 0, 1]
Output: [0, 1, 2]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Counting sort 2 lượt, O(n). Đếm số lượng 0, 1, 2 rồi ghi đè lại. Đơn giản nhưng đi 2 lượt.

Cách 2 — Dutch National Flag (Edsger Dijkstra), 1 lượt, O(n).

Giữ 3 con trỏ: - lo = ranh giới phải của vùng 0s (mọi phần tử ở [0..lo-1] là 0). - hi = ranh giới trái của vùng 2s (mọi phần tử ở [hi+1..n-1] là 2). - mid = con trỏ duyệt giữa hai vùng.

Bất biến: [0..lo-1] = 0, [lo..mid-1] = 1, [mid..hi] chưa xử lý, [hi+1..n-1] = 2.

Tại mỗi bước: - nums[mid] == 0 → swap với nums[lo], lo++, mid++. - nums[mid] == 1 → đã đúng vùng, mid++. - nums[mid] == 2 → swap với nums[hi], hi-- (mid không tăng vì giá trị mới từ hi xuống chưa được xử lý).

Hình minh hoạ với nums = [2, 0, 2, 1, 1, 0]:

                  lo  mid          hi
Khởi tạo  :  [ 2,  0,  2,  1,  1,  0 ]
                ↑   ↑                ↑
              lo=0 mid=0           hi=5

mid=0: nums[0]=2 → swap(0,5), hi--
              [ 0,  0,  2,  1,  1,  2 ]
                ↑   ↑           ↑
              lo=0 mid=0      hi=4

mid=0: nums[0]=0 → swap(lo,mid)=swap(0,0), lo++, mid++
              [ 0,  0,  2,  1,  1,  2 ]
                    ↑   ↑       ↑
                  lo=1 mid=1  hi=4

mid=1: nums[1]=0 → swap(1,1), lo++, mid++
              [ 0,  0,  2,  1,  1,  2 ]
                        ↑   ↑   ↑
                       lo=2 mid=2 hi=4

mid=2: nums[2]=2 → swap(2,4), hi--
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑   ↑   ↑
                       lo=2 mid=2 hi=3

mid=2: nums[2]=1 → mid++
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑       ↑
                       lo=2 mid=3 hi=3

mid=3: nums[3]=1 → mid++
              [ 0,  0,  1,  1,  2,  2 ]
                        ↑           ↑
                       lo=2  mid=4 hi=3   ← mid > hi → dừng

Kết quả : [0, 0, 1, 1, 2, 2]  ✓

Code Python 3

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        lo, mid, hi = 0, 0, len(nums) - 1
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:  # nums[mid] == 2
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1
                # KHÔNG tăng mid — giá trị từ hi chưa biết là gì

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

4.2 Merge Intervals (LC 56)

Đề bài

Cho mảng các khoảng intervals[i] = [start_i, end_i]. Hãy gộp tất cả các khoảng giao nhau lại thành các khoảng không giao nhau, và trả về kết quả.

Ví dụ

Input:  intervals = [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Giải thích: [1,3] và [2,6] giao nhau → gộp thành [1,6].

Input:  intervals = [[1,4], [4,5]]
Output: [[1,5]]
Giải thích: [1,4] và [4,5] coi là giao (chia sẻ điểm 4).

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force. Lặp đi lặp lại tìm cặp giao nhau và gộp. O(n²) hoặc tệ hơn.

Tối ưu — Sort + 1 lượt — O(n log n).

Sort theo start tăng dần. Sau đó duyệt, giữ last = khoảng cuối cùng đã thêm vào kết quả. Với khoảng cur tiếp theo: - Nếu cur.start <= last.end → giao nhau, mở rộng last.end = max(last.end, cur.end). - Nếu không → push cur thành khoảng mới.

Hình minh hoạ với [[1,3], [2,6], [8,10], [15,18]]:

Trục số:
   1   3   5   7   9  11  13  15  17  19
   |   |   |   |   |   |   |   |   |   |
   ├───┤                                       [1,3]
       ├──────────┤                            [2,6]
                       ├───┤                   [8,10]
                                       ├───┤   [15,18]

Sau khi sort theo start: [[1,3], [2,6], [8,10], [15,18]]

Duyệt:
  Push [1,3]                              result = [[1,3]]
  cur=[2,6], 2 <= 3 → mở rộng [1, max(3,6)] = [1,6]
                                           result = [[1,6]]
  cur=[8,10], 8 > 6 → push                result = [[1,6], [8,10]]
  cur=[15,18], 15 > 10 → push             result = [[1,6], [8,10], [15,18]]

Kết quả: [[1,6], [8,10], [15,18]]

Code Python 3

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        result: list[list[int]] = []
        for cur in intervals:
            if result and cur[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], cur[1])
            else:
                result.append(cur[:])   # copy để khỏi share reference
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

4.3 Largest Number (LC 179)

Đề bài

Cho mảng số nguyên không âm nums. Hãy ghép chúng (theo thứ tự nào đó) lại thành một chuỗi sao cho số tạo ra là lớn nhất. Trả về kết quả dưới dạng chuỗi (vì số có thể rất lớn).

Ví dụ

Input:  nums = [10, 2]
Output: "210"

Input:  nums = [3, 30, 34, 5, 9]
Output: "9534330"

Input:  nums = [0, 0]
Output: "0"   (không phải "00")

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — thử mọi hoán vị O(n! · n). TLE khi n đủ lớn.

Tối ưu — Sort với comparator tuỳ biến — O(n log n · L) với L = độ dài tối đa.

Insight: Để quyết định a đứng trước b hay sau, chỉ cần so sánh 2 cách ghép: str(a) + str(b) vs str(b) + str(a) — chuỗi nào lớn hơn thì cách đó “tốt hơn”.

Tại sao đúng? Quan hệ “ghép nào lớn hơn” có tính bắc cầu — chứng minh chặt qua trường hợp Lexicographic của các chuỗi ghép, đảm bảo tồn tại thứ tự sort hợp lệ.

Ví dụ: a = 3, b = 30 → "330" > "303" → 3 đứng trước 30.

Code Python 3

from functools import cmp_to_key
from typing import List

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = [str(x) for x in nums]

        def cmp(a: str, b: str) -> int:
            if a + b > b + a:   return -1   # a đứng trước
            if a + b < b + a:   return  1   # b đứng trước
            return 0

        strs.sort(key=cmp_to_key(cmp))
        result = ''.join(strs)
        # edge case: [0, 0, 0] → tránh ra "000"
        return '0' if result[0] == '0' else result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

4.4 Meeting Rooms II (LC 253)

Đề bài

Cho mảng các khoảng intervals[i] = [start_i, end_i] đại diện cho các cuộc họp. Tìm số phòng tối thiểu cần thiết để chứa tất cả.

(Tức là, tại mọi thời điểm, có tối đa mấy cuộc họp đang diễn ra đồng thời?)

Ví dụ

Input:  intervals = [[0,30], [5,10], [15,20]]
Output: 2
Giải thích: tại t=5, [0,30] và [5,10] cùng diễn ra → cần 2 phòng.

Input:  intervals = [[7,10], [2,4]]
Output: 1
Giải thích: 2 cuộc họp không overlap, 1 phòng dùng được cả 2.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Có 3 cách hay, đều xứng đáng biết:

Cách 1 — Heap (priority queue) — O(n log n).

Sort theo start. Duyệt từng cuộc họp, dùng min-heap chứa end_time của các cuộc đang diễn ra. Khi cuộc mới đến (start): - Nếu heap top có end <= start → cuộc cũ đã xong → pop ra (tái dùng phòng). - Push end của cuộc mới.

Kích thước heap tại mỗi thời điểm = số phòng đang dùng → max của size là đáp án.

Cách 2 — Sweep line / Chronological — O(n log n).

Tạo 2 mảng: starts (đã sort) và ends (đã sort). Duyệt 2 con trỏ: nếu starts[i] < ends[j] → cuộc mới bắt đầu trước cuộc cũ kết thúc → cần thêm phòng (rooms++, i++); ngược lại → giải phóng (i++ thì sao đây — sai). Đúng ra: i++ khi starts[i] < ends[j] và j++ khi starts[i] >= ends[j].

Cách 3 — Event-driven, O(n log n).

Mỗi cuộc tạo 2 sự kiện: (start, +1) và (end, -1). Sort tất cả sự kiện (ưu tiên -1 trước +1 nếu cùng time → ưu tiên đóng phòng). Duyệt và giữ cur/peak.

Hình minh hoạ với [[0,30], [5,10], [15,20]] — heap-based:

Sort by start: [[0,30], [5,10], [15,20]]

Bước 1: cuộc [0,30]    heap = [30]     → rooms = 1
Bước 2: cuộc [5,10]    top=30 > 5 → giữ; push 10  heap = [10, 30]  → rooms = 2 ★
Bước 3: cuộc [15,20]   top=10 <= 15 → pop 10; push 20  heap = [20, 30] → rooms = 2

Trục số:
   0   5  10  15  20  25  30
   |   |   |   |   |   |   |
   ├───────────────────────┤    [0, 30] dùng phòng A
       ├───┤                    [5, 10] dùng phòng B
                ├───┤            [15, 20] tái dùng phòng B

Code Python 3

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap: list[int] = []   # min-heap of end times
        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
        return len(heap)


class SolutionEvents:
    """Cách event-driven — clean cho follow-up."""

    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for s, e in intervals:
            events.append((s, +1))
            events.append((e, -1))
        # Khi cùng time: ưu tiên -1 trước +1 (cuộc kết thúc thì phòng giải phóng trước cuộc mới)
        events.sort(key=lambda x: (x[0], x[1]))

        cur = peak = 0
        for _, delta in events:
            cur += delta
            peak = max(peak, cur)
        return peak

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

4.5 Custom Sort String (LC 791)

Đề bài

Cho hai chuỗi order (toàn các ký tự phân biệt) và s. Hãy sắp xếp lại s sao cho thứ tự các ký tự xuất hiện trong order được tôn trọng. Các ký tự không nằm trong order có thể đặt ở bất cứ đâu trong kết quả.

Ví dụ

Input:  order = "cba", s = "abcd"
Output: "cbad"
Giải thích: trong order, c < b < a. Các ký tự d không xuất hiện trong order
            nên đặt đâu cũng được.

Input:  order = "bcafg", s = "abcd"
Output: "bcad"

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Sort với comparator theo bảng index, O(|s| log |s|).

Tạo dict priority = {ch: i for i, ch in enumerate(order)}. Mỗi ký tự không có trong order cho priority lớn vô cùng (ví dụ 26). Rồi sort s theo priority này.

Cách 2 — Counter + emit theo order, O(|s|).

Đếm Counter(s), sau đó duyệt qua từng ký tự trong order và “in ra” đúng số lần. Cuối cùng nối thêm các ký tự còn lại (không trong order).

Cách 2 không cần sort, nhanh hơn, và rất tự nhiên — interviewer thường mong đợi cách này.

Code Python 3

from collections import Counter

class Solution:
    """Cách 2 — Counter + emit theo order."""

    def customSortString(self, order: str, s: str) -> str:
        cnt = Counter(s)
        parts: list[str] = []
        # 1. Phần các ký tự thuộc order, theo đúng thứ tự order.
        for ch in order:
            if ch in cnt:
                parts.append(ch * cnt.pop(ch))
        # 2. Các ký tự còn lại (không trong order) — thứ tự không quan trọng.
        for ch, c in cnt.items():
            parts.append(ch * c)
        return ''.join(parts)


class SolutionSort:
    """Cách 1 — comparator theo bảng index."""

    def customSortString(self, order: str, s: str) -> str:
        priority = {ch: i for i, ch in enumerate(order)}
        return ''.join(sorted(s, key=lambda ch: priority.get(ch, 26)))

Phân tích độ phức tạp

Cách Time Space
Counter O(|s| + |order|) O(1)
Sort key O(|s| log |s|) O(|s|)

Bình luận

Bài tự luyện liên quan

4.6 Wiggle Sort (LC 280)

Đề bài

Cho mảng nums. Sắp xếp lại để thoả mãn:

nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] <= ...

Tức là vị trí lẻ luôn >= vị trí kề bên trái và phải.

Ví dụ

Input:  nums = [3, 5, 2, 1, 6, 4]
Output: [3, 5, 1, 6, 2, 4]   (một trong nhiều đáp án hợp lệ)

Input:  nums = [6, 6, 5, 6, 3, 8]
Output: [6, 6, 5, 6, 3, 8]   (đã thoả mãn)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Sort rồi swap cặp, O(n log n). Sort tăng dần, sau đó với mỗi cặp (i, i+1) với i lẻ → swap. Bài giải đúng nhưng không tối ưu.

Cách 2 — Greedy 1 lượt, O(n).

Quan sát điều kiện: tại mỗi vị trí i, - Nếu i lẻ (1, 3, 5, …): nums[i] >= nums[i-1]. - Nếu i chẵn (2, 4, 6, …): nums[i] <= nums[i-1].

Duyệt từ i = 1, nếu vi phạm thì swap nums[i] với nums[i-1]. Tại sao swap đảm bảo không phá quan hệ trước đó? Vì ta chỉ sửa phần tử ở vị trí i-1 (làm nó nhỏ hơn hoặc lớn hơn), và quan hệ giữa nums[i-2] và nums[i-1] ở bước trước đã đảm bảo “biên” phù hợp.

Hình minh hoạ với nums = [3, 5, 2, 1, 6, 4]:

Index :   0   1   2   3   4   5
Input :  [3,  5,  2,  1,  6,  4]
            lẻ  chẵn lẻ  chẵn lẻ
            ≥   ≤    ≥   ≤    ≥

i=1 (lẻ):  cần nums[1] >= nums[0]   5 >= 3 ✓
i=2 (chẵn):cần nums[2] <= nums[1]   2 <= 5 ✓
i=3 (lẻ):  cần nums[3] >= nums[2]   1 >= 2 ✗ → swap
           [3, 5, 1, 2, 6, 4]
i=4 (chẵn):cần nums[4] <= nums[3]   6 <= 2 ✗ → swap
           [3, 5, 1, 6, 2, 4]
i=5 (lẻ):  cần nums[5] >= nums[4]   4 >= 2 ✓

Kết quả : [3, 5, 1, 6, 2, 4]  ✓

Code Python 3

from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        for i in range(1, len(nums)):
            should_be_greater = (i % 2 == 1)
            if (should_be_greater and nums[i] < nums[i - 1]) or \
               (not should_be_greater and nums[i] > nums[i - 1]):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Sorting mua gì / mất gì

Mua: - Đưa thứ tự về monotonic → cho phép two-pointer, binary search, sweep. - Hợp nhóm các phần tử “giống nhau” cạnh nhau (anagram, intervals).

Mất: - Mất index gốc → nếu output yêu cầu index, lưu (value, idx) trước. - Mutate input — làm rõ với interviewer trước khi sort. - O(n log n), không miễn phí.

Largest Number (LC 179) — bẫy comparator

Meeting Rooms II — heap vs sweep

Heap Sweep line
Tư duy Phòng nào trống sớm nhất → tái dùng Đếm overlap tại mỗi mốc thời gian
Code heapq + sort theo start Sort events (time, ±1)
Output yêu cầu Số phòng max Số phòng max
Khi mở rộng Dễ trả về schedule (phòng nào lúc nào) Khó trả về schedule

Wiggle Sort: LC 280 vs 324

Binary Search (tìm kiếm nhị phân) tưởng dễ — “chia đôi mảng đã sort” — nhưng thực tế là bug magnet số một trong phỏng vấn. Knuth từng viết: “trong khi ý tưởng đơn giản, viết đúng nó là chuyện khó hơn ta tưởng”. Chương này dạy bạn một template duy nhất áp dụng cho mọi biến thể: tìm equal, tìm boundary, tìm trên rotated, search on answer, … — sẽ gặp lại ở Chương 25 (Advanced Binary Search).

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Mẫu suy nghĩ chuẩn: 1. Không gian tìm kiếm là gì? (index, giá trị, đáp án). 2. Hàm check(mid) trả True/False thế nào? Liệu nó đơn điệu không? 3. Đáp án là ranh giới nào? First True hay last False?

Template code

def lower_bound(nums: list[int], target: int) -> int:
    """Trả về vị trí đầu tiên có nums[i] >= target. Nếu không có, trả về len(nums)."""
    lo, hi = 0, len(nums)        # [lo, hi)  — half-open
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(nums: list[int], target: int) -> int:
    """Trả về vị trí đầu tiên có nums[i] > target."""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def binary_search_answer(check, lo: int, hi: int) -> int:
    """Tìm giá trị nhỏ nhất trong [lo, hi] thoả check(x)=True (check đơn điệu F→T)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Mẹo cuối cùng: mình luôn dùng nửa khoảng đóng-mở [lo, hi) và điều kiện vòng lặp lo < hi. Cách này đồng bộ với bisect của Python và ít bug off-by-one hơn cách lo <= hi.

Bài tự luyện cuối chương

5.1 Binary Search cơ bản (LC 704)

Đề bài

Cho mảng nums đã sort tăng dần và số target. Trả về chỉ số của target trong nums, hoặc -1 nếu không có. Phải chạy O(log n).

Ví dụ

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n). Duyệt tuần tự — không thoả O(log n).

Tối ưu — Binary Search half-open, O(log n).

Duy trì [lo, hi). Tại mỗi vòng: - mid = (lo + hi) // 2. - Nếu nums[mid] == target → trả mid. - Nếu nums[mid] < target → đáp án (nếu có) ở [mid+1, hi) → lo = mid + 1. - Nếu nums[mid] > target → đáp án ở [lo, mid) → hi = mid.

Hình minh hoạ với nums = [-1, 0, 3, 5, 9, 12], target = 9:

index :     0    1    2    3    4    5
nums  :  [ -1,   0,   3,   5,   9,  12 ]

Vòng 1: lo=0, hi=6  → mid=3, nums[3]=5 < 9 → lo = mid+1 = 4
Vòng 2: lo=4, hi=6  → mid=5, nums[5]=12 > 9 → hi = mid = 5
Vòng 3: lo=4, hi=5  → mid=4, nums[4]=9 == 9 → trả 4  ✓

Code Python 3

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)    # [lo, hi)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

5.2 Search Insert Position (LC 35)

Đề bài

Cho mảng nums đã sort, không có duplicate, và target. Trả về: - Chỉ số của target nếu có trong mảng. - Vị trí mà target sẽ được chèn vào nếu không có (giữ mảng vẫn sort).

Phải O(log n).

Ví dụ

Input:  nums = [1, 3, 5, 6], target = 5   → 2
Input:  nums = [1, 3, 5, 6], target = 2   → 1
Input:  nums = [1, 3, 5, 6], target = 7   → 4   (chèn cuối)
Input:  nums = [1, 3, 5, 6], target = 0   → 0   (chèn đầu)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Đây chính là lower_bound! Vị trí đầu tiên có nums[i] >= target — ý nghĩa: “đây là vị trí target sẽ đứng nếu được chèn”.

Code Python 3

from typing import List

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

5.3 First Bad Version (LC 278)

Đề bài

Cho n phiên bản, đánh số từ 1 đến n. Có một phiên bản “bad” và mọi phiên bản sau nó cũng bad. Bạn được cấp hàm API isBadVersion(int) trả True/False. Hãy tìm phiên bản bad đầu tiên với số lần gọi API tối thiểu.

Ví dụ

n = 5, bad version = 4
gọi isBadVersion(3) → False
gọi isBadVersion(5) → True
gọi isBadVersion(4) → True
→ trả 4

Ràng buộc

Clarifying questions

Hướng tiếp cận

Đây là search on monotonic predicate. Pattern hoàn hảo cho template binary_search_answer:

Hình minh hoạ với n = 7, bad = 4:

version :  1     2     3     4     5     6     7
check  :   F     F     F     T     T     T     T
                              ↑
                       cần tìm vị trí này

Vòng 1: lo=1, hi=7  → mid=4, check(4)=T → hi=4
Vòng 2: lo=1, hi=4  → mid=2, check(2)=F → lo=3
Vòng 3: lo=3, hi=4  → mid=3, check(3)=F → lo=4
lo == hi → trả lo = 4  ✓

Code Python 3

def isBadVersion(v: int) -> bool: ...     # API có sẵn

class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo, hi = 1, n      # closed interval [lo, hi]
        while lo < hi:
            mid = lo + (hi - lo) // 2      # tránh overflow ở các ngôn ngữ khác
            if isBadVersion(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

5.4 Find First and Last Position of Element (LC 34)

Đề bài

Cho mảng nums đã sort tăng dần (có thể có duplicate) và target. Trả về [first, last] — chỉ số đầu và cuối của các vị trí target trong mảng. Nếu không có, trả [-1, -1]. Phải O(log n).

Ví dụ

Input:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Input:  nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]

Input:  nums = [], target = 0
Output: [-1, -1]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Dùng 2 lần binary search: - first = lower_bound(target) — vị trí đầu tiên >= target. - last = upper_bound(target) - 1 — vị trí cuối cùng <= target.

Sau đó kiểm tra xem first có hợp lệ và nums[first] == target không.

Hình minh hoạ với nums = [5, 7, 7, 8, 8, 10], target = 8:

index :     0    1    2    3    4    5
nums  :  [  5,   7,   7,   8,   8,  10 ]
                          ↑    ↑
                       first  last

lower_bound(8) = 3   (vị trí đầu tiên >= 8)
upper_bound(8) = 5   (vị trí đầu tiên > 8)
last           = 4   (= upper - 1)

Trả [3, 4]

Code Python 3

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(t: int) -> int:
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < t:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        first = lower_bound(target)
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        last = lower_bound(target + 1) - 1
        return [first, last]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

5.5 Search in Rotated Sorted Array (LC 33)

Đề bài

Cho mảng nums đã sort tăng dần và các giá trị phân biệt, sau đó bị xoay tại một pivot bí ẩn (k lần xoay phải, k chưa biết). Cho target, trả về index hoặc -1. Phải O(log n).

Ví dụ

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

Input:  nums = [1], target = 0
Output: -1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Quan sát then chốt: Khi chia mảng bị rotated tại mid, luôn có ít nhất một nửa ([lo, mid] hoặc [mid, hi]) là sorted đúng (không bị rotate).

Quy trình mỗi vòng: 1. Tính mid. 2. Nếu nums[mid] == target → trả mid. 3. Xác định nửa nào đang sorted: - Nếu nums[lo] <= nums[mid] → nửa trái sorted. - Ngược lại → nửa phải sorted. 4. Kiểm tra target có nằm trong nửa sorted không (so sánh bằng <, >): - Có → search nửa sorted. - Không → search nửa còn lại.

Hình minh hoạ với nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

index :   0    1    2    3    4    5    6
nums  :  [4,   5,   6,   7,   0,   1,   2]
          lo                            hi

Vòng 1: lo=0, hi=6, mid=3, nums[mid]=7
  nums[lo]=4 <= nums[mid]=7 → nửa trái [0..3] = [4,5,6,7] đã sort.
  target=0 nằm trong [4..7]? Không (0 < 4) → đi nửa phải.
  → lo = mid + 1 = 4

Vòng 2: lo=4, hi=6, mid=5, nums[mid]=1
  nums[lo]=0 <= nums[mid]=1 → nửa trái [4..5] = [0,1] đã sort.
  target=0 nằm trong [0..1]? Có → đi nửa trái.
  → hi = mid - 1 = 4

Vòng 3: lo=4, hi=4, mid=4, nums[mid]=0 == target → trả 4  ✓

Code Python 3

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1        # closed interval
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid

            # Nửa trái [lo..mid] đã sort?
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1     # target ở nửa trái
                else:
                    lo = mid + 1
            # Ngược lại: nửa phải [mid..hi] đã sort
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1     # target ở nửa phải
                else:
                    hi = mid - 1

        return -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

5.6 Sqrt(x) (LC 69)

Đề bài

Cho số nguyên không âm x. Trả về căn bậc hai làm tròn xuống của x, tức là số nguyên r lớn nhất sao cho r * r <= x.

Không được dùng hàm built-in sqrt.

Ví dụ

Input:  x = 4   → 2
Input:  x = 8   → 2   (vì 2² = 4 ≤ 8 < 9 = 3²)
Input:  x = 0   → 0
Input:  x = 1   → 1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Binary Search trên đáp án — O(log x).

Tìm số nguyên lớn nhất r thoả r² <= x. Tương đương với “last True” trong dãy đơn điệu [T, T, ..., T, F, F, ...] (T = r² <= x).

Khoảng tìm kiếm: [0, x] (hoặc [0, x//2 + 1] để tiết kiệm).

Cách 2 — Newton’s Method — O(log x) nhưng hằng số nhỏ hơn.

Lặp r = (r + x/r) / 2 cho đến khi r² <= x < (r+1)². Hội tụ rất nhanh (quadratic convergence) — đây là cách sqrt được cài trong nhiều thư viện chuẩn.

Hình minh hoạ — Binary Search cho x = 8:

   r :    0    1    2    3    4    5    6    7    8
  r² :    0    1    4    9   16   25   36   49   64
                    ↑
                last r với r² <= 8

Vòng 1: lo=0, hi=8   mid=4, 16 > 8 → hi = 3
Vòng 2: lo=0, hi=3   mid=1,  1 <= 8 → answer=1, lo=2
Vòng 3: lo=2, hi=3   mid=2,  4 <= 8 → answer=2, lo=3
Vòng 4: lo=3, hi=3   mid=3,  9 > 8 → hi=2  → lo > hi, dừng

Trả 2  ✓

Code Python 3

class Solution:
    """Cách 1 — Binary Search."""

    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        lo, hi = 1, x // 2 + 1
        answer = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                answer = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return answer


class SolutionNewton:
    """Cách 2 — Newton's Method, hằng số nhỏ hơn."""

    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Template invariants (chọn 1 và bám)

Closed interval [lo, hi]:

lo, hi = 0, n - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if check(mid): return mid
    elif too_small(mid): lo = mid + 1
    else: hi = mid - 1
return -1

Half-open [lo, hi) — first-true (lower_bound):

lo, hi = 0, n          # hi không inclusive
while lo < hi:
    mid = (lo + hi) // 2
    if pred(mid): hi = mid
    else: lo = mid + 1
return lo                # vị trí đầu tiên thỏa

Checklist trước khi submit

  1. lo, hi khởi tạo đúng (đặc biệt khi search on answer: lo = min, hi = max hoặc max+1).
  2. Điều kiện vòng lặp khớp với loại interval (<= hay <).
  3. Cập nhật mid+1 / mid-1 / mid đúng — tránh infinite loop.
  4. Trường hợp không tìm thấy trả về cái gì? -1, n, lo?
  5. Overflow (lo + hi) // 2 an toàn ở Python; ở Java/C++ dùng lo + (hi - lo) // 2.

Sqrt overflow note (ngôn ngữ khác)

Python int không tràn. Java/C++: mid * mid có thể tràn int32. Dùng (long) mid * mid hoặc so sánh mid <= x / mid để tránh nhân.

Chương 6 — Hash Table

Hash Table (bảng băm) là “vũ khí thần kỳ” của phỏng vấn coding: nó biến nhiều bài O(n²) thành O(n). Triết lý: đổi bộ nhớ lấy thời gian — chấp nhận thêm O(n) bộ nhớ phụ để có look-up O(1). Chương này dạy bạn nhận diện khi nào nên và khi nào không nên dùng hash, cùng 6 bài kinh điển rất hay gặp ở Big Tech.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Khi không nên dùng hash: - Cần thứ tự sort → dùng SortedSet/TreeMap (Python: sortedcontainers). - Cần O(1) worst-case (không phải amortized) → hash bị adversary tấn công collision. - Khoá là loại phức tạp (list, dict) → phải convert sang tuple/frozenset.

Template code

from collections import Counter, defaultdict
from typing import List

# 1) Counter: đếm tần suất
cnt = Counter(nums)               # {value: count}
top3 = cnt.most_common(3)         # 3 phần tử thường gặp nhất

# 2) defaultdict(list): nhóm theo khoá
groups: dict[str, list[int]] = defaultdict(list)
for i, v in enumerate(arr):
    groups[v].append(i)

# 3) Prefix sum + dict: tìm subarray
prefix_index = {0: -1}            # prefix_sum -> index sớm nhất
cur = 0
for i, x in enumerate(arr):
    cur += x
    if cur - target in prefix_index:
        # tìm thấy subarray có sum = target
        ...
    if cur not in prefix_index:
        prefix_index[cur] = i

Bài tự luyện cuối chương

6.1 Contains Duplicate (LC 217)

Đề bài

Cho mảng nums. Trả về True nếu có ít nhất 1 phần tử xuất hiện ≥ 2 lần, ngược lại False.

Ví dụ

Input:  nums = [1, 2, 3, 1]   → True
Input:  nums = [1, 2, 3, 4]   → False
Input:  nums = []             → False

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). So sánh mọi cặp.

Sort — O(n log n), O(1) extra space. Sort rồi check 2 phần tử kề.

Hash set — O(n) time, O(n) space — đáp án phổ biến nhất.

One-liner Pythonic: return len(set(nums)) != len(nums).

Code Python 3

from typing import List

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen: set[int] = set()
        for x in nums:
            if x in seen:
                return True
            seen.add(x)
        return False

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

6.2 Longest Consecutive Sequence (LC 128)

Đề bài

Cho mảng nums không sort. Trả về độ dài của dãy số liên tiếp (consecutive integers, có thể không đứng cạnh trong mảng) dài nhất. Phải chạy O(n).

Ví dụ

Input:  nums = [100, 4, 200, 1, 3, 2]
Output: 4
Giải thích: dãy [1, 2, 3, 4] dài 4.

Input:  nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Giải thích: dãy [0, 1, 2, 3, 4, 5, 6, 7, 8].

Input:  nums = []
Output: 0

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n³). Với mỗi phần tử, đếm số x, x+1, x+2, ... có trong mảng.

Sort — O(n log n). Sort, đếm dãy liên tiếp. Đơn giản nhưng không thoả O(n).

Tối ưu — Hash Set + “chỉ bắt đầu từ điểm đầu dãy” — O(n).

Insight then chốt: Một số x là điểm bắt đầu dãy ↔︎ x - 1 không có trong mảng. Vậy chỉ với những x thoả điều kiện này, ta mới đếm dãy x, x+1, x+2, ... bằng cách lookup hash. Mỗi phần tử bị “đếm tới” tối đa 1 lần trên toàn quá trình → tổng O(n).

Hình minh hoạ với nums = [100, 4, 200, 1, 3, 2]:

Set: {100, 4, 200, 1, 3, 2}

Duyệt từng x trong set:
  x=100: 99 không có trong set → là điểm bắt đầu
         Đếm: 100 ✓, 101 ✗  → length 1
  x=4:   3 CÓ trong set → SKIP (sẽ được đếm khi bắt đầu từ 1)
  x=200: 199 không có → là điểm bắt đầu
         Đếm: 200 ✓, 201 ✗  → length 1
  x=1:   0 không có → là điểm bắt đầu
         Đếm: 1 ✓, 2 ✓, 3 ✓, 4 ✓, 5 ✗  → length 4  ★
  x=3:   2 CÓ → SKIP
  x=2:   1 CÓ → SKIP

Tổng: max length = 4.

Chìa khoá: mỗi phần tử của dãy 1-2-3-4 chỉ được "duyệt forward" đúng 1 lần
            (khi x=1). Tổng công ~ O(n).

Code Python 3

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        best = 0
        for x in num_set:
            # Chỉ bắt đầu khi x là điểm đầu dãy (x-1 không có).
            if x - 1 not in num_set:
                cur = x
                length = 1
                while cur + 1 in num_set:
                    cur += 1
                    length += 1
                best = max(best, length)
        return best

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

6.3 Top K Frequent Elements (LC 347)

Đề bài

Cho mảng nums và số nguyên k. Trả về k phần tử thường gặp nhất (output order tuỳ ý).

Ví dụ

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

Input:  nums = [1], k = 1
Output: [1]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Counter + sort — O(n log n). Đơn giản nhưng không thoả gợi ý LC.

Cách 2 — Min-heap kích thước k — O(n log k). Duy trì heap kích thước k; khi vượt thì pop phần tử ít tần suất nhất.

Cách 3 — Bucket sort theo frequency — O(n) — xịn nhất.

Frequency tối đa là n → tạo n + 1 bucket, bucket i chứa các phần tử có frequency i. Duyệt bucket từ cao xuống thấp, gom k phần tử.

Hình minh hoạ với nums = [1,1,1,2,2,3], k=2:

Bước 1: Counter → {1:3, 2:2, 3:1}

Bước 2: Bucket sort theo frequency (n=6, có 7 bucket 0..6):
  bucket[0] = []
  bucket[1] = [3]      # số 3 xuất hiện 1 lần
  bucket[2] = [2]      # số 2 xuất hiện 2 lần
  bucket[3] = [1]      # số 1 xuất hiện 3 lần
  bucket[4..6] = []

Bước 3: Duyệt bucket từ index 6 xuống:
  i=6: rỗng
  i=5: rỗng
  i=4: rỗng
  i=3: [1] → result = [1]
  i=2: [2] → result = [1, 2]   đủ k=2, dừng

Output: [1, 2]

Code Python 3

import heapq
from collections import Counter
from typing import List

class Solution:
    """Cách 3 — Bucket sort, O(n)."""

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        n = len(nums)
        buckets: list[list[int]] = [[] for _ in range(n + 1)]
        for x, freq in cnt.items():
            buckets[freq].append(x)
        result: list[int] = []
        for freq in range(n, 0, -1):
            for x in buckets[freq]:
                result.append(x)
                if len(result) == k:
                    return result
        return result


class SolutionHeap:
    """Cách 2 — Min-heap kích thước k, O(n log k)."""

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        # heapq.nlargest dùng heap-based partial sort
        return heapq.nlargest(k, cnt.keys(), key=cnt.get)

Phân tích độ phức tạp

Cách Time Space
Counter + sort O(n log n) O(n)
Min-heap O(n log k) O(n)
Bucket sort O(n) O(n)

Bình luận

Bài tự luyện liên quan

6.4 Subarray Sum Equals K (LC 560)

Đề bài

Cho mảng số nguyên nums và số k. Trả về số lượng subarray (liên tục) có tổng đúng bằng k.

Ví dụ

Input:  nums = [1, 1, 1], k = 2
Output: 2
Giải thích: 2 subarray [1,1] (vị trí 0..1 và 1..2).

Input:  nums = [1, 2, 3], k = 3
Output: 2
Giải thích: [1,2] và [3].

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). Với mỗi i, tính prefix sum dần và check == k. Chấp nhận được nhưng không tối ưu.

Tối ưu — Prefix sum + Hash map — O(n).

Đặt P[i] = tổng nums[0..i-1] (P[0] = 0). Khi đó tổng subarray nums[j..i-1] = P[i] - P[j]. Subarray có tổng k ↔︎ P[i] - P[j] = k ↔︎ P[j] = P[i] - k.

→ Duyệt và đếm số j < i thoả P[j] == cur - k. Dùng dict đếm {prefix_sum: số lần xuất hiện}.

Hình minh hoạ với nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7:

i    :   0    1    2    3    4    5    6    7
nums :   3    4    7    2   -3    1    4    2
P[i+1]:  3    7   14   16   13   14   18   20
                  ↑                   ↑
                P[3]=14            P[7]=18  ←  P[7]-P[3]=4? KHÔNG, =4

Tay xét:
P[]   = [0, 3, 7, 14, 16, 13, 14, 18, 20]
counts = {0:1}                        cur=0
i=0  cur=3   (3-7=-4 not in counts)  add 3 → {0:1, 3:1}
i=1  cur=7   (7-7= 0 in counts: +1)  add 7 → {0:1, 3:1, 7:1}   answer=1
i=2  cur=14  (14-7=7 in counts: +1)  add 14 → ...              answer=2
i=3  cur=16  (16-7=9 not in counts)                            answer=2
i=4  cur=13  (13-7=6 not in counts)                            answer=2
i=5  cur=14  (14-7=7 in counts: +1)  cur cũ đã có → counts[14]+=1
                                                              answer=3
i=6  cur=18  (18-7=11 not in counts)                          answer=3
i=7  cur=20  (20-7=13 in counts: +1)                          answer=4

Đáp án: 4 subarray có tổng = 7.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        counts: dict[int, int] = defaultdict(int)
        counts[0] = 1            # prefix sum 0 đã xuất hiện 1 lần (rỗng)
        cur = 0
        result = 0
        for x in nums:
            cur += x
            result += counts[cur - k]    # bao nhiêu j thoả P[j] = cur - k
            counts[cur] += 1
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

6.5 Isomorphic Strings (LC 205)

Đề bài

Hai chuỗi s và t gọi là đồng cấu (isomorphic) nếu tồn tại một song ánh giữa các ký tự của s và t sao cho thay thế từng ký tự trong s theo ánh xạ đó cho ra t.

Ví dụ

Input:  s = "egg", t = "add"   → True
Giải thích: e→a, g→d (bijection).

Input:  s = "foo", t = "bar"   → False
Giải thích: o phải map cả vào a và r (không là hàm).

Input:  s = "paper", t = "title"   → True

Input:  s = "badc", t = "baba"   → False
Giải thích: d→a và c→a, hai ký tự khác map vào cùng 1 → vi phạm song ánh.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Dùng 2 dict (map cả 2 chiều).

Duyệt cùng lúc 2 chuỗi: - Nếu s[i] đã trong s2t → check s2t[s[i]] == t[i]. - Nếu chưa → kiểm tra t[i] chưa nằm trong t2s (tránh nhiều s map vào cùng 1 t). - Lưu cặp (s[i], t[i]) vào cả 2 dict.

Cách 2 — Thay bằng “first occurrence index”.

Một chuỗi có thể được “chuẩn hoá” bằng cách thay mỗi ký tự bằng vị trí xuất hiện đầu tiên của nó. Hai chuỗi isomorphic ↔︎ chuẩn hoá xong giống nhau.

Ví dụ "egg" → [0, 1, 1], "add" → [0, 1, 1] → bằng nhau → True.

Cách 1 trực quan hơn, cách 2 đẹp về mặt thuật toán. Cả 2 đều O(n).

Code Python 3

class Solution:
    """Cách 1 — 2 dict, kiểm tra song ánh."""

    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        s2t: dict[str, str] = {}
        t2s: dict[str, str] = {}
        for a, b in zip(s, t):
            if a in s2t:
                if s2t[a] != b:
                    return False
            else:
                if b in t2s:        # b đã được map từ ký tự khác
                    return False
                s2t[a] = b
                t2s[b] = a
        return True


class SolutionNormalize:
    """Cách 2 — chuẩn hoá theo first-occurrence index."""

    def isIsomorphic(self, s: str, t: str) -> bool:
        return self._normalize(s) == self._normalize(t)

    @staticmethod
    def _normalize(s: str) -> list[int]:
        idx: dict[str, int] = {}
        out: list[int] = []
        for ch in s:
            if ch not in idx:
                idx[ch] = len(idx)
            out.append(idx[ch])
        return out

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

6.6 LRU Cache (LC 146)

Đề bài

Thiết kế Least Recently Used (LRU) Cache với 2 operations đều O(1):

Ví dụ

Input (LC-style operation arrays):
  ops  = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  args = [[2],        [1,1], [2,2], [1],   [3,3], [2],   [4,4], [1],   [3],   [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Trace từng bước (capacity = 2; cuối phải = MRU, trái = LRU):

  LRUCache(2)         → null;   cache = {}                    (LRU ← → MRU)
  put(1, 1)           → null;   cache = {1=1}
  put(2, 2)           → null;   cache = {1=1, 2=2}
  get(1)              → 1;      cache = {2=2, 1=1}   (1 vừa dùng → MRU)
  put(3, 3)           → null;   cache = {1=1, 3=3}   (evict 2: LRU)
  get(2)              → -1;     (key 2 không còn)
  put(4, 4)           → null;   cache = {3=3, 4=4}   (evict 1)
  get(1)              → -1
  get(3)              → 3;      cache = {4=4, 3=3}
  get(4)              → 4;      cache = {3=3, 4=4}

Ràng buộc

Clarifying questions

Hướng tiếp cận

Yêu cầu cốt lõi: O(1) cho cả get và put ↔︎ cần đồng thời: - Hash map: key → reference đến node (cho O(1) lookup). - Doubly Linked List (DLL): thứ tự truy cập (MRU ở 1 đầu, LRU ở đầu kia). Cho phép xoá node bất kỳ trong O(1) nếu có reference.

Mỗi get(k): - Nếu k trong map → lấy node, di chuyển node lên đầu DLL (= MRU), trả value. - Ngược lại trả -1.

Mỗi put(k, v): - Nếu k đã có → update value, di chuyển lên đầu. - Nếu không → thêm node mới ở đầu. Nếu vượt capacity → xoá node cuối (LRU) và xoá khỏi map.

Cách Pythonic — dùng OrderedDict (đã hỗ trợ sẵn 2 yêu cầu trên):

OrderedDict Python được triển khai bên dưới như hash map kết hợp doubly linked list. Lớp này có 2 method đắt giá cho LRU: move_to_end(key) và popitem(last=False) (pop đầu).

Hình minh hoạ — DLL state qua các operation:

capacity = 2
                    Head (MRU)              Tail (LRU)
                          │                       │
                          ▼                       ▼
put(1,1):   DLL:    1                              cache = {1: node1}
put(2,2):   DLL:    2 ─── 1                       cache = {1: ., 2: .}
get(1)=1:   DLL:    1 ─── 2     (1 → MRU)
put(3,3):   DLL:    3 ─── 1     (xoá 2 vì LRU)
get(2)=-1
put(4,4):   DLL:    4 ─── 3     (xoá 1)
get(1)=-1
get(3)=3:   DLL:    3 ─── 4
get(4)=4:   DLL:    4 ─── 3

Code Python 3

from collections import OrderedDict

class LRUCache:
    """Cách Pythonic — OrderedDict đã có sẵn DLL + hash."""

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)        # đẩy thành MRU (cuối)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # pop LRU ở đầu


# ─────────────────────────────────────────────────────────────
# Phiên bản tự tay (interview-friendly): dict + doubly linked list.
# Trình bày khi interviewer hỏi: "Implement LRU không dùng built-in."

class _Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: int = 0, val: int = 0):
        self.key, self.val = key, val
        self.prev: "_Node | None" = None
        self.next: "_Node | None" = None


class LRUCacheManual:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, _Node] = {}
        # Dùng 2 sentinel head/tail để code rút gọn (không phải check None).
        self.head, self.tail = _Node(), _Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.cache) == self.cap:
            lru = self.tail.prev          # LRU = sát tail
            self._remove(lru)
            del self.cache[lru.key]
        new_node = _Node(key, value)
        self.cache[key] = new_node
        self._add_to_front(new_node)

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Khi hash KHÔNG đủ

Yêu cầu Hash đủ? Thay thế
Lookup O(1), không cần thứ tự ✅ —
Cần thứ tự duyệt ❌ OrderedDict / sorted list
Range query [l, r] ❌ Fenwick / Segment Tree (Chương 22)
Top-k frequent Partial Heap (Chương 15)
Nearest neighbor ❌ Sorted set / BST
Subarray sum có số âm ✅ Prefix sum + hash —
Subarray sum không âm Thường dùng sliding window (27) —

LRU 2 cách

Longest Consecutive — vì sao O(n)?

Chương 7 — Linked List

Linked List (danh sách liên kết) là cấu trúc “đơn giản về lý thuyết, phức tạp về code”. Mỗi node trỏ tới node kế tiếp, vậy thôi — nhưng để code không bug, bạn cần thuộc lòng 5 trick nhỏ: dummy head, two pointers, đảo in-place, split-by-pivot, và phép gắn pointer chéo. Hết chương này, bạn sẽ thấy LL không còn đáng sợ.

Chương này có 12 bài — gấp đôi các chương cơ bản — vì pattern LL có nhiều biến thể quan trọng, từ Easy (Reverse, Merge, Cycle) đến Hard (Reverse k-Group, Sort, Reorder).

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

5 trick phải thuộc lòng:

  1. Dummy head: tạo 1 node giả dummy.next = head, dùng prev = dummy. Tránh hàng tá if head is None.
  2. Two pointers (slow / fast): tìm giữa (1×, 2× tốc độ), phát hiện chu trình (Floyd), tìm offset từ cuối.
  3. Reverse in-place: 3 con trỏ prev / curr / nxt.
  4. Split → process → merge: pattern cho merge-sort, palindrome check, reorder.
  5. Pointer relinking: khi gắn a.next = b, luôn nhớ rời a khỏi vị trí cũ trước (cập nhật cả pointer “đi vào” và “đi ra” của a).

Định dạng input (áp dụng cho TẤT CẢ bài trong chương)

Mọi bài trong chương 7 (và 3.3, 15.5) đều dùng ListNode chuẩn của LeetCode:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Template code

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def use_dummy(head: ListNode | None) -> ListNode | None:
    """Mẫu dummy head — bài hay có chèn/xoá node ở đầu."""
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        # ... thao tác trên prev.next ...
        prev = prev.next
    return dummy.next      # head có thể đã đổi


def find_middle(head: ListNode | None) -> ListNode | None:
    """Slow/fast pointers — tìm middle (LC 876)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def reverse(head: ListNode | None) -> ListNode | None:
    """Reverse iterative — 3 con trỏ."""
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

Bài tự luyện cuối chương

7.1 Reverse Linked List (LC 206) — bản iterative

Đề bài

Cho head của linked list đơn. Đảo ngược danh sách và trả về head mới. (Bài này đã có bản đệ quy ở Chương 3.3 — phần này tập trung vào bản iterative với O(1) space.)

Ví dụ

Input:  head = 1 → 2 → 3 → 4 → 5 → None  (singly linked list)
Output: 5 → 4 → 3 → 2 → 1 → None

Ràng buộc

Clarifying questions

Hướng tiếp cận

3 con trỏ: - prev = node ngay trước curr trong danh sách kết quả. - curr = node đang xử lý. - nxt = sao lưu curr.next trước khi sửa.

Mỗi vòng: lật curr.next về prev, rồi dịch prev, curr về phía trước.

Hình minh hoạ với 1 → 2 → 3 → None:

Bắt đầu :   prev = None
            curr → 1 → 2 → 3 → None
                    
Vòng 1:     nxt = 2
            curr.next = prev   →   None ← 1   2 → 3 → None
            prev = curr = 1, curr = 2

Vòng 2:     nxt = 3
            curr.next = prev   →   None ← 1 ← 2   3 → None
            prev = 2, curr = 3

Vòng 3:     nxt = None
            curr.next = prev   →   None ← 1 ← 2 ← 3
            prev = 3, curr = None  → dừng

Trả prev = 3, danh sách: 3 → 2 → 1 → None

Code Python 3

class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Pythonic 1 dòng inside loop: curr.next, prev, curr = prev, curr, curr.next. Tuple unpacking đánh giá RHS trước, không cần nxt tạm.

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.2 Merge Two Sorted Lists (LC 21)

Đề bài

Cho 2 head của 2 linked list đã sort tăng dần. Trả về head của list gộp lại (cũng sort tăng).

Ví dụ

Input:  l1 = 1 → 2 → 4,  l2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Ràng buộc

Clarifying questions

Hướng tiếp cận

Iterative — dùng dummy head. Tạo dummy và tail = dummy. Mỗi vòng, gắn tail.next vào node nhỏ hơn của 2 list, dịch tail. Cuối cùng gắn phần đuôi còn dư.

Đệ quy (rất gọn nhưng O(n) stack):

if not l1: return l2
if not l2: return l1
if l1.val <= l2.val:
    l1.next = self.mergeTwoLists(l1.next, l2)
    return l1
else:
    l2.next = self.mergeTwoLists(l1, l2.next)
    return l2

Code Python 3

class Solution:
    def mergeTwoLists(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2     # gắn phần đuôi còn dư
        return dummy.next

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.3 Linked List Cycle (LC 141)

Đề bài

Cho head của linked list. Trả về True nếu có chu trình, ngược lại False. Yêu cầu: O(1) extra space.

Ví dụ

Input:  head = [3, 2, 0, -4], cycle bắt đầu ở index 1
        3 → 2 → 0 → -4
            ↑________|
Output: True

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — Hash set, O(n) space. Lưu các node đã thấy.

Tối ưu — Floyd’s Tortoise and Hare, O(1) space.

Hai con trỏ slow (1×) và fast (2×). Nếu có chu trình, fast sẽ “đuổi kịp” slow trong vòng tròn (mỗi bước khoảng cách giữa 2 giảm 1). Nếu không, fast hết đường.

Hình minh hoạ — slow/fast trên chu trình:

Linked list:  3 → 2 → 0 → -4 → ⟲ (về 2)

Bước 0:  slow=3, fast=3
Bước 1:  slow=2, fast=0
Bước 2:  slow=0, fast=2     (fast đã quay vòng)
Bước 3:  slow=-4, fast=-4   ★ gặp nhau → return True

Trên chu trình dài L, slow đi 1 bước, fast đi 2 bước → khoảng cách
giảm 1 mỗi bước → tối đa L bước thì gặp.

Code Python 3

class Solution:
    def hasCycle(self, head: ListNode | None) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.4 Middle of the Linked List (LC 876)

Đề bài

Cho head. Trả về node giữa của linked list. Nếu có 2 node giữa (list chẵn), trả về cái thứ 2.

Ví dụ

Input:  head = 1 → 2 → 3 → 4 → 5     (singly linked list)
Output: node có value 3 (giữa, thuộc về nửa sau khi length chẵn)
Input:  head = 1 → 2 → 3 → 4 → 5 → 6   (singly linked list, length chẵn)
Output: node có value 4 (giữa thứ 2)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — 2 lượt, O(n). Đếm độ dài, rồi đi đến giữa.

Tối ưu — Slow/fast 1 lượt, O(n). Khi fast chạm cuối, slow ở giữa.

Code Python 3

class Solution:
    def middleNode(self, head: ListNode | None) -> ListNode | None:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.5 Remove Nth Node From End of List (LC 19)

Đề bài

Cho head và số n. Xoá node thứ n tính từ cuối (1-indexed) và trả về head có thể đã đổi.

Ví dụ

Input:  1 → 2 → 3 → 4 → 5, n = 2     → 1 → 2 → 3 → 5  (xoá node 4)
Input:  1, n = 1                     → None
Input:  1 → 2, n = 1                 → 1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — 2 lượt. Đếm độ dài L, sau đó xoá node thứ L - n từ đầu.

Tối ưu — 1 lượt, two pointers cách nhau n. - Tạo dummy để xử lý case xoá head. - fast đi n bước trước. - Sau đó slow và fast cùng đi đến khi fast.next is None. Lúc đó slow.next chính là node cần xoá.

Hình minh hoạ với 1 → 2 → 3 → 4 → 5, n = 2:

Bắt đầu:  dummy → 1 → 2 → 3 → 4 → 5 → None
          slow                            
          fast                            

Sau khi fast đi n=2 bước:
          dummy → 1 → 2 → 3 → 4 → 5 → None
          slow        fast              

Cùng đi đến khi fast.next == None:
          dummy → 1 → 2 → 3 → 4 → 5 → None
                          slow      fast

slow.next = 4 → cần xoá. slow.next = slow.next.next.
          dummy → 1 → 2 → 3 → 5 → None  ✓

Code Python 3

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.6 Palindrome Linked List (LC 234)

Đề bài

Cho head của linked list đơn. Trả về True nếu giá trị các node tạo thành chuỗi palindrome. Yêu cầu: O(n) time, O(1) space.

Ví dụ

Input:  head = 1 → 2 → 2 → 1     → Output: True   (palindrome)
Input:  head = 1 → 2             → Output: False  (1 ≠ 2)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — copy ra mảng + two pointers, O(n) space. Đơn giản, nhưng vi phạm O(1) space.

Tối ưu — Split + Reverse half + Compare, O(1) space. 1. Tìm middle (slow/fast). 2. Đảo nửa sau (in-place). 3. So sánh từng node giữa nửa đầu và nửa sau đã đảo. 4. (Optional) Khôi phục nửa sau (trong phỏng vấn thường khỏi cần).

Hình minh hoạ với 1 → 2 → 3 → 2 → 1:

Bước 1: tìm middle (slow ở node 3)
              1 → 2 → 3 → 2 → 1
                      ↑ slow

Bước 2: đảo nửa sau (từ slow.next = 2):
              1 → 2 → 3   1 → 2
              (nửa đầu)   (nửa sau đã đảo)

Bước 3: so sánh từng node:
              1 vs 1 ✓
              2 vs 2 ✓
        → True

Code Python 3

class Solution:
    def isPalindrome(self, head: ListNode | None) -> bool:
        # 1. Tìm middle.
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Đảo nửa sau (bắt đầu từ slow).
        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        # 3. So sánh.
        left, right = head, prev
        while right:    # nửa sau đã đảo có thể ngắn hơn 1 node
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.7 Add Two Numbers (LC 2)

Đề bài

Cho 2 linked list đại diện 2 số nguyên không âm, digits lưu ngược (digit hàng đơn vị ở head). Trả về linked list = tổng 2 số (cũng theo dạng ngược).

Ví dụ

Input:  l1 = 2 → 4 → 3   (đại diện 342)
        l2 = 5 → 6 → 4   (đại diện 465)
Output: 7 → 0 → 8         (đại diện 807 = 342 + 465)

Input:  l1 = 9 → 9 → 9 → 9 → 9 → 9 → 9
        l2 = 9 → 9 → 9 → 9
Output: 8 → 9 → 9 → 9 → 0 → 0 → 0 → 1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Mô phỏng cộng “tay”: đi đồng thời 2 list, giữ biến carry. Mỗi vòng: - total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry - digit = total % 10, carry = total // 10. - Push digit vào kết quả; dịch l1, l2.

Vòng lặp dừng khi cả 2 cạn và carry == 0.

Code Python 3

class Solution:
    def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        carry = 0
        while l1 or l2 or carry:
            total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return dummy.next

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.8 Copy List with Random Pointer (LC 138)

Đề bài

Cho linked list mà mỗi node ngoài next còn có random — trỏ tới node bất kỳ trong list (hoặc None). Hãy deep copy danh sách (mỗi node mới là 1 instance riêng, các random trỏ đúng vào node mới tương ứng).

Ví dụ

Input (LC-style):
  head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
  (mỗi phần tử [val, random_index]; random_index là chỉ số 0-based của node
   mà `random` trỏ tới, hoặc null nếu `random = None`)

  Tương ứng linked list:
        node 0      node 1      node 2      node 3      node 4
        val=7   →   val=13  →   val=11  →   val=10  →   val=1  →  None
        random:                                                    (next pointers)
          [0] → None
          [1] → node 0  (val 7)
          [2] → node 4  (val 1)
          [3] → node 2  (val 11)
          [4] → node 0  (val 7)

Output: deep copy của list trên — cùng val và cùng cấu trúc random,
        nhưng MỌI node là instance MỚI (không chia sẻ với input).

Output ở dạng LC array:
  [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Hash map “old → new”, O(n) time, O(n) space.

Lượt 1: tạo các node mới, lưu old_to_new[old] = new. Lượt 2: với mỗi old, gán new.next = old_to_new[old.next] và new.random = old_to_new[old.random].

Cách 2 — Interweave, O(n) time, O(1) extra space.

Trick rất nổi tiếng: 1. Lượt 1: chèn mỗi node copy ngay sau node gốc: A → A' → B → B' → C → C'. 2. Lượt 2: với mỗi node gốc A: gán A'.random = A.random.next (vì A.random.next chính là copy của A.random). 3. Lượt 3: tách 2 list ra.

Hình minh hoạ — Cách 2 với 3 node A, B, C:

Lượt 1 (chèn copy):
  A → A' → B → B' → C → C'

Lượt 2 (gán random):
  Giả sử A.random = C
  → A'.random = A.random.next = C.next = C'   (copy của C)  ✓

Lượt 3 (tách):
  Original:  A → B → C
  Copy:      A' → B' → C'

Code Python 3

class Node:
    def __init__(self, val: int = 0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random


class Solution:
    """Cách 1 — Hash map. Code dễ debug nhất."""

    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None
        old_to_new: dict[Node, Node] = {}
        # Lượt 1: tạo node copy.
        cur = head
        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next
        # Lượt 2: gán next/random.
        cur = head
        while cur:
            old_to_new[cur].next = old_to_new.get(cur.next)
            old_to_new[cur].random = old_to_new.get(cur.random)
            cur = cur.next
        return old_to_new[head]


class SolutionInterleave:
    """Cách 2 — Interweave, O(1) extra space."""

    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None
        # 1. Chèn copy ngay sau mỗi node gốc.
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next
        # 2. Gán random cho copy.
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. Tách 2 list.
        new_head = head.next
        cur, copy = head, new_head
        while cur:
            cur.next = copy.next
            cur = cur.next
            copy.next = cur.next if cur else None
            copy = copy.next
        return new_head

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.9 Reverse Nodes in k-Group (LC 25)

Đề bài

Cho head và số k. Đảo ngược từng nhóm k node liên tiếp trong list. Nếu số node còn lại không đủ k thì giữ nguyên. Yêu cầu: O(1) extra space.

Ví dụ

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5    (nhóm cuối chỉ có 1 node → giữ)

Input:  1 → 2 → 3 → 4 → 5, k = 3
Output: 3 → 2 → 1 → 4 → 5

Ràng buộc

Clarifying questions

Hướng tiếp cận

Quy trình: 1. Đi k bước để xác định đuôi nhóm. Nếu không đủ k → break. 2. Đảo nhóm trong khoảng [head_nhóm, đuôi_nhóm]. 3. Khâu đầu nhóm đã đảo vào prev_group_tail, đuôi nhóm đã đảo trỏ tới next_group_head. 4. Cập nhật prev_group_tail để tiếp tục nhóm sau.

Hình minh hoạ với 1 → 2 → 3 → 4 → 5, k = 2:

Bắt đầu:    dummy → 1 → 2 → 3 → 4 → 5 → None
            prev

Nhóm 1: [1, 2]. Đảo → [2, 1].
            dummy → 2 → 1 → 3 → 4 → 5 → None
                        ↑
                       prev (= 1, tail của nhóm vừa đảo)

Nhóm 2: [3, 4]. Đảo → [4, 3].
            dummy → 2 → 1 → 4 → 3 → 5 → None
                                ↑
                               prev (= 3)

Nhóm 3: [5]. Chỉ 1 node → không đủ k=2 → giữ.
            dummy → 2 → 1 → 4 → 3 → 5 → None   ✓

Code Python 3

class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        dummy = ListNode(0, head)
        prev_group_tail = dummy

        while True:
            # 1. Tìm đuôi nhóm — đi k bước.
            kth = prev_group_tail
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next      # không đủ k → giữ nguyên

            group_next = kth.next
            # 2. Đảo từ prev_group_tail.next đến kth.
            prev, curr = group_next, prev_group_tail.next
            while curr is not group_next:
                curr.next, prev, curr = prev, curr, curr.next
            # 3. Khâu nhóm đã đảo vào.
            old_head = prev_group_tail.next
            prev_group_tail.next = kth
            prev_group_tail = old_head     # bây giờ là đuôi của nhóm đã đảo

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.10 Sort List (LC 148)

Đề bài

Sort linked list tăng dần với O(n log n) time và O(1) extra space (theo follow-up — chỉ tính call stack/aux, không tính node).

Ví dụ

Input:  head = 4 → 2 → 1 → 3   (singly linked list)
Output: 1 → 2 → 3 → 4

Ràng buộc

Clarifying questions

Hướng tiếp cận

O(n log n) ⇒ quicksort, mergesort, heapsort. Quicksort khó áp cho LL, heapsort cần O(n) extra. Mergesort là tự nhiên nhất:

  1. Split list thành 2 nửa (dùng slow/fast tìm middle, ngắt slow.next).
  2. Recurse trên cả 2 nửa.
  3. Merge 2 list đã sort (bài 7.2).

Top-down (đệ quy) đẹp về code nhưng tốn O(log n) stack. Bottom-up (iterative) đạt thật sự O(1) space — nhưng code phức tạp. Trong phỏng vấn, top-down là đủ tốt.

Hình minh hoạ với 4 → 2 → 1 → 3:

                   sort([4, 2, 1, 3])
                  /                  \
        sort([4, 2])             sort([1, 3])
         /        \                /        \
    [4]            [2]         [1]            [3]
       \          /                \          /
       merge → [2, 4]              merge → [1, 3]
                       \              /
                       merge → [1, 2, 3, 4]   ✓

Code Python 3

class Solution:
    def sortList(self, head: ListNode | None) -> ListNode | None:
        if not head or not head.next:
            return head

        # 1. Split: tìm middle, ngắt đôi.
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None

        # 2. Recurse.
        left = self.sortList(head)
        right = self.sortList(mid)

        # 3. Merge.
        return self._merge(left, right)

    @staticmethod
    def _merge(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.11 LRU Cache (LC 146) — recap

Bài này đã được giải đầy đủ ở Chương 6 — Hash Table (mục 6.6). Ở đây chúng ta chỉ tóm tắt nhanh pattern Doubly Linked List vốn là điểm nhấn của LL.

Đề bài

Thiết kế LRU Cache với get(key) và put(key, value) đều O(1). Khi vượt capacity → xoá key ít dùng gần nhất.

Ràng buộc

Clarifying questions

Hướng tiếp cận: Doubly Linked List + Hash Map

LRU yêu cầu O(1) cho cả: - Lookup theo key → hash map. - Di chuyển 1 phần tử bất kỳ về đầu → doubly linked list (chỉ DLL mới cho phép unlink O(1) khi có reference).

Hình minh hoạ DLL state khi LRU eviction

capacity = 2
Head sentinel — MRU end                LRU end — Tail sentinel
       │                                                  │
       ▼                                                  ▼
     ┌───┐    ┌──────┐    ┌──────┐    ┌──────┐    ┌───┐
     │ H │ ↔ │ K=4  │ ↔ │ K=3  │ ↔ │ K=1  │ ↔ │ T │
     └───┘    └──────┘    └──────┘    └──────┘    └───┘
                                          ▲
                          khi vượt capacity, xoá node này
                          (Tail.prev = LRU)

Hash map:  {1: node1, 3: node3, 4: node4}

Code Python 3 (pattern DLL)

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


# Hai sentinel head/tail giúp tránh hàng tá check None.
head, tail = Node(), Node()
head.next, tail.prev = tail, head

def _remove(node):              # O(1) — chỉ cần reference
    node.prev.next = node.next
    node.next.prev = node.prev

def _add_to_front(node):
    node.prev = head
    node.next = head.next
    head.next.prev = node
    head.next = node

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

7.12 Reorder List (LC 143)

Đề bài

Cho linked list L: L0 → L1 → ... → Ln-1. Hãy sắp xếp lại thành:

L0 → Ln-1 → L1 → Ln-2 → L2 → Ln-3 → ...

In-place, không được tạo node mới.

Ví dụ

Input:  head = 1 → 2 → 3 → 4
Output: 1 → 4 → 2 → 3 (mutate in-place)

Input:  head = 1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3   (mutate in-place)

Ràng buộc

Clarifying questions

Hướng tiếp cận

3 bước chuẩn — vẫn là pattern “split → reverse → merge”:

  1. Tìm middle (slow/fast).
  2. Đảo nửa sau (in-place).
  3. Merge xen kẽ nửa đầu và nửa sau đã đảo.

Hình minh hoạ với 1 → 2 → 3 → 4 → 5:

Bước 1: tìm middle (slow ở 3)
            1 → 2 → 3 → 4 → 5

Bước 2: cắt đôi và đảo nửa sau:
            1 → 2 → 3      5 → 4
            (nửa đầu)      (nửa sau đã đảo)

Bước 3: merge xen kẽ:
            Lấy 1 từ trái → 1
            Lấy 5 từ phải → 1, 5
            Lấy 2 từ trái → 1, 5, 2
            Lấy 4 từ phải → 1, 5, 2, 4
            Lấy 3 từ trái → 1, 5, 2, 4, 3

Output: 1 → 5 → 2 → 4 → 3  ✓

Code Python 3

class Solution:
    def reorderList(self, head: ListNode | None) -> None:
        if not head or not head.next:
            return

        # 1. Tìm middle.
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Đảo nửa sau (từ slow.next).
        second = slow.next
        slow.next = None      # cắt đôi
        prev, curr = None, second
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        second = prev          # head của nửa sau đã đảo

        # 3. Merge xen kẽ.
        first = head
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Pointer safety checklist

  1. Trước khi cắt a.next = b, đã lưu a.next cũ chưa?
  2. Có dummy/sentinel trỏ vào head chưa? (Cần khi head có thể đổi.)
  3. Vòng lặp while cur and cur.next: chú ý điều kiện kép cho 2 nút cuối.
  4. Sau khi reverse hoặc split, tail cũ đã .next = None chưa? (Tránh cycle.)
  5. Edge cases: list rỗng (head = None), 1 phần tử, k > len.

Dummy/sentinel pattern (cốt lõi)

dummy = ListNode(0, head)
prev = dummy
# ... thao tác trên prev.next ...
return dummy.next

Dùng cho: Remove Nth From End, Merge Two Sorted, Partition, Odd Even, Reverse K-Group.

LRU (LC 146) bridge

Chương 8 — Queue + Stack

Stack (LIFO) và Queue (FIFO) là cặp đôi “ngược nhau”. Stack giải được mọi bài có cấu trúc lồng (parentheses, recursion, nested structure), Queue phục vụ duyệt theo lớp (BFS, sliding window). Chương này tập trung stack — bài queue thuần sẽ gặp lại ở Chương 10 (BFS). Cuối chương có 1 bài teaser về monotonic stack — pattern mạnh sẽ được khai thác sâu ở Chương 18.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Stack rất hợp khi: - Có cấu trúc lồng / balanced (ngoặc, tag HTML, nested expression). - Cần “undo” — bước trước phải xử lý xong sau bước hiện tại (DFS iterative). - Bài “next greater element”, “largest rectangle”, “daily temperatures” → monotonic stack (Chương 18).

Queue rất hợp khi: - Cần duyệt theo lớp / BFS (Chương 10). - Bài “sliding window max” → monotonic deque (Chương 18). - Producer-consumer, task scheduler.

Template code

from collections import deque
from typing import List

# 1) Stack với list (built-in trong Python, O(1) amortized).
stack: List[int] = []
stack.append(x)        # push
top = stack[-1]        # peek
val = stack.pop()      # pop

# 2) Queue với collections.deque — O(1) push/pop ở cả 2 đầu.
queue: deque[int] = deque()
queue.append(x)        # enqueue (đẩy vào cuối)
val = queue.popleft()  # dequeue (lấy đầu)

# 3) Stack lưu (index, value) — pattern monotonic.
stack: list[tuple[int, int]] = []        # (index, value)
for i, v in enumerate(arr):
    while stack and stack[-1][1] < v:
        idx, _ = stack.pop()
        # ... xử lý idx ...
    stack.append((i, v))

Bài tự luyện cuối chương

8.1 Valid Parentheses (LC 20)

Đề bài

Cho chuỗi s chỉ chứa ()[]{}. Trả về True nếu chuỗi hợp lệ: - Mỗi dấu ngoặc mở có dấu đóng tương ứng. - Các dấu ngoặc đóng đúng thứ tự (LIFO).

Ví dụ

Input:  s = "()"            → Output: True
Input:  s = "()[]{}"        → Output: True
Input:  s = "(]"            → Output: False
Input:  s = "([)]"          → Output: False    (lồng sai)
Input:  s = "{[]}"          → Output: True

Ràng buộc

Clarifying questions

Hướng tiếp cận

Stack pattern kinh điển. Duyệt từng ký tự: - Nếu là ngoặc mở → push. - Nếu là ngoặc đóng → check stack top có phải cặp tương ứng không. Nếu không, hoặc stack rỗng → return False. Nếu có → pop.

Cuối cùng stack phải rỗng (mọi ngoặc đã match).

Hình minh hoạ với s = "{[()]}":

ch   action          stack sau action
─────────────────────────────────────
{    push            ['{']
[    push            ['{', '[']
(    push            ['{', '[', '(']
)    pop, match (    ['{', '[']
]    pop, match [    ['{']
}    pop, match {    []

Stack rỗng → True ✓

Code Python 3

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stack: list[str] = []
        for ch in s:
            if ch in pairs:                # ngoặc đóng
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:                          # ngoặc mở
                stack.append(ch)
        return not stack

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

8.2 Min Stack (LC 155)

Đề bài

Thiết kế stack hỗ trợ 4 thao tác đều O(1): - push(x) - pop() - top() — peek - getMin() — trả về min hiện có trong stack

Ví dụ

Input (LC-style operation arrays):
  ops  = ["MinStack","push","push","push","getMin","pop","top","getMin"]
  args = [[],        [-2],   [0],  [-3],  [],     [],   [],   []]

Output: [null, null, null, null, -3, null, 0, -2]

Giải thích từng bước:
  MinStack()  → khởi tạo
  push(-2);  push(0);  push(-3)
  getMin()   → -3
  pop()      → bỏ -3
  top()      → 0
  getMin()   → -2

Ràng buộc

Clarifying questions

Hướng tiếp cận

Vấn đề: getMin() O(1) ⇒ phải lưu min đâu đó. Nhưng khi pop min ra, phải biết min mới — đây là cốt lõi.

Cách 1 — Aux stack song song giữ min_so_far.

Stack phụ mins mỗi ô = min của tất cả các phần tử dưới (kể cả nó) trong main stack. Khi push, push min(x, mins[-1]). Khi pop, pop cả 2 stack.

Cách 2 — 1 stack lưu (value, current_min).

Tương đương cách 1 nhưng gộp thành tuple. Cùng overhead.

Hình minh hoạ — Cách 1 với push(-2), push(0), push(-3), pop():

push(-2):  stack=[-2]      mins=[-2]
push(0):   stack=[-2, 0]   mins=[-2, -2]    (min(0, -2)=-2)
push(-3):  stack=[-2,0,-3] mins=[-2,-2,-3]   (min(-3, -2)=-3)

getMin() → mins[-1] = -3   ✓
pop():    stack=[-2, 0]    mins=[-2, -2]
getMin() → mins[-1] = -2   ✓

Code Python 3

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.mins: list[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        cur_min = val if not self.mins else min(val, self.mins[-1])
        self.mins.append(cur_min)

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.mins[-1]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

8.3 Implement Queue using Stacks (LC 232)

Đề bài

Thiết kế Queue (FIFO) chỉ dùng 2 stack. Hỗ trợ push, pop, peek, empty.

Ví dụ

Input (LC-style operation arrays):
  ops  = ["MyQueue","push","push","peek","pop","empty"]
  args = [[],       [1],   [2],   [],    [],   []]

Output: [null, null, null, 1, 1, false]

Giải thích từng bước:
  MyQueue()  → khởi tạo
  push(1);  push(2)
  peek()    → 1   (FIFO: phần tử đẩy vào trước ra trước)
  pop()     → 1
  empty()   → false

Ràng buộc

Clarifying questions

Hướng tiếp cận

Ý tưởng — 2 stack: in (input) và out (output). - push(x): push vào in. - pop / peek: nếu out rỗng → “đổ” toàn bộ in sang out (đảo thứ tự vì stack). Sau đó pop/peek từ out.

Phân tích amortized: Mỗi phần tử bị move giữa 2 stack tối đa 1 lần. Worst-case 1 op = O(n), nhưng amortized = O(1).

Hình minh hoạ với push(1), push(2), push(3), pop(), push(4), pop():

push(1): in=[1]              out=[]
push(2): in=[1, 2]           out=[]
push(3): in=[1, 2, 3]        out=[]

pop(): out rỗng → đổ in sang out
       in=[]                  out=[3, 2, 1]    (1 ở top)
       out.pop() → 1
       in=[]                  out=[3, 2]

push(4): in=[4]              out=[3, 2]

pop(): out không rỗng → out.pop() → 2
       in=[4]                out=[3]

→ FIFO: 1 ra trước (đúng thứ tự push)

Code Python 3

class MyQueue:
    def __init__(self):
        self.in_st: list[int] = []
        self.out_st: list[int] = []

    def push(self, x: int) -> None:
        self.in_st.append(x)

    def pop(self) -> int:
        self._shift()
        return self.out_st.pop()

    def peek(self) -> int:
        self._shift()
        return self.out_st[-1]

    def empty(self) -> bool:
        return not self.in_st and not self.out_st

    def _shift(self) -> None:
        """Khi out rỗng, đổ toàn bộ in sang out."""
        if not self.out_st:
            while self.in_st:
                self.out_st.append(self.in_st.pop())

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

8.4 Evaluate Reverse Polish Notation (LC 150)

Đề bài

Cho mảng tokens biểu diễn biểu thức Reverse Polish Notation (postfix). Mỗi token là số nguyên hoặc 1 trong 4 phép + - * /. Trả về kết quả (chia lấy phần nguyên hướng về 0).

Ví dụ

Input:  tokens = ["2","1","+","3","*"]
Output: 9
Giải thích: (2 + 1) * 3 = 9.

Input:  tokens = ["4","13","5","/","+"]
Output: 6
Giải thích: 4 + (13 / 5) = 4 + 2 = 6.

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Ràng buộc

Clarifying questions

Hướng tiếp cận

RPN ↔︎ stack — kinh điển. Duyệt: - Số → push. - Phép → pop 2 phần tử (b lấy trước, a lấy sau), tính a op b, push kết quả.

Cuối cùng stack còn 1 phần tử = kết quả.

Hình minh hoạ với ["2","1","+","3","*"]:

token   action                      stack
─────────────────────────────────────────────
"2"     push 2                      [2]
"1"     push 1                      [2, 1]
"+"     pop b=1, a=2; push 3        [3]
"3"     push 3                      [3, 3]
"*"     pop b=3, a=3; push 9        [9]

Kết quả: 9

Code Python 3

from typing import List
import operator

class Solution:
    OPS = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': lambda a, b: int(a / b),   # chia hướng về 0
    }

    def evalRPN(self, tokens: List[str]) -> int:
        stack: list[int] = []
        for tk in tokens:
            if tk in self.OPS:
                b = stack.pop()
                a = stack.pop()
                stack.append(self.OPS[tk](a, b))
            else:
                stack.append(int(tk))
        return stack[0]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

8.5 Daily Temperatures (LC 739) — teaser monotonic stack

Đề bài

Cho mảng temperatures các nhiệt độ. Với mỗi ngày i, tìm xem bao nhiêu ngày sau đó mới có nhiệt độ cao hơn ngày i. Nếu không có, trả 0.

Ví dụ

Input:  temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Giải thích:
  day 0: 73 → ngày 1 (74) cao hơn → 1
  day 2: 75 → phải đợi tới ngày 6 (76) → 6-2=4
  day 6: 76 không có gì cao hơn → 0

Ràng buộc

Clarifying questions

Hướng tiếp cận

Brute force — O(n²). Với mỗi i, quét forward tìm cái lớn hơn. TLE khi n = 10^5.

Tối ưu — Monotonic decreasing stack — O(n).

Ý tưởng: Duy trì stack các index mà temperature giảm dần (từ đáy lên đỉnh). Khi gặp ngày i có nhiệt cao hơn top của stack → đó chính là “answer” cho ngày ở top. Pop và ghi result[top] = i - top.

Hình minh hoạ với [73, 74, 75, 71, 69, 72, 76, 73]:

i  temp   action                                stack (idx)    result
─────────────────────────────────────────────────────────────────────────
0  73     push 0                                [0]            [_, _, _, _, _, _, _, _]
1  74     74 > 73 → pop 0, result[0]=1-0=1     [1]            [1, _, _, _, _, _, _, _]
          push 1
2  75     75 > 74 → pop 1, result[1]=2-1=1     [2]            [1, 1, _, _, _, _, _, _]
          push 2
3  71     71 < 75 → push 3                     [2, 3]
4  69     69 < 71 → push 4                     [2, 3, 4]
5  72     72 > 69 → pop 4, result[4]=5-4=1     [2, 3, 5]
          72 > 71 → pop 3, result[3]=5-3=2
          push 5
6  76     76 > 72 → pop 5, result[5]=6-5=1     [6]
          76 > 75 → pop 2, result[2]=6-2=4
          push 6
7  73     73 < 76 → push 7                     [6, 7]

Còn lại trong stack: [6, 7] → result giữ 0.
Kết quả: [1, 1, 4, 2, 1, 1, 0, 0]  ✓

Stack invariant: index trong stack có temperature giảm dần từ đáy lên đỉnh. Mỗi index được push 1 lần, pop tối đa 1 lần → tổng O(n).

Code Python 3

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        stack: list[int] = []   # các index có temperature giảm dần
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                result[j] = i - j
            stack.append(i)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

8.6 Decode String (LC 394)

Đề bài

Cho chuỗi s mã hoá theo dạng k[encoded_string] — nghĩa là encoded_string sẽ được lặp k lần. Decode chuỗi.

Ví dụ

Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

Input:  s = "3[a2[c]]"
Output: "accaccacc"   (lồng)

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cấu trúc lồng ⇒ dùng stack. Mỗi khi gặp [, ta “lưu” số k và chuỗi đang build vào stack, rồi reset chuỗi build. Khi gặp ], pop ra (prev_str, k) và nối prev_str + k * cur_str.

Cách 2 — Đệ quy. Mỗi k[...] thành 1 lần gọi đệ quy. Code gọn hơn nhưng tốn stack (đệ quy có thể vượt giới hạn với chuỗi lồng sâu).

Hình minh hoạ — Cách stack với "3[a2[c]]":

ch    action                                     stack         cur
─────────────────────────────────────────────────────────────────
'3'   k = 3                                      []           ""
'['   push (k, cur); reset k, cur                [(3, "")]    ""
'a'   cur += 'a'                                 [(3, "")]    "a"
'2'   k = 2                                      [(3, "")]    "a"
'['   push (k=2, cur="a"); reset k, cur          [(3, ""), (2, "a")]  ""
'c'   cur += 'c'                                 [(3, ""), (2, "a")]  "c"
']'   (prev_k=2, prev_str="a") = pop;
      cur = prev_str + prev_k * cur = "a" + "cc" [(3, "")]    "acc"
']'   (prev_k=3, prev_str="") = pop;
      cur = "" + 3 * "acc" = "accaccacc"         []           "accaccacc"

Kết quả: "accaccacc"  ✓

Code Python 3

class Solution:
    def decodeString(self, s: str) -> str:
        stack: list[tuple[str, int]] = []   # (prev_str, prev_k)
        cur, k = "", 0
        for ch in s:
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == '[':
                stack.append((cur, k))
                cur, k = "", 0
            elif ch == ']':
                prev_str, prev_k = stack.pop()
                cur = prev_str + cur * prev_k
            else:
                cur += ch
        return cur


class SolutionRecursive:
    """Cách 2 — đệ quy. Code clean nhưng tốn stack."""

    def decodeString(self, s: str) -> str:
        self.i = 0
        return self._decode(s)

    def _decode(self, s: str) -> str:
        result = ""
        k = 0
        while self.i < len(s) and s[self.i] != ']':
            ch = s[self.i]
            if ch.isdigit():
                k = k * 10 + int(ch)
                self.i += 1
            elif ch == '[':
                self.i += 1
                inner = self._decode(s)
                result += k * inner
                k = 0
                self.i += 1     # skip ']'
            else:
                result += ch
                self.i += 1
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Stack mental models

Mục đích Stack chứa gì Bài ví dụ
Match cặp đối xứng Mở ngoặc / token chờ đóng LC 20, 1249
Lưu token trước đó chưa hoàn tất Số / chuỗi cần “expand” sau LC 394 Decode
Undo / context Phép tính cha LC 224 Calculator
Monotonic Index/value tăng/giảm Chương 18
Iterative DFS Frame call Tree iterative inorder

Decode String (LC 394) — trace 3[a2[c]]

Bước Char num cur numStack strStack
0 3 3 "" [] []
1 [ 0 "" [3] [""]
2 a 0 "a" [3] [""]
3 2 2 "a" [3] [""]
4 [ 0 "" [3,2] ["", "a"]
5 c 0 "c" [3,2] ["", "a"]
6 ] 0 "acc" (a + c×2) [3] [""]
7 ] 0 "accaccacc" (×3) [] []

RPN (LC 150) — thứ tự operand

Pop b trước, a sau, tính a op b. Nhầm thứ tự là bug điển hình với - và /.

Min Stack so sánh

Chương 9 — Graph

Graph là cấu trúc dữ liệu trừu tượng nhất nhưng cũng phổ biến nhất trong đời thực: bạn bè, đường đi, dependency, … Chương này giới thiệu biểu diễn graph và 6 bài phổ thông về graph. Hai kỹ thuật duyệt BFS, DFS sẽ được đào sâu ở Chương 10 và 11; chương này dùng cả 2 ở mức cơ bản để bạn làm quen.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

3 câu hỏi trước khi code: 1. Hướng / vô hướng? Directed cần cân nhắc thêm chu trình. 2. Có trọng số? Nếu có → cân nhắc Dijkstra (Chương 30), không thì BFS/DFS đủ. 3. Đặc tính đặc biệt? DAG → topo sort, bipartite, planar, …

Biểu diễn graph

from collections import defaultdict
from typing import List

# 1) Adjacency List — hầu hết bài dùng cái này
graph: dict[int, list[int]] = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)    # bỏ dòng này nếu directed

# 2) Edge List — input "raw"
edges: list[tuple[int, int]] = [(0, 1), (1, 2), ...]

# 3) Adjacency Matrix — chỉ khi V nhỏ (≤ 1000) và mật độ cao
adj = [[0] * n for _ in range(n)]
for u, v in edges:
    adj[u][v] = 1

Khi nào dùng cái nào?

Biểu diễn Lookup (u, v) Duyệt láng giềng u Bộ nhớ
Adj list O(deg(u)) O(deg(u)) O(V + E)
Edge list O(E) O(E) O(E)
Adj matrix O(1) O(V) O(V²)

→ Mặc định dùng adjacency list. Chỉ chuyển sang matrix khi cần kiểm tra edge O(1) và V nhỏ.

Template code

from collections import defaultdict, deque

# DFS đệ quy
def dfs(node: int, visited: set[int], graph: dict) -> None:
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor, visited, graph)

# DFS iterative bằng stack
def dfs_iter(start: int, graph: dict) -> set[int]:
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                stack.append(nb)
    return visited

# BFS bằng queue
def bfs(start: int, graph: dict) -> set[int]:
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return visited

Bài tự luyện cuối chương

9.1 Find if Path Exists in Graph (LC 1971)

Đề bài

Cho n đỉnh đánh số 0..n-1 và mảng cạnh vô hướng edges[i] = [u, v]. Cho source và destination. Trả về True nếu có đường đi giữa chúng.

Ví dụ

Input:  n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: True

Input:  n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: False

Ràng buộc

Clarifying questions

Hướng tiếp cận

3 cách kinh điển, đều O(V + E): 1. BFS — duyệt theo lớp, return ngay khi gặp destination. 2. DFS — đệ quy hoặc stack. 3. Union Find (Chương 24) — gộp 2 đỉnh thành 1 root nếu có cạnh; check find(source) == find(destination). Đẹp khi đề bài có nhiều query “có đường đi giữa u, v?”.

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    """BFS — sạch nhất cho 1 query."""

    def validPath(self, n: int, edges: List[List[int]],
                  source: int, destination: int) -> bool:
        if source == destination:
            return True
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = {source}
        queue = deque([source])
        while queue:
            node = queue.popleft()
            for nb in graph[node]:
                if nb == destination:
                    return True
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        return False

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

9.2 Clone Graph (LC 133)

Đề bài

Cho node của một undirected connected graph. Mỗi Node có val: int và neighbors: list[Node]. Hãy deep copy graph: tạo bản sao mà mỗi node mới là instance riêng, các neighbors trỏ vào node mới tương ứng.

Ví dụ

Input:  adjList = [[2,4], [1,3], [2,4], [1,3]]
        (adjList[i-1] = danh sách neighbor của node i, node value 1-indexed
         giống LC; tham số API thực chất là Node = adjList[0] = node 1)

        Tương ứng graph:
            1 ── 2
            │    │
            4 ── 3

Output: [[2,4], [1,3], [2,4], [1,3]]
        (cùng cấu trúc adjacency, nhưng MỌI Node trong output là instance MỚI;
         không có Node nào dùng chung với input)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Pattern y hệt LC 138 (Copy List with Random Pointer, bài 7.8): dùng hash map original_to_copy để tránh tạo trùng và xử lý chu trình.

BFS / DFS đều OK — quan trọng là check visited qua dict.

Hình minh hoạ với graph 1—2—3—4—1:

Bắt đầu: visit 1.
  cloned = {1: Node(1)}
  queue = [1]

Pop 1:  hàng xóm = [2, 4]
  Tạo Node(2), Node(4); thêm vào cloned.
  cloned[1].neighbors = [cloned[2], cloned[4]]
  queue = [2, 4]

Pop 2:  hàng xóm = [1, 3]
  cloned[1] đã có; tạo Node(3).
  cloned[2].neighbors = [cloned[1], cloned[3]]
  queue = [4, 3]

Pop 4:  hàng xóm = [1, 3]
  cả 2 đã có trong cloned.
  cloned[4].neighbors = [cloned[1], cloned[3]]

Pop 3:  hàng xóm = [2, 4]
  cả 2 đã có.
  cloned[3].neighbors = [cloned[2], cloned[4]]

→ Trả cloned[1] làm head của bản copy.

Code Python 3

from collections import deque

class Node:
    def __init__(self, val: int = 0, neighbors: "list[Node] | None" = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution:
    """BFS với hash map."""

    def cloneGraph(self, node: "Node | None") -> "Node | None":
        if not node:
            return None

        cloned: dict["Node", "Node"] = {node: Node(node.val)}
        queue: deque["Node"] = deque([node])

        while queue:
            cur = queue.popleft()
            for nb in cur.neighbors:
                if nb not in cloned:
                    cloned[nb] = Node(nb.val)
                    queue.append(nb)
                cloned[cur].neighbors.append(cloned[nb])

        return cloned[node]


class SolutionDFS:
    """DFS đệ quy — code ngắn hơn."""

    def cloneGraph(self, node: "Node | None") -> "Node | None":
        cloned: dict["Node", "Node"] = {}

        def dfs(cur: "Node") -> "Node":
            if cur in cloned:
                return cloned[cur]
            copy = Node(cur.val)
            cloned[cur] = copy           # phải set TRƯỚC khi đệ quy neighbors
            copy.neighbors = [dfs(nb) for nb in cur.neighbors]
            return copy

        return dfs(node) if node else None

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

9.3 Number of Connected Components (LC 323)

Đề bài

Cho n đỉnh đánh số 0..n-1 và mảng cạnh vô hướng. Đếm số thành phần liên thông.

Ví dụ

Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Giải thích: 2 component {0,1,2} và {3,4}.

Input:  n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — Duyệt DFS/BFS từng đỉnh chưa thăm — O(V + E). Cho mỗi đỉnh chưa thăm, tăng counter và DFS/BFS đánh dấu cả component.

Cách 2 — Union Find — O((V + E) · α(V)). Gom các đỉnh có cạnh thành cùng root. Đếm số root khác nhau.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = [False] * n
        count = 0

        def dfs(node: int) -> None:
            visited[node] = True
            for nb in graph[node]:
                if not visited[nb]:
                    dfs(nb)

        for i in range(n):
            if not visited[i]:
                count += 1
                dfs(i)
        return count


class SolutionUF:
    """Union Find — đẹp khi đề bài có nhiều query."""

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]   # path compression
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            parent[px] = py
            return True

        components = n
        for u, v in edges:
            if union(u, v):
                components -= 1
        return components

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

9.4 Course Schedule (LC 207)

Đề bài

Có numCourses khoá học đánh số 0..numCourses-1. prerequisites[i] = [a, b] nghĩa là muốn học khoá a thì phải hoàn thành khoá b trước. Trả về True nếu có thể học hết tất cả khoá, ngược lại False.

Ví dụ

Input:  numCourses = 2, prerequisites = [[1, 0]]
Output: True

Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False    (vòng tròn: 1 cần 0, 0 cần 1)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Phát biểu lại: Tạo directed graph b → a (b phải xong trước a). Câu hỏi: graph có chu trình không? Nếu không có chu trình → có thể học hết.

Cách 1 — DFS với 3 trạng thái (white / gray / black).

Nếu DFS gặp gray → tìm thấy back-edge → có chu trình.

Cách 2 — Topological Sort BFS (Kahn’s algorithm).

Đếm indegree mỗi node. Đẩy các node indegree == 0 vào queue. Pop và giảm indegree của các neighbors. Nếu cuối cùng đếm được numCourses node → DAG; ngược lại có chu trình.

Topological sort là cốt lõi của Chương 13. Ở đây giới thiệu sớm vì Course Schedule là kinh điển ứng dụng nó.

Hình minh hoạ — DFS 3 màu với cycle 0 → 1 → 0:

Bắt đầu: tất cả white.
DFS(0):
  mark 0 = gray.
  visit 1 (white):
    DFS(1):
      mark 1 = gray.
      visit 0 (gray!) → back-edge phát hiện → return False (có chu trình)

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    """DFS 3-color."""

    WHITE, GRAY, BLACK = 0, 1, 2

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)            # b → a

        color = [self.WHITE] * numCourses

        def has_cycle(node: int) -> bool:
            if color[node] == self.GRAY:
                return True               # back-edge
            if color[node] == self.BLACK:
                return False              # đã xong, không có cycle từ đây
            color[node] = self.GRAY
            for nb in graph[node]:
                if has_cycle(nb):
                    return True
            color[node] = self.BLACK
            return False

        for i in range(numCourses):
            if has_cycle(i):
                return False
        return True


class SolutionKahn:
    """BFS topo sort (Kahn's algorithm)."""

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1

        queue = deque(i for i, d in enumerate(indeg) if d == 0)
        processed = 0
        while queue:
            node = queue.popleft()
            processed += 1
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return processed == numCourses

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

9.5 Is Graph Bipartite? (LC 785)

Đề bài

Cho graph vô hướng dạng adjacency list graph[i] = [hàng xóm của i]. Trả về True nếu graph là bipartite — có thể chia các đỉnh thành 2 tập sao cho mọi cạnh nối 2 đỉnh ở khác tập.

Ví dụ

Input:  graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: False
Giải thích: 0—1—2—0 là tam giác → không thể 2-color.

Input:  graph = [[1,3],[0,2],[1,3],[0,2]]
Output: True
Giải thích: tập A = {0, 2}, tập B = {1, 3}.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Equivalent: Graph bipartite ↔︎ tô được 2 màu sao cho không có 2 đỉnh kề nhau cùng màu.

BFS/DFS với 2-color: Bắt đầu mỗi component, tô đỉnh đầu màu 0. Khi BFS/DFS sang hàng xóm, tô màu ngược. Nếu gặp hàng xóm đã có màu giống → return False.

Hình minh hoạ — graph tam giác (không bipartite):

       0
      / \
     1───2

BFS từ 0:
  color[0] = 0.
  Sang 1: color[1] = 1 (ngược màu 0).
  Sang 2: color[2] = 1 (ngược màu 0).
  Từ 1, sang 2: color[2] đã là 1 == color[1] = 1 → MÂU THUẪN → False

Code Python 3

from collections import deque
from typing import List

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n        # -1 = chưa tô

        for start in range(n):
            if color[start] != -1:
                continue
            # BFS component chứa start.
            color[start] = 0
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for nb in graph[node]:
                    if color[nb] == -1:
                        color[nb] = 1 - color[node]
                        queue.append(nb)
                    elif color[nb] == color[node]:
                        return False
        return True

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

9.6 Evaluate Division (LC 399)

Đề bài

Cho mảng các đẳng thức equations[i] = [Ai, Bi] và mảng values[i] nghĩa là Ai / Bi = values[i]. Cho mảng query queries[j] = [Cj, Dj]. Hãy trả lời mỗi query với giá trị Cj / Dj, hoặc -1 nếu không xác định được.

Ví dụ

Input:  equations = [["a","b"], ["b","c"]]
        values    = [2.0, 3.0]
        queries   = [["a","c"], ["b","a"], ["a","e"], ["a","a"], ["x","x"]]
Output: [6.0, 0.5, -1.0, 1.0, -1.0]
Giải thích:
  a/c = a/b * b/c = 2 * 3 = 6
  b/a = 1/(a/b) = 0.5
  a/e không xác định (e không có trong equations)
  a/a = 1
  x/x: x không có trong equations → -1

Ràng buộc

Clarifying questions

Hướng tiếp cận

Insight: mỗi đẳng thức A / B = k ↔︎ trong directed graph có 2 cạnh: - A → B trọng số k. - B → A trọng số 1/k.

Khi đó C / D = tích trọng số dọc theo bất kỳ đường đi nào từ C đến D. Nếu không có đường đi → trả -1.

DFS trên graph trọng số là đủ. Tối ưu hơn: Union Find với trọng số (xem Chương 24).

Hình minh hoạ với equations a/b=2, b/c=3:

Graph trọng số:
            ── 2 ──>          ── 3 ──>
       a               b               c
            <─ 0.5 ──         <─ 1/3 ─

Query a/c: DFS từ a:
  a → b (× 2), tiếp b → c (× 3) → tổng 2 * 3 = 6.  ✓

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(
        self, equations: List[List[str]],
        values: List[float], queries: List[List[str]]
    ) -> List[float]:
        graph: dict[str, dict[str, float]] = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = v
            graph[b][a] = 1.0 / v

        def dfs(src: str, dst: str, visited: set[str]) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited.add(src)
            for nb, weight in graph[src].items():
                if nb in visited:
                    continue
                sub = dfs(nb, dst, visited)
                if sub != -1.0:
                    return weight * sub
            return -1.0

        return [dfs(c, d, set()) for c, d in queries]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Graph problem diagnosis

Triệu chứng đề bài Pattern phù hợp Chương
“Có đường từ A đến B?” BFS / DFS / Union Find 10, 11, 24
“Số cụm/đảo” DFS / Union Find 12, 24
“Thứ tự thực hiện với ràng buộc” Topological sort 13
“Shortest path trọng số dương” Dijkstra (Chương 30)
“Shortest path 0/1 edges” 0-1 BFS / BFS thường
“All-pairs shortest” Floyd-Warshall O(V³)
“Nhỏ nhất kết nối tất cả” MST (Chương 33)
“Bottleneck min/max trên path” Kruskal + DSU / BS + BFS (37)
“Bipartite?” BFS/DFS 2-color

Clone Graph (LC 133) — mapping diagram

old:  1 — 2
       \  /
        3 — 4

old_to_new = {1:1', 2:2', 3:3', 4:4'}   (dict cũ → bản sao)
clone(node):
    if node in old_to_new: return old_to_new[node]
    new = Node(node.val)
    old_to_new[node] = new       # ĐẶT TRƯỚC khi đệ quy → tránh vòng
    for nei in node.neighbors:
        new.neighbors.append(clone(nei))
    return new

Evaluate Division (LC 399) — weighted DFS

Course Schedule ở chương này = teaser

Bài đầy đủ Topological sort xem Chương 13. Chương này chỉ trình bày DFS detect cycle.

Chương 10 — Breadth-First Search (BFS)

BFS duyệt graph theo lớp (level by level). Đặc tính then chốt: nếu mọi cạnh có trọng số bằng nhau (= 1), BFS từ source cho ra đường đi ngắn nhất đến mọi đỉnh khác. Đây là lý do BFS xuất hiện rất nhiều ở các bài “shortest path in unweighted graph”, “minimum steps”, “minimum transformations”, …

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Phân biệt với DFS: - BFS: tìm path ngắn nhất, duyệt theo lớp. - DFS: thám hiểm sâu (path đầu tiên đến đích), check connectivity, đếm components.

Template code

from collections import deque

# 1) BFS chuẩn — đường đi ngắn nhất từ start tới target
def bfs_shortest(start, target, neighbors_fn) -> int:
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])         # (node, distance)
    while queue:
        node, dist = queue.popleft()
        for nb in neighbors_fn(node):
            if nb == target:
                return dist + 1
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, dist + 1))
    return -1


# 2) BFS theo lớp — không cần lưu distance trong queue
def bfs_by_level(start, neighbors_fn):
    visited = {start}
    queue = deque([start])
    level = 0
    while queue:
        size = len(queue)
        for _ in range(size):
            node = queue.popleft()
            # ... xử lý node ở level này ...
            for nb in neighbors_fn(node):
                if nb not in visited:
                    visited.add(nb)
                    queue.append(nb)
        level += 1


# 3) Multi-source BFS — đẩy nhiều nguồn vào queue cùng lúc
def multi_source(sources: list, neighbors_fn):
    queue = deque(sources)
    visited = set(sources)
    while queue:
        ...

Bài tự luyện cuối chương

10.1 Binary Tree Level Order Traversal (LC 102)

Đề bài

Cho root của một binary tree. Trả về level order traversal dưới dạng danh sách các list (mỗi list chứa các node ở 1 level từ trên xuống, trái sang phải).

Ví dụ

Input:  root = [3, 9, 20, null, null, 15, 7]   (LC level-order serialize)

        Cây thực tế:
              3
             / \
            9   20
               /  \
              15   7

Output: [[3], [9, 20], [15, 7]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

BFS theo lớp. Mỗi vòng outer = 1 level. Đầu mỗi vòng, ghi size = len(queue), sau đó pop đúng size node — đó là toàn bộ level hiện tại.

Hình minh hoạ:

Init:  queue = [3]
Level 0: size=1
  Pop 3. result.append([3]). Push 9, 20.
  queue = [9, 20]

Level 1: size=2
  Pop 9 → null children.
  Pop 20 → push 15, 7.
  result.append([9, 20]).
  queue = [15, 7]

Level 2: size=2
  Pop 15, 7 → null children.
  result.append([15, 7]).
  queue = []

→ [[3], [9, 20], [15, 7]]

Code Python 3

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result: List[List[int]] = []
        queue = deque([root])
        while queue:
            size = len(queue)
            level_vals: list[int] = []
            for _ in range(size):
                node = queue.popleft()
                level_vals.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level_vals)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

10.2 Rotting Oranges (LC 994) — Multi-source BFS

Đề bài

Cho lưới grid với các giá trị: - 0 = ô trống - 1 = quả tươi - 2 = quả thối

Mỗi phút, mỗi quả thối làm 4 ô kề bên (lên/xuống/trái/phải) có quả tươi trở thành thối. Trả về số phút tối thiểu để không còn quả tươi, hoặc -1 nếu không khả thi.

Ví dụ

Input:  grid = [[2,1,1],
                [1,1,0],
                [0,1,1]]
        (0 = empty, 1 = fresh orange, 2 = rotten)
Output: 4   (số phút để mọi orange thối)

Input:  grid = [[2,1,1],
                [0,1,1],
                [1,0,1]]
Output: -1   (quả tươi ở (2,0) bị cô lập, không bao giờ thối)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Insight: Mỗi quả thối là một nguồn lan toả. Tất cả nguồn lan đồng thời mỗi phút → multi-source BFS.

Quy trình: 1. Đẩy tất cả quả thối ban đầu vào queue cùng lúc (level 0). 2. BFS theo lớp — mỗi level tăng minutes thêm 1. 3. Đếm số quả tươi ban đầu. Mỗi lần thối thêm một quả → giảm count. 4. Cuối: nếu còn quả tươi → -1, ngược lại → minutes.

Hình minh hoạ với grid 3x3:

Init:                t=0:              t=1:              t=4:
[2, 1, 1]            [2, 1, 1]         [2, 2, 1]         [2, 2, 2]
[1, 1, 0]            [1, 1, 0]         [2, 1, 0]         [2, 2, 0]
[0, 1, 1]            [0, 1, 1]         [0, 1, 1]         [0, 2, 2]
                                       (4 quả tươi)      (xong)

Hàng động BFS:
Queue chứa các ô (i, j) cùng level → mỗi vòng outer pop hết queue rồi push
hàng xóm. Số vòng outer = số phút.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue: deque[tuple[int, int]] = deque()
        fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        if fresh == 0:
            return 0

        minutes = 0
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue and fresh > 0:
            minutes += 1
            for _ in range(len(queue)):
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))

        return minutes if fresh == 0 else -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

10.3 Word Ladder (LC 127)

Đề bài

Cho beginWord, endWord, và wordList (các từ cùng độ dài). Mỗi bước biến đổi: thay đúng 1 ký tự trong word hiện tại sao cho từ mới vẫn nằm trong wordList. Trả về số bước tối thiểu để biến beginWord → endWord (bao gồm cả 2 đầu). Trả 0 nếu không khả thi.

Ví dụ

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Giải thích: hit → hot → dot → dog → cog  (độ dài 5)

Input:  beginWord = "hit", endWord = "cog"
        wordList = ["hot","dot","dog","lot","log"]
Output: 0    (cog không trong wordList)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Mô hình hoá: Mỗi từ là 1 đỉnh; có cạnh giữa 2 từ nếu chúng khác nhau đúng 1 ký tự. Bài thành shortest path trong undirected graph → BFS.

Tối ưu sinh hàng xóm: Thay vì so sánh từ cur với mọi từ trong wordList (O(N·L) mỗi node) — quá chậm — ta sinh hàng xóm bằng cách thay từng vị trí ký tự bằng a..z (O(26·L) mỗi node).

Hình minh hoạ với "hit" → "cog":

Level 1: hit
Level 2: hot                (đổi i→o)
Level 3: dot, lot           (đổi h→d/l)
Level 4: dog, log           (đổi t→g)
Level 5: cog                ★ đáp án (5 bước)

Code Python 3

from collections import deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if endWord not in word_set:
            return 0

        queue = deque([(beginWord, 1)])
        visited = {beginWord}
        while queue:
            word, steps = queue.popleft()
            if word == endWord:
                return steps
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    if ch == word[i]:
                        continue
                    next_word = word[:i] + ch + word[i + 1:]
                    if next_word in word_set and next_word not in visited:
                        visited.add(next_word)
                        queue.append((next_word, steps + 1))
        return 0

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

10.4 Open the Lock (LC 752)

Đề bài

Cho khoá 4 ô số 0000. Mỗi bước: xoay 1 ô số lên hoặc xuống 1 đơn vị (vòng 0..9). Cho deadends (các tổ hợp không được đến) và target. Trả về số bước tối thiểu để đến target, hoặc -1 nếu không khả thi.

Ví dụ

Input:  deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Giải thích: 0000 → 1000 → 1100 → 1200 → 1201 → 1202 → 0202
            (không trùng deadend nào)

Ràng buộc

Clarifying questions

Hướng tiếp cận

State space implicit graph. Mỗi state là chuỗi 4 chữ số → 10^4 = 10000 state. Từ mỗi state có 8 transition (4 ô × 2 chiều).

BFS: bắt đầu từ "0000", BFS đến target. Skip các state trong deadends.

Hình minh hoạ một phần BFS:

Level 0: 0000
Level 1: 1000, 9000, 0100, 0900, 0010, 0090, 0001, 0009  (8 hàng xóm)
Level 2: ... (mỗi node 8 hàng xóm, trừ những cái đã visited / deadend)
...
Level 6: 0202  ★

Code Python 3

from collections import deque
from typing import List

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        if "0000" in dead:
            return -1
        if target == "0000":
            return 0

        def neighbors(state: str):
            for i in range(4):
                d = int(state[i])
                for delta in (-1, 1):
                    new_d = (d + delta) % 10
                    yield state[:i] + str(new_d) + state[i + 1:]

        visited = {"0000"}
        queue = deque([("0000", 0)])
        while queue:
            state, steps = queue.popleft()
            for nb in neighbors(state):
                if nb in dead or nb in visited:
                    continue
                if nb == target:
                    return steps + 1
                visited.add(nb)
                queue.append((nb, steps + 1))
        return -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

10.5 Shortest Path in Binary Matrix (LC 1091)

Đề bài

Cho ma trận vuông n × n chứa 0 (đi được) và 1 (vật cản). Tìm đường đi ngắn nhất từ (0,0) đến (n-1,n-1), đi được 8 hướng (4 trục + 4 chéo). Độ dài đường đi = số ô đi qua (kể cả start và end). Trả -1 nếu không đi được.

Ví dụ

Input:  grid = [[0,0,0],
                [1,1,0],
                [1,1,0]]
Output: 4
Giải thích: (0,0) → (0,1) → (1,2) → (2,2)

Ràng buộc

Clarifying questions

Hướng tiếp cận

BFS từ (0,0) với 8 hướng. Mỗi cạnh trọng số 1 (mỗi bước = 1 ô).

Code Python 3

from collections import deque
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
            return -1
        if n == 1:
            return 1

        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        queue = deque([(0, 0, 1)])     # (r, c, steps)
        grid[0][0] = 1                  # mark visited
        while queue:
            r, c, steps = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if (nr, nc) == (n - 1, n - 1):
                        return steps + 1
                    grid[nr][nc] = 1
                    queue.append((nr, nc, steps + 1))
        return -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

10.6 Snakes and Ladders (LC 909)

Đề bài

Cho bàn cờ n × n đánh số ô theo zigzag (như cờ rắn rồng). board[i][j] = -1 nghĩa là ô bình thường; nếu >= 1, đó là rắn/thang đưa bạn đến ô số đó.

Mỗi bước, từ ô hiện tại bạn được tung xúc xắc (6 mặt) đi 1..6 bước; nếu ô đến có rắn/thang, tự động đi tiếp đến ô đích. Tìm số lần tung tối thiểu để đến ô n*n cuối cùng. Trả -1 nếu không thể.

Ví dụ

Input:  board =
        [[-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,35,-1,-1,13,-1],
         [-1,-1,-1,-1,-1,-1],
         [-1,15,-1,-1,-1,-1]]
Output: 4

Ràng buộc

Clarifying questions

Hướng tiếp cận

State space: mỗi ô đánh số 1..n². Từ ô s, có thể đi đến ô s+1, s+2, ..., s+6 (rồi nhảy nếu có rắn/thang). Mỗi cạnh = 1 lần tung → BFS ra số tung tối thiểu.

Trick zigzag → tọa độ: - Hàng (từ dưới): (label - 1) // n. - Cột tuỳ hướng hàng: chẵn từ dưới thì trái → phải, lẻ thì phải → trái.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        def label_to_pos(label: int) -> tuple[int, int]:
            quot, rem = divmod(label - 1, n)
            row = n - 1 - quot
            col = rem if quot % 2 == 0 else n - 1 - rem
            return row, col

        target = n * n
        visited = {1}
        queue = deque([(1, 0)])     # (square, throws)
        while queue:
            square, throws = queue.popleft()
            for d in range(1, 7):
                nxt = square + d
                if nxt > target:
                    break
                r, c = label_to_pos(nxt)
                if board[r][c] != -1:
                    nxt = board[r][c]
                if nxt == target:
                    return throws + 1
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, throws + 1))
        return -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

BFS state design (đa dạng hơn bạn nghĩ)

State Bài tiêu biểu
node Shortest path unweighted graph
(r, c) Grid (Number of Islands, 01 Matrix)
word Word Ladder
(r, c, k_remaining) Shortest Path with K Obstacles
board_serialized Sliding Puzzle, Open Lock
bitmask_visited Shortest Path Visiting All Nodes
(node, parity) Bipartite, chẵn/lẻ bước

Word Ladder — neighbor generation

Snakes & Ladders — 1D ↔︎ 2D

Board n×n serpentine: index i (1..n²) → tọa độ:

row_from_bottom = (i - 1) // n     # 0 = bottom row
col_in_row      = (i - 1) % n
r = n - 1 - row_from_bottom
c = col_in_row if row_from_bottom % 2 == 0 else n - 1 - col_in_row

Bug điển hình: quên đảo chiều hàng lẻ, hoặc index 0/1.

Distance: level BFS vs lưu trong queue

Chương 11 — Depth-First Search (DFS)

DFS đi sâu nhất có thể trước khi quay lui. Đây là pattern tự nhiên cho mọi bài cây / đồ thị có cấu trúc đệ quy: depth, path sum, validate, LCA, … Chương này tập trung DFS trên cây — pattern dễ thuộc lòng và rất hay trong phỏng vấn. DFS trên grid sẽ ở Chương 12 (Island Matrix).

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

3 mẫu DFS trên cây: 1. Top-down: truyền state xuống (vd. path_so_far, current_sum). 2. Bottom-up: leaf trả giá trị lên, node tổng hợp từ con. 3. Hỗn hợp: vừa truyền xuống vừa nhận lên.

Định dạng input (áp dụng cho TẤT CẢ bài tree trong chương)

Mọi bài trong chương 10/11/22 (tree) dùng TreeNode chuẩn của LeetCode:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Template code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


# 1) Bottom-up: trả về giá trị từ con
def dfs_bottom_up(node) -> int:
    if not node:
        return 0
    left = dfs_bottom_up(node.left)
    right = dfs_bottom_up(node.right)
    return combine(node.val, left, right)


# 2) Top-down: truyền state xuống
def dfs_top_down(node, state) -> None:
    if not node:
        return
    new_state = update(state, node.val)
    if is_leaf(node):
        # ... ghi kết quả ...
        return
    dfs_top_down(node.left, new_state)
    dfs_top_down(node.right, new_state)


# 3) Iterative DFS bằng stack
def dfs_iter(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        # ... visit node ...
        stack.append(node.right)
        stack.append(node.left)     # left lên top trước

Bài tự luyện cuối chương

11.1 Maximum Depth of Binary Tree (LC 104)

Đề bài

Cho root của binary tree. Trả về độ sâu lớn nhất (số node trên path dài nhất từ root đến lá).

Ví dụ

Input:  root = [3, 9, 20, null, null, 15, 7]   (LC level-order serialize)

        Cây thực tế:
              3
             / \
            9   20
               /  \
              15   7

Output: 3

Ràng buộc

Clarifying questions

Hướng tiếp cận

Bottom-up một dòng:

depth(node) = 1 + max(depth(left), depth(right)), base case rỗng → 0.

Code Python 3

class Solution:
    def maxDepth(self, root) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

11.2 Path Sum II (LC 113)

Đề bài

Cho root và số targetSum. Trả về tất cả đường đi root-to-leaf có tổng giá trị bằng targetSum.

Ví dụ

Input:  root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
        targetSum = 22

        Cây thực tế:
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1

Output: [[5,4,11,2], [5,8,4,5]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

DFS top-down + backtracking: - Đi xuống mỗi node, giảm target còn lại và append node vào path. - Tại leaf: nếu target == leaf.val → copy path vào kết quả. - Khi quay lên (sau khi duyệt xong các con) → path.pop() để khôi phục trạng thái.

Hình minh hoạ — đường đi 5 → 4 → 11 → 2 cho target = 22:

DFS(5, target=22, path=[]):
  path=[5], remaining=17
  DFS(4, 17):
    path=[5,4], remaining=13
    DFS(11, 13):
      path=[5,4,11], remaining=2
      DFS(7, 2):  leaf, 7 != 2 → bỏ
                  pop → path=[5,4,11]
      DFS(2, 2):  leaf, 2 == 2 → ADD [5,4,11,2] vào result
                  pop → path=[5,4,11]
      pop → path=[5,4]
    pop → path=[5]
  ...

Code Python 3

from typing import List, Optional

class Solution:
    def pathSum(self, root: Optional["TreeNode"], targetSum: int) -> List[List[int]]:
        result: list[list[int]] = []
        path: list[int] = []

        def dfs(node, remaining: int) -> None:
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right and remaining == 0:
                result.append(path.copy())
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()                  # backtrack

        dfs(root, targetSum)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

11.3 All Paths From Source to Target (LC 797)

Đề bài

Cho DAG graph (mảng adjacency list, node i có hàng xóm graph[i]). Trả về tất cả đường đi từ node 0 đến node n - 1.

Ví dụ

Input:  graph = [[1,2],[3],[3],[]]
        # đồ thị:  0 → 1 → 3
        #          0 → 2 → 3
Output: [[0,1,3], [0,2,3]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

DAG ⇒ không có chu trình ⇒ không cần visited. DFS từ 0, mỗi đến n-1 ghi path.

Code Python 3

from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        result: list[list[int]] = []
        path: list[int] = [0]

        def dfs(node: int) -> None:
            if node == n - 1:
                result.append(path.copy())
                return
            for nb in graph[node]:
                path.append(nb)
                dfs(nb)
                path.pop()

        dfs(0)
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

11.4 Validate Binary Search Tree (LC 98)

Đề bài

Cho root. Kiểm tra cây có phải BST hợp lệ không, theo định nghĩa: - Mọi node con trái: value strictly less than node hiện tại. - Mọi node con phải: value strictly greater than node hiện tại. - Cả 2 subtree đều là BST.

Ví dụ

Input:  root = [2, 1, 3]
        Cây thực tế:
              2
             / \
            1   3
Output: true

Input:  root = [5, 1, 4, null, null, 3, 6]
        Cây thực tế:
              5
             / \
            1   4
               / \
              3   6
Output: false
        (node 3 ở subtree phải của 5, nhưng 3 < 5 → vi phạm BST)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách sai phổ biến — chỉ check node.left.val < node.val < node.right.val. Sai vì BST yêu cầu TOÀN BỘ subtree trái < node, không chỉ child trực tiếp.

Ví dụ ngược:

    5
   / \
  1   4
     / \
    3   6

Tại node 5: 4 < 5 (OK), 1 < 5 (OK). Tại node 4: 3 < 4 < 6 (OK). Local check pass, nhưng 3 < 5 trong subtree phải → sai.

Cách đúng — DFS truyền (low, high) bound:

dfs(node, low, high): node phải thoả low < node.val < high. Khi đi xuống: - Trái: bound mới (low, node.val). - Phải: bound mới (node.val, high).

Cách 2 — Inorder traversal phải sắp xếp tăng strict.

BST inorder = sequence sorted. Duyệt inorder, kiểm tra mỗi value > value trước.

Code Python 3

import math
from typing import Optional

class Solution:
    """Cách 1 — DFS với bound (low, high)."""

    def isValidBST(self, root: Optional["TreeNode"]) -> bool:

        def dfs(node, low: float, high: float) -> bool:
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return dfs(node.left, low, node.val) and \
                   dfs(node.right, node.val, high)

        return dfs(root, -math.inf, math.inf)


class SolutionInorder:
    """Cách 2 — inorder traversal."""

    def isValidBST(self, root) -> bool:
        self.prev = -math.inf

        def inorder(node) -> bool:
            if not node:
                return True
            if not inorder(node.left):
                return False
            if node.val <= self.prev:
                return False
            self.prev = node.val
            return inorder(node.right)

        return inorder(root)

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

11.5 House Robber III (LC 337)

Đề bài

Cho root của binary tree (LC level-order serialize, vd [3,2,3,null,3,null,1]). Nhà ở mỗi node có giá trị node.val. Tên trộm không thể trộm 2 nhà kề nhau (parent ↔︎ child). Trả về số tiền tối đa trộm được.

Ví dụ

Input:  root = [3, 2, 3, null, 3, null, 1]
        Cây thực tế:
              3
             / \
            2   3
             \   \
              3   1
Output: 7
        (trộm 3 + 3 + 1 = 7)

Input:  root = [3, 4, 5, 1, 3, null, 1]
        Cây thực tế:
              3
             / \
            4   5
           / \   \
          1   3   1
Output: 9
        (trộm 4 + 5 = 9)

Ràng buộc

Clarifying questions

Hướng tiếp cận

DP trên cây — mỗi node trả về 2 giá trị: - rob_this = max tiền nếu trộm node này (con không trộm). - skip_this = max tiền nếu không trộm node này (con tuỳ ý).

Quan hệ: - rob_this = node.val + left.skip + right.skip - skip_this = max(left.rob, left.skip) + max(right.rob, right.skip)

Đáp án = max(root.rob, root.skip).

Hình minh hoạ:

       3
      / \
     2   3
      \   \
       3   1

DFS bottom-up:
  node 3 (lá phải-phải): rob=3, skip=0
  node 3 (lá phải-trái): rob=3, skip=0
  node 1 (lá phải-phải-right): rob=1, skip=0

  node 2: rob = 2 + 0 (no left) + 0 (3 skip) = 2
          skip = 0 + max(3, 0) = 3
  node 3 (right): rob = 3 + max(0, 0)(no left) + 0 = 3
                  skip = 0 + max(1, 0) = 1

  node 3 (root): rob = 3 + 3 (no rob của 2) + 1 (no rob của 3-right) = 7
                 skip = max(2,3) + max(3,1) = 3 + 3 = 6

Đáp án: max(7, 6) = 7

Code Python 3

from typing import Optional, Tuple

class Solution:
    def rob(self, root: Optional["TreeNode"]) -> int:

        def dfs(node) -> Tuple[int, int]:
            """Trả về (rob_this, skip_this)."""
            if not node:
                return 0, 0
            l_rob, l_skip = dfs(node.left)
            r_rob, r_skip = dfs(node.right)
            rob_this = node.val + l_skip + r_skip
            skip_this = max(l_rob, l_skip) + max(r_rob, r_skip)
            return rob_this, skip_this

        return max(dfs(root))

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

11.6 Lowest Common Ancestor of a Binary Tree (LC 236)

Đề bài

Cho root của binary tree (không phải BST) và 2 node p, q. Tìm lowest common ancestor (LCA) — node thấp nhất có cả p và q trong subtree của nó.

Ví dụ

Input:  root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]
        Cây thực tế:
              3
             / \
            5   1
           / \ / \
          6  2 0  8
            / \
           7   4

Input:  p = 5, q = 1   → Output: 3
Input:  p = 5, q = 4   → Output: 5   (5 là tổ tiên của chính nó)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Insight tinh tế: Tại mỗi node: - Nếu node == p hoặc node == q → trả về node luôn. - Đệ quy trên left và right. - Nếu cả 2 đệ quy đều trả về non-None → node là LCA. - Nếu chỉ 1 cái trả non-None → trả cái đó (nghĩa là cả p và q đều ở 1 bên).

Code Python 3

from typing import Optional

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root is p or root is q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root          # p và q ở 2 nhánh → root là LCA
        return left if left else right

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Traversal order cheat sheet

Traversal Khi nào dùng
Pre-order (root → L → R) Serialize, clone, copy
In-order (L → root → R) BST sorted output, kth smallest
Post-order (L → R → root) Tổng hợp từ con (tree DP, diameter)
Level-order (BFS) Theo tầng, distance

DFS return value design (cốt lõi tree DP)

def dfs(node):
    if not node: return base
    L = dfs(node.left)
    R = dfs(node.right)
    # combine L, R với node.val → ans cho subtree này
    # CẬP NHẬT đáp số toàn cục nếu cần
    return result_to_pass_up

Validate BST — global bounds

House Robber III — (rob, skip) trace

Cây:

    3
   / \
  2   3
   \   \
    3   1

Post-order trả về (rob_this, skip_this): - Lá 3 (left của 2): (3, 0). - Lá 1 (right của 3): (1, 0). - Node 2: rob = 2 + 0 = 2, skip = max(3,0) = 3 → (2, 3). - Node 3 (right of root): rob = 3 + 0 = 3, skip = max(1,0) = 1 → (3, 1). - Root 3: rob = 3 + 3 + 1 = 7, skip = max(2,3) + max(3,1) = 3 + 3 = 6 → max(7,6) = 7.

LCA variants — phân biệt

Loại cây Cách
Binary tree thường Đệ quy bottom-up, trả node nếu chứa p hoặc q (LC 236)
BST So sánh value với root, đi 1 nhánh (LC 235) — O(log n)
Có parent pointer Hash các tổ tiên của p, đi từ q lên

Chương 12 — Island Matrix Traversal

Grid 2D thực ra là graph ngầm: mỗi ô là 1 node, 4 ô kề (lên/xuống/trái/ phải) là cạnh. Mọi bài “đảo” / “tô màu vùng” / “flood fill” đều là DFS/BFS trên graph này. Chương này dạy bạn 4 trick đặc trưng cho grid: (1) flood fill, (2) multi-source BFS từ biên, (3) reverse thinking (đánh dấu cái không cần), (4) mutate input để mark visited.

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

Template code

from collections import deque
from typing import List

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 1) Flood fill DFS (đệ quy)
def flood_fill(grid: List[List[int]], r: int, c: int, marker: int) -> int:
    rows, cols = len(grid), len(grid[0])
    if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
        return 0
    grid[r][c] = marker             # mark visited
    size = 1
    for dr, dc in DIRS:
        size += flood_fill(grid, r + dr, c + dc, marker)
    return size


# 2) Multi-source BFS từ tất cả biên hoặc tất cả ô đặc biệt
def multi_source_bfs(grid, sources):
    queue = deque(sources)
    visited = set(sources)
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))
    return visited

Bài tự luyện cuối chương

12.1 Number of Islands (LC 200)

Đề bài

Cho grid m × n với '1' = đất, '0' = nước. Đảo là vùng đất liên thông (4 hướng). Đếm số đảo.

Ví dụ

Input:
[["1","1","1","1","0"],
 ["1","1","0","1","0"],
 ["1","1","0","0","0"],
 ["0","0","0","0","0"]]
Output: 1   (cả vùng "1" liên thông)

Input:
[["1","1","0","0","0"],
 ["1","1","0","0","0"],
 ["0","0","1","0","0"],
 ["0","0","0","1","1"]]
Output: 3   (góc trái-trên, giữa, góc phải-dưới)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Pattern flood fill kinh điển. Duyệt mỗi ô: - Nếu là '1' và chưa visited → tăng counter, gọi DFS/BFS đánh dấu toàn bộ đảo này thành visited (đổi '1' → '0' để khỏi dùng set riêng).

Hình minh hoạ với grid 4×5 thứ 2:

Bước 1, ô (0,0) = '1' → DFS:
[1 1 0 0 0]      [* * 0 0 0]
[1 1 0 0 0]  →   [* * 0 0 0]
[0 0 1 0 0]      [0 0 1 0 0]
[0 0 0 1 1]      [0 0 0 1 1]
                 (đảo 1 đánh dấu)

Bước 2, gặp ô (2,2) = '1' → DFS (chỉ đánh dấu chính nó):
[* * 0 0 0]
[* * 0 0 0]
[0 0 * 0 0]
[0 0 0 1 1]

Bước 3, gặp ô (3,3) = '1' → DFS:
[* * 0 0 0]
[* * 0 0 0]
[0 0 * 0 0]
[0 0 0 * *]

Đếm: 3 đảo

Code Python 3

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        rows, cols = len(grid), len(grid[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
                return
            grid[r][c] = '0'              # mark visited
            for dr, dc in DIRS:
                dfs(r + dr, c + dc)

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

12.2 Max Area of Island (LC 695)

Đề bài

Cùng grid với 0/1. Trả về diện tích lớn nhất của một đảo (số ô ‘1’ của nó), hoặc 0 nếu không có đảo nào.

Ví dụ

Input:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

Ràng buộc

Clarifying questions

Hướng tiếp cận

Variant của bài 12.1, nhưng DFS trả về size thay vì void. Lấy max qua các lần khởi động DFS.

Code Python 3

from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r: int, c: int) -> int:
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + sum(dfs(r + dr, c + dc) for dr, dc in DIRS)

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))
        return best

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

12.3 Surrounded Regions (LC 130)

Đề bài

Cho grid chứa 'X' và 'O'. Lật mọi vùng 'O' được bao quanh hoàn toàn bởi 'X' (vùng không chạm biên grid) thành 'X'. Vùng 'O' chạm biên được giữ nguyên.

Ví dụ

Input:  board = [['X','X','X','X'],
                 ['X','O','O','X'],
                 ['X','X','O','X'],
                 ['X','O','X','X']]
Output: board = [['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','X','X','X'],
                 ['X','O','X','X']]

(mutate in-place; 'O' ở (3,1) chạm biên dưới → giữ;
 cụm 'O' bên trong bị bao quanh → lật thành 'X')

Ràng buộc

Clarifying questions

Hướng tiếp cận

Reverse thinking — đây là pattern cực hay: - Thay vì tìm vùng 'O' bị bao, ta tìm vùng 'O' chạm biên (rất dễ). - Đánh dấu chúng (vd. đổi tạm thành '#'). - Cuối cùng: - '#' → 'O' (giữ). - 'O' còn lại → 'X' (lật).

Hình minh hoạ:

Grid ban đầu:               Sau DFS từ các 'O' biên (đánh dấu '#'):
X X X X                     X X X X
X O O X                     X O O X     (O ở (1,1),(1,2) KHÔNG chạm biên,
X X O X         →           X X O X       không bị mark)
X O X X                     X # X X     (O ở (3,1) chạm biên → mark)

Quét cuối:
'#' → 'O'; 'O' → 'X':
X X X X
X X X X
X X X X
X O X X

Code Python 3

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        rows, cols = len(board), len(board[0])

        def dfs(r: int, c: int) -> None:
            if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != 'O':
                return
            board[r][c] = '#'
            dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

        # 1. DFS từ mọi 'O' ở biên — mark thành '#'.
        for r in range(rows):
            dfs(r, 0)
            dfs(r, cols - 1)
        for c in range(cols):
            dfs(0, c)
            dfs(rows - 1, c)

        # 2. Lật: '#' → 'O' (giữ); 'O' → 'X' (lật).
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == '#':
                    board[r][c] = 'O'

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

12.4 Pacific Atlantic Water Flow (LC 417)

Đề bài

Cho ma trận chiều cao heights[i][j] đại diện chiều cao đảo. Mép trái và mép trên giáp Thái Bình Dương; mép phải và mép dưới giáp Đại Tây Dương. Nước chảy từ ô (r, c) sang ô kề có chiều cao ≤ (r, c).

Trả về tất cả (r, c) mà nước từ đó có thể chảy ra cả 2 đại dương.

Ví dụ

Input:  heights = [[1,2,2,3,5],
                   [3,2,3,4,4],
                   [2,4,5,3,1],
                   [6,7,1,4,5],
                   [5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Forward thinking — TLE. Với mỗi ô, BFS xem chảy được ra biên nào. Worst-case O((mn)²).

Reverse thinking — O(m · n).

Thay vì hỏi “ô nào chảy được ra biển?”, ta hỏi “biển có thể vươn lên tới ô nào?”. Biển vươn lên cao theo quy tắc: chỉ vào ô có chiều cao ≥ ô hiện tại.

Hình minh hoạ — Pacific reach (P) và Atlantic reach (A) trên ma trận 5x5:

P P P P P/A                   A A A A A
P . . . A             P/A . . . A
P . . . A             P . . . A
P/A . . . A             P . . . A
P/A A A A A             P P P P P

Giao P ∩ A = các ô có cả 2 → đáp án.

Code Python 3

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights:
            return []
        rows, cols = len(heights), len(heights[0])
        pacific: set[tuple[int, int]] = set()
        atlantic: set[tuple[int, int]] = set()

        def dfs(r: int, c: int, visited: set, prev_h: int) -> None:
            if (r, c) in visited:
                return
            if not (0 <= r < rows and 0 <= c < cols):
                return
            if heights[r][c] < prev_h:    # biển không vươn được vào ô thấp hơn
                return
            visited.add((r, c))
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                dfs(r + dr, c + dc, visited, heights[r][c])

        # Pacific: biên trái + biên trên.
        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
        # Atlantic: biên phải + biên dưới.
        for r in range(rows):
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])
        for c in range(cols):
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])

        return [[r, c] for r, c in pacific & atlantic]

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

12.5 Walls and Gates (LC 286)

Đề bài

Cho rooms: ma trận m × n các số nguyên với 3 giá trị có ý nghĩa: - -1 = tường (cản đường). - 0 = cổng (gate). - INF (= 2³¹ - 1) = phòng trống.

Điền vào mỗi phòng trống khoảng cách ngắn nhất (số bước 4 hướng) đến cổng gần nhất. Nếu phòng không đến được cổng nào, giữ INF.

Ví dụ

Input:  rooms = [[INF, -1,  0, INF],
                 [INF,INF,INF, -1],
                 [INF, -1,INF, -1],
                 [  0, -1,INF,INF]]
        (-1 = tường, 0 = cổng, INF = phòng trống)

Output: rooms = [[3, -1, 0, 1],
                 [2,  2, 1,-1],
                 [1, -1, 2,-1],
                 [0, -1, 3, 4]]
        (mutate in-place; mỗi ô = khoảng cách 4 hướng tới cổng gần nhất)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Multi-source BFS — đẩy tất cả các cổng vào queue cùng lúc. Lan toả ra ngoài, mỗi ô đặt distance = số bước từ cổng gần nhất.

Vì sao multi-source > BFS từng cổng? Multi-source O(mn), BFS từng cổng O(gates · mn) — gates có thể O(mn).

Code Python 3

from collections import deque
from typing import List

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        if not rooms:
            return
        rows, cols = len(rooms), len(rooms[0])
        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if rooms[r][c] == 0:
                    queue.append((r, c))

        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                # Chỉ "ghi" vào ô INF — vì BFS, lần đầu ghi đã là min.
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.append((nr, nc))

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

12.6 01 Matrix (LC 542)

Đề bài

Cho ma trận mat chỉ chứa 0 và 1. Trả về ma trận cùng kích thước, mỗi ô = khoảng cách (số bước 4 hướng) đến số 0 gần nhất.

Ví dụ

Input:  mat = [[0,0,0],
               [0,1,0],
               [1,1,1]]
Output:       [[0,0,0],
               [0,1,0],
               [1,2,1]]
        (mỗi ô = khoảng cách Manhattan tới ô '0' gần nhất)

Ràng buộc

Clarifying questions

Hướng tiếp cận

Y hệt Walls and Gates: multi-source BFS từ tất cả ô 0. Distance ban đầu của ô 0 = 0, các ô 1 chưa biết.

Cách khác — DP 2 lượt, O(m · n): - Lượt 1 (trên-trái → dưới-phải): dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + 1. - Lượt 2 (dưới-phải → trên-trái): dp[r][c] = min(dp[r][c], dp[r+1][c]+1, dp[r][c+1]+1).

Cả 2 đều O(m · n). BFS trực quan hơn; DP gọn space.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        INF = float('inf')
        dist = [[INF] * cols for _ in range(rows)]

        queue: deque[tuple[int, int]] = deque()
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    queue.append((r, c))

        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        return dist


class SolutionDP:
    """Cách DP 2 lượt — gọn space (in-place khi cho phép)."""

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        INF = rows + cols + 1
        dist = [[0 if mat[r][c] == 0 else INF
                 for c in range(cols)] for r in range(rows)]
        # Lượt 1: trên-trái → dưới-phải.
        for r in range(rows):
            for c in range(cols):
                if dist[r][c] == 0:
                    continue
                top = dist[r-1][c] if r > 0 else INF
                left = dist[r][c-1] if c > 0 else INF
                dist[r][c] = min(top, left) + 1
        # Lượt 2: dưới-phải → trên-trái.
        for r in range(rows - 1, -1, -1):
            for c in range(cols - 1, -1, -1):
                if dist[r][c] == 0:
                    continue
                bot = dist[r+1][c] + 1 if r < rows - 1 else INF
                right = dist[r][c+1] + 1 if c < cols - 1 else INF
                dist[r][c] = min(dist[r][c], bot, right)
        return dist

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Matrix traversal checklist

  1. Direction array: dirs = [(-1,0),(1,0),(0,-1),(0,1)] (4-conn) hoặc 8-conn.
  2. Bounds: 0 <= nr < R and 0 <= nc < C.
  3. Visited: in-place mark (đổi '1' → '0' hoặc #) hay set?
  4. Mutation OK? Hỏi interviewer; nếu không, dùng visited 2D.
  5. Stack overflow với DFS đệ quy: grid 1000×1000 có thể vượt limit. Dùng iterative stack hoặc BFS.

Boundary-first technique

Cho bài Surrounded Regions (LC 130) và Pacific Atlantic (LC 417): - “Cell không thoả điều kiện” = cell kết nối với biên. - Seed BFS/DFS từ biên, đánh dấu cell reach được; cell còn lại là cell bị bao quanh.

Multi-source BFS

Cho 01 Matrix (LC 542) và Walls and Gates (LC 286): - Bỏ tất cả nguồn vào queue ban đầu (cell 0 cho 542, cổng 0 cho 286). - BFS level → distance lan ra. Mỗi cell được visit một lần ⇒ O(R·C).

In-place mark vs visited set

Tiêu chí In-place Set/2D bool
Bộ nhớ phụ O(1) O(R·C)
Mutate input? Có Không
Concurrency/restore Khó Dễ
Ưu tiên Khi cho phép & cần O(1) extra Khi grid immutable hoặc cần re-run

Chương 13 — Topological Sort

Topological Sort sắp xếp đỉnh của DAG (Directed Acyclic Graph) sao cho mọi cạnh u → v thì u đứng trước v trong thứ tự. Đây là pattern bắt buộc cho mọi bài “hoàn thành theo thứ tự phụ thuộc”: build system, task scheduler, course prerequisites, …

Mục tiêu chương

Sau chương này, bạn sẽ:

Quy ước hướng cạnh

Một trong những lỗi phổ biến nhất khi giải topo sort là vẽ cạnh sai chiều. Vì lý do này, toàn bộ sách dùng một quy ước duy nhất:

Mô tả thực tế              Cạnh trong graph        Indegree
─────────────────────────────────────────────────────────────
"a must come before b"     a → b                   indeg[b] += 1
"b depends on a"           a → b                   indeg[b] += 1
"a is prerequisite of b"   a → b                   indeg[b] += 1
─────────────────────────────────────────────────────────────
LC 207/210 input:          prerequisites[i] = [course, prereq]
                           tức là [b, a] dạng "to do b, must do a"
                           → cạnh a → b (prereq → course)
─────────────────────────────────────────────────────────────
LC 269 Alien Dict:         words[i] < words[i+1] theo lex
                           → ký tự khác nhau đầu tiên: c1 < c2
                           → cạnh c1 → c2

Kahn’s invariant: Pop node có indeg == 0 ↔︎ “không còn ai phải xong trước nó”.

Mọi bài Topo trong cuốn sách dùng convention u → v nghĩa là u xong trước v. Khi gặp đề có wording khác, bước đầu tiên nên là vẽ 2–3 cạnh ra giấy để kiểm tra rằng hướng cạnh trong code khớp đúng với mô tả của đề bài.

Khi nào dùng pattern này?

2 thuật toán kinh điển:

  1. Kahn’s algorithm (BFS) — đếm indegree, đẩy node có indeg=0 vào queue.
  2. DFS với post-order — duyệt DFS, push node vào stack khi xong; reverse stack.

Cả 2 đều O(V + E). Mặc định mình dùng Kahn vì nó dễ extend cho “min levels”.

Template code

from collections import defaultdict, deque
from typing import List

def topo_sort_kahn(n: int, edges: List[tuple]) -> List[int]:
    graph = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1

    queue = deque(i for i in range(n) if indeg[i] == 0)
    order: list[int] = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    return order if len(order) == n else []     # rỗng = có chu trình

Bài tự luyện cuối chương

13.1 Course Schedule II (LC 210)

Đề bài

Cho numCourses khoá và prerequisites[i] = [a, b] (học a cần b xong trước). Trả về thứ tự học hợp lệ, hoặc [] nếu có chu trình.

Ví dụ

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]   (hoặc [0, 2, 1, 3])
Giải thích:
  Cạnh: 0 → 1, 0 → 2, 1 → 3, 2 → 3.

Ràng buộc

Clarifying questions

Hướng tiếp cận

Kahn’s algorithm — y hệt template. Khi pop node, push vào order. Cuối: nếu len(order) == numCourses → trả order; ngược lại có chu trình.

Hình minh hoạ với [[1,0],[2,0],[3,1],[3,2]]:

Graph:        0
             / \
            1   2
             \ /
              3

indeg ban đầu: [0, 1, 1, 2]
queue = [0]                   (indeg 0)

Pop 0 → order=[0]
  giảm indeg[1], indeg[2] → [_, 0, 0, 2]
  queue = [1, 2]

Pop 1 → order=[0, 1]
  giảm indeg[3] → [_, _, _, 1]

Pop 2 → order=[0, 1, 2]
  giảm indeg[3] → [_, _, _, 0]
  queue = [3]

Pop 3 → order=[0, 1, 2, 3]

len(order)=4=numCourses → trả [0, 1, 2, 3]  ✓

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1

        queue = deque(i for i, d in enumerate(indeg) if d == 0)
        order: list[int] = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return order if len(order) == numCourses else []

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

13.2 Alien Dictionary (LC 269)

Đề bài

Một ngôn ngữ ngoài hành tinh dùng chữ cái Latin nhưng thứ tự khác. Cho danh sách words đã sắp xếp theo thứ tự đó. Hãy tìm 1 thứ tự chữ cái hợp lệ (string các chữ cái). Trả "" nếu mâu thuẫn.

Ví dụ

Input:  words = ["wrt","wrf","er","ett","rftt"]
        (mảng từ đã sort theo thứ tự alphabet của ngôn ngữ ngoài hành tinh)
Output: "wertf"  (1 thứ tự chữ cái hợp lệ; có thể có nhiều đáp án)
Giải thích:
  wrt < wrf  → t < f
  wrf < er   → w < e
  er  < ett  → r < t
  ett < rftt → e < r
  → topo: w < e < r < t < f

Input:  words = ["z","x","z"]
Output: ""             (mâu thuẫn cyclic: z<x từ cặp 1 nhưng x<z từ cặp 2)

Ràng buộc

Clarifying questions

Hướng tiếp cận

2 bước:

  1. Trích quan hệ thứ tự từ các cặp (words[i], words[i+1]) liền kề:
  2. Topological sort trên các quan hệ thu được.

Hình minh hoạ với ["wrt","wrf","er","ett","rftt"]:

Cặp 1: wrt vs wrf
  vị trí khác đầu: index 2 → t < f
  → cạnh t → f

Cặp 2: wrf vs er
  vị trí khác đầu: index 0 → w < e
  → cạnh w → e

Cặp 3: er vs ett
  vị trí khác đầu: index 1 → r < t
  → cạnh r → t

Cặp 4: ett vs rftt
  vị trí khác đầu: index 0 → e < r
  → cạnh e → r

Graph: w → e → r → t → f
Topo: w, e, r, t, f → "wertf"

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Khởi tạo indeg cho tất cả ký tự xuất hiện.
        indeg = {ch: 0 for w in words for ch in w}
        graph = defaultdict(set)

        # Trích quan hệ từ các cặp kề nhau.
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            # Edge case mâu thuẫn tiền tố.
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        indeg[c2] += 1
                    break

        # Kahn's.
        queue = deque(ch for ch, d in indeg.items() if d == 0)
        order: list[str] = []
        while queue:
            ch = queue.popleft()
            order.append(ch)
            for nb in graph[ch]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return ''.join(order) if len(order) == len(indeg) else ""

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

13.3 Minimum Height Trees (LC 310)

Đề bài

Input: n (số đỉnh) và edges: List[List[int]] — danh sách n-1 cạnh [u, v] mô tả tree vô hướng. Đỉnh đánh số 0..n-1.

Tìm tất cả root có thể chọn để chiều cao tree là min. Trả về danh sách root đó (có thể có 1 hoặc 2).

Ví dụ

Input:  n=6, edges = [[0,3],[1,3],[2,3],[4,3],[5,4]]
Tree:    0   1   2
          \  |  /
           \ | /
             3
             |
             4
             |
             5
Output: [3, 4]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Insight: Centroid của tree (gồm 1 hoặc 2 node) tối thiểu hoá chiều cao. Cách tìm: BFS từ các lá, “gọt vỏ” dần.

Quy trình: 1. Xây graph + tính degree. 2. Đẩy mọi lá (degree == 1) vào queue. 3. Lặp: pop một lớp lá, giảm degree hàng xóm, lá mới (degree == 1) → queue. 4. Khi còn ≤ 2 node → đó là centroid(s).

Hình minh hoạ:

Lớp đầu — lá: [0, 1, 2, 5]
Gọt → còn lại: [3, 4]
                3 (degree=1 sau gọt), 4 (degree=1 sau gọt)
→ ≤ 2 node → centroids = [3, 4]

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        graph = defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        leaves = deque(i for i in range(n) if len(graph[i]) == 1)
        remaining = n
        while remaining > 2:
            size = len(leaves)
            remaining -= size
            for _ in range(size):
                leaf = leaves.popleft()
                nb = next(iter(graph[leaf]))    # lá có đúng 1 hàng xóm
                graph[nb].remove(leaf)
                if len(graph[nb]) == 1:
                    leaves.append(nb)
        return list(leaves)

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

13.4 Sort Items by Groups Respecting Dependencies (LC 1203)

Đề bài

Cho n items, mỗi item thuộc 1 group (group[i] = -1 nếu chưa thuộc nhóm nào, sẽ phân nhóm riêng). Cho beforeItems[i] = các item phải làm trước item i. Hãy sắp xếp items sao cho: - Tôn trọng beforeItems. - Các item cùng group đứng liền nhau.

Trả [] nếu không khả thi.

Ví dụ

Input:  n=8, m=2, group=[-1,-1,1,0,0,1,0,-1], beforeItems=[[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Hai lần topo sort: 1. Sort các group với nhau (item-level edge i → j mà khác group → group-edge). 2. Trong mỗi group, sort các item của nó. 3. Concat kết quả: dùng order group, mỗi group ghi tất cả item của nó theo order item.

Pre-processing: mọi item có group[i] == -1 → gán group mới riêng để tránh “không nhóm” ảnh hưởng.

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    def sortItems(
        self, n: int, m: int,
        group: List[int], beforeItems: List[List[int]]
    ) -> List[int]:
        # Gán group riêng cho item -1.
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1

        item_graph = defaultdict(list)
        item_indeg = [0] * n
        group_graph = defaultdict(set)
        group_indeg = defaultdict(int)

        for cur, befores in enumerate(beforeItems):
            for prev in befores:
                item_graph[prev].append(cur)
                item_indeg[cur] += 1
                if group[prev] != group[cur]:
                    if group[cur] not in group_graph[group[prev]]:
                        group_graph[group[prev]].add(group[cur])
                        group_indeg[group[cur]] += 1

        def topo(nodes, graph, indeg) -> List[int]:
            queue = deque(x for x in nodes if indeg[x] == 0)
            out: list = []
            while queue:
                x = queue.popleft()
                out.append(x)
                for nb in graph[x]:
                    indeg[nb] -= 1
                    if indeg[nb] == 0:
                        queue.append(nb)
            return out if len(out) == len(nodes) else []

        item_order = topo(range(n), item_graph, item_indeg)
        if not item_order:
            return []
        group_order = topo(range(m), group_graph, group_indeg)
        if not group_order:
            return []

        # Gom theo group theo thứ tự group, các item trong group giữ thứ tự item_order.
        bucket: dict[int, list[int]] = defaultdict(list)
        for item in item_order:
            bucket[group[item]].append(item)
        result: list[int] = []
        for g in group_order:
            result.extend(bucket[g])
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

13.5 Sequence Reconstruction (LC 444)

Đề bài

Cho nums (1 hoán vị của 1..n) và sequences (list các sub-sequence). Hãy kiểm tra nums có phải là topological order duy nhất suy ra từ sequences hay không.

Ví dụ

Input:  nums = [1, 2, 3], sequences = [[1,2],[1,3]]
Output: False
Giải thích: từ [1,2] và [1,3] → có thể là [1,2,3] hoặc [1,3,2] → không unique.

Input:  nums = [1, 2, 3], sequences = [[1,2],[1,3],[2,3]]
Output: True

Ràng buộc

Clarifying questions

Hướng tiếp cận

Chạy Kahn’s. Để unique, mỗi level chỉ có đúng 1 node indeg == 0 — nếu có ≥ 2 ⇒ có nhiều topo order ⇒ False. Đồng thời thứ tự pop phải khớp nums.

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        graph = defaultdict(set)
        indeg = [0] * (n + 1)
        for seq in sequences:
            for i in range(len(seq) - 1):
                u, v = seq[i], seq[i + 1]
                if v not in graph[u]:
                    graph[u].add(v)
                    indeg[v] += 1

        queue = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        idx = 0
        while queue:
            if len(queue) > 1:
                return False              # >1 lựa chọn → không unique
            x = queue.popleft()
            if nums[idx] != x:
                return False              # khác thứ tự nums
            idx += 1
            for nb in graph[x]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)
        return idx == n

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

13.6 Parallel Courses (LC 1136)

Đề bài

Cho n khoá học và relations [a, b] (học a xong rồi học b). Mỗi semester bạn có thể học bất kỳ số khoá miễn đã hoàn thành prerequisite. Trả về số semester tối thiểu để học hết, hoặc -1 nếu có chu trình.

Ví dụ

Input:  n=3, relations=[[1,3],[2,3]]
Output: 2
Giải thích: Semester 1 học [1,2], semester 2 học [3]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Kahn’s BFS, nhưng đếm theo level (semester). Mỗi vòng outer of BFS xử lý toàn bộ queue hiện tại = các khoá có thể học cùng semester.

Code Python 3

from collections import defaultdict, deque
from typing import List

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = defaultdict(list)
        indeg = [0] * (n + 1)
        for u, v in relations:
            graph[u].append(v)
            indeg[v] += 1

        queue = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        taken = 0
        semesters = 0
        while queue:
            semesters += 1
            for _ in range(len(queue)):
                u = queue.popleft()
                taken += 1
                for v in graph[u]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        queue.append(v)
        return semesters if taken == n else -1

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Topo + DP framing (cầu nối sang Chương 43)

Sequence Reconstruction (LC 444) — vì sao queue phải luôn có ≤ 1 phần tử?

Alien Dictionary (LC 269) — invalid prefix case

Nếu w_i là prefix của w_{i-1} (vd ["abc", "ab"]), từ điển không hợp lệ → return "". Kiểm tra TRƯỚC khi build edges (đừng quên break đúng chỗ).

Sort Items by Groups (LC 1203) — DAG 2 lớp

items 5,6 ∈ groupA   items 7,8 ∈ groupB   items 9 ∈ -1 (riêng)

Item DAG:  5 → 6,  7 → 8,  6 → 7   (intra + cross-group)
Group DAG: A → B   (vì 6 → 7 mà 6 ∈ A, 7 ∈ B)

→ Topo group order → trong mỗi group topo item order.

Chương 14 — Interval

Interval (khoảng [start, end]) là pattern bao trùm nhiều bài calendar/scheduling/booking quan trọng. Hai chương 4 (Sorting) đã chạm qua Merge Intervals và Meeting Rooms II; chương này xoáy sâu vào 8 mẫu thao tác trên interval (merge, insert, intersection, overlap, free time) — đây là pattern không thể tránh khi phỏng vấn các công ty lịch (Google Calendar) và đặt phòng (Airbnb, Booking).

Mục tiêu chương

Sau chương này, bạn sẽ:

Khi nào dùng pattern này?

4 thao tác chuẩn trên 2 interval A = [a₁, a₂], B = [b₁, b₂]:

1. Tách rời (disjoint):   A.end < B.start  →  A trước B, không giao
2. Chạm điểm (touch):     A.end == B.start →  liền kề, có thể merge tuỳ đề
3. Giao một phần:         A.start < B.start ≤ A.end < B.end
4. Chứa nhau (contain):   A.start ≤ B.start ≤ B.end ≤ A.end

Template code

from typing import List

# 1) Merge 2 interval có giao nhau
def merge_two(a, b):
    return [min(a[0], b[0]), max(a[1], b[1])]


# 2) Check overlap (kể cả chỉ chạm điểm)
def overlaps(a, b) -> bool:
    return a[0] <= b[1] and b[0] <= a[1]


# 3) Sweep line: cùng pattern cho mọi bài "đếm overlap tối đa"
events: List[tuple[int, int]] = []
for s, e in intervals:
    events.append((s, +1))       # mở
    events.append((e, -1))       # đóng
events.sort()
cur = peak = 0
for _, delta in events:
    cur += delta
    peak = max(peak, cur)

Bài tự luyện cuối chương

14.1 Merge Intervals (LC 56) — recap

Đã giải đầy đủ ở Chương 4.2 dưới góc Sorting. Ở đây mình tóm tắt nhanh dưới lens “interval” và mở rộng follow-up.

Đề bài

Gộp các khoảng giao nhau. [1,3] và [2,6] → [1,6].

Hướng tiếp cận

Sort theo start. Duyệt 1 lượt, giữ last = interval cuối đã thêm vào kết quả. Nếu cur.start <= last.end → last.end = max(last.end, cur.end); ngược lại push cur mới.

Code Python 3

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        result = []
        for cur in intervals:
            if result and cur[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], cur[1])
            else:
                result.append(cur[:])
        return result

Phân tích độ phức tạp

Bình luận thêm cho góc interval

Bài tự luyện liên quan

14.2 Insert Interval (LC 57)

Đề bài

Cho mảng intervals đã sort theo start và không giao nhau. Chèn newInterval vào và merge nếu cần.

Ví dụ

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Ràng buộc

Clarifying questions

Hướng tiếp cận

Cách 1 — O(n) duyệt 1 lượt, 3 giai đoạn.

  1. Trước newInterval: đẩy hết các interval có end < newInterval.start.
  2. Giao nhau: với các interval có start <= newInterval.end, mở rộng newInterval (start = min, end = max). Cuối giai đoạn, push newInterval.
  3. Sau newInterval: đẩy phần còn lại.

Cách 2 — Concat + merge (gọi lại bài 14.1). Đơn giản nhưng O(n log n) cho sort thừa.

Hình minh hoạ với intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8]:

Trục số:
1   3   5   6  7  8  10        12      16
├─┤ ├───┤ ├─┤  ├──┤            ├──────┤
        ├──────────┤  new = [4, 8]

Giai đoạn 1 (end < 4):  [1, 2]
                         result = [[1,2]]

Giai đoạn 2 (start <= 8):
  [3, 5]: mở rộng newInterval = [min(4,3), max(8,5)] = [3, 8]
  [6, 7]: mở rộng = [3, 8]
  [8, 10]: mở rộng = [3, 10]
  Push [3, 10]
                         result = [[1,2], [3,10]]

Giai đoạn 3: còn [12, 16]
                         result = [[1,2], [3,10], [12,16]]  ✓

Code Python 3

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result: list[list[int]] = []
        i, n = 0, len(intervals)
        # 1) Trước newInterval.
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        # 2) Giao nhau — mở rộng newInterval.
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        # 3) Sau newInterval.
        while i < n:
            result.append(intervals[i])
            i += 1
        return result

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

14.3 Non-overlapping Intervals (LC 435)

Đề bài

Cho mảng intervals. Trả về số interval tối thiểu cần xoá để các interval còn lại không giao nhau.

Ví dụ

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Giải thích: xoá [1,3] → còn [1,2],[2,3],[3,4] không giao nhau.

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2

Input:  intervals = [[1,2],[2,3]]
Output: 0              (đã không giao, không cần xoá)

(mỗi phần tử [start, end] biểu diễn khoảng nửa-mở [start, end))

Ràng buộc

Clarifying questions

Hướng tiếp cận

Greedy — sort theo end tăng dần. Giữ interval có end nhỏ nhất → giữ được càng nhiều “không gian” về sau cho các interval tiếp theo.

Pseudocode: - Sort theo end. - Giữ last_end = -∞. Với mỗi interval [s, e]: - Nếu s >= last_end → giữ (không overlap), last_end = e. - Ngược lại → đếm xoá.

Tại sao sort theo end, không phải start? Greedy hoạt động vì: “luôn chọn interval có end sớm nhất” cho phép phần còn lại có nhiều “free time” hơn — chứng minh quy nạp.

Hình minh hoạ với [[1,2],[2,3],[3,4],[1,3]]:

Sort theo end:  [[1,2], [2,3], [1,3], [3,4]]
                       end=2   end=3   end=3   end=4

Duyệt:
  [1,2]: start=1 >= -inf → giữ; last_end=2          giữ: 1
  [2,3]: start=2 >= 2    → giữ; last_end=3          giữ: 2
  [1,3]: start=1 < 3     → xoá                       xoá: 1
  [3,4]: start=3 >= 3    → giữ; last_end=4          giữ: 3

Giữ 3, xoá 1 → đáp án = 1.

Code Python 3

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        kept = 1
        last_end = intervals[0][1]
        for s, e in intervals[1:]:
            if s >= last_end:
                kept += 1
                last_end = e
        return len(intervals) - kept

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

14.4 Meeting Rooms II (LC 253) — recap

Đã giải đầy đủ ở Chương 4.4. Ở đây chỉ tóm tắt và liên hệ.

Đề bài

Tìm số phòng tối thiểu để chứa tất cả meeting.

Hướng tiếp cận

3 cách (heap, sweep line events, chronological 2-pointer) — tất cả đều O(n log n). Sweep line là pattern interval ngôn ngữ chuẩn.

Code Python 3

from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = [(s, +1) for s, _ in intervals] + [(e, -1) for _, e in intervals]
        events.sort(key=lambda x: (x[0], x[1]))
        cur = peak = 0
        for _, d in events:
            cur += d
            peak = max(peak, cur)
        return peak

Phân tích độ phức tạp

Bình luận thêm

Bài tự luyện liên quan

14.5 Minimum Number of Arrows to Burst Balloons (LC 452)

Đề bài

Cho mảng các balloon [x_start, x_end] (mỗi balloon là 1 interval trên trục x). Một mũi tên bắn thẳng đứng tại x = X sẽ làm nổ tất cả balloon có x_start <= X <= x_end. Tìm số mũi tên tối thiểu để nổ hết.

Ví dụ

Input:  points = [[10,16],[2,8],[1,6],[7,12]]
        (mỗi phần tử [xstart, xend] biểu diễn 1 quả bóng nằm trong khoảng đóng [xstart, xend])
Output: 2   (cần ít nhất 2 mũi tên: bắn x=6 nổ [1,6] và [2,8]; bắn x=11 nổ [7,12] và [10,16])
Giải thích:
  1 mũi tại x = 6 nổ [1,6] và [2,8].
  1 mũi tại x = 11 nổ [7,12] và [10,16].

Ràng buộc

Clarifying questions

Hướng tiếp cận

Tương đương bài 14.3 (Non-overlapping Intervals): mỗi mũi tên ứng với 1 nhóm balloon có giao chung. Đếm nhóm = số mũi tên.

Greedy sort theo end y hệt 14.3: - Sort balloons theo end. - Giữ last_end = -∞. Với mỗi balloon [s, e]: - Nếu s > last_end → cần mũi mới; last_end = e. - Ngược lại → balloon này được nổ chung với mũi hiện tại.

Code Python 3

from typing import List

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key=lambda x: x[1])
        arrows = 1
        last_end = points[0][1]
        for s, e in points[1:]:
            if s > last_end:        # không giao → cần mũi mới
                arrows += 1
                last_end = e
        return arrows

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

14.6 Employee Free Time (LC 759)

Đề bài

Cho schedule[i] = danh sách interval đại diện thời gian bận của employee i. Trả về tất cả interval free chung cho tất cả employee, sắp xếp tăng dần. (Không tính khoảng trước người đầu tiên bận và sau người cuối kết thúc.)

Ví dụ

Input:  schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3, 4]]
Giải thích:
  Hợp các bận: [1,3] (gồm [1,2] + [1,3]), [4,10] (gồm [5,6] + [4,10]).
  Free chung giữa các khoảng bận: [3, 4].

Ràng buộc

Clarifying questions

Hướng tiếp cận

Bước 1: Gộp tất cả interval bận thành 1 list không phụ thuộc employee. Bước 2: Sort theo start, merge (như bài 14.1). Bước 3: Kẽ hở giữa các merged intervals = free time.

Code Python 3

from typing import List

class Interval:
    def __init__(self, start: int = 0, end: int = 0):
        self.start, self.end = start, end


class Solution:
    def employeeFreeTime(self, schedule: "List[List[Interval]]") -> "List[Interval]":
        all_busy: list[tuple[int, int]] = []
        for emp_sched in schedule:
            for iv in emp_sched:
                all_busy.append((iv.start, iv.end))
        all_busy.sort()

        merged: list[list[int]] = []
        for s, e in all_busy:
            if merged and s <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], e)
            else:
                merged.append([s, e])

        free = []
        for i in range(1, len(merged)):
            if merged[i - 1][1] < merged[i][0]:
                free.append(Interval(merged[i - 1][1], merged[i][0]))
        return free

Phân tích độ phức tạp

Bình luận

Bài tự luyện liên quan

Tóm tắt chương & Quyết định

Interval convention checklist

  1. Đóng [s, e] hay nửa mở [s, e)?
  2. Sort theo start (Merge, Insert) hay sort theo end (Greedy, Min Arrows)?
  3. Sweep line tie-break: với event tại cùng thời điểm t:

Employee Free Time — visual

e1: |==1==|       |==3==|
e2:    |==2==|       |==4==|
sort all → merge ⇒ busy: [1∪2] [3∪4]
free = complement giữa các busy block

Recap lens (vì sao Merge & Meeting xuất hiện lại)

Hết bản preview miễn phí

Bạn vừa đọc xong 14 chương đầu công khai trên web. Bản đầy đủ gồm 44 chương + phụ lục (288 bài kèm lời giải Python 3) có tại Gumroad:

🛒 Mua sách đầy đủ trên Gumroad