Chương 37 - Binary Search kết hợp Graph Traversal

Khi bài có dạng “min của max” hoặc “max của min” trên graph/grid, ta có thể binary search trên đáp án + kiểm tra tính khả thi bằng BFS/DFS. Pattern này xuất hiện khi ta muốn lời giải O((V + E) · log range) đơn giản, thay cho Dijkstra hoặc MST tinh vi hơn.

Mục tiêu chương

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

• Pattern: binary search trên đáp án + BFS/DFS check reachability.
• can_reach(x): với threshold x, có path không?
• So sánh với Dijkstra/DSU offline: BS + BFS chậm hơn nhưng dễ code.
• Bài đặc biệt: Trapping Rain Water II - priority queue, không phải BS thuần.

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

• “Min effort / max difficulty path” - đáp án là threshold.
• Predicate “với threshold T, có thể đi từ A đến B không?” → BFS/DFS.

Template code

def search_on_answer_graph(lo, hi, can_reach):
    while lo < hi:
        mid = (lo + hi) // 2
        if can_reach(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

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

• LC 1102 - Path With Maximum Minimum Value
• LC 1631 - Path With Minimum Effort

---

37.1 Swim in Rising Water (LC 778) - recap

Đã giải 2 cách (DSU offline, Dijkstra) ở Chương 24.6 và 30.4. Đây là cách thứ 3: binary search trên t + BFS check.

Đề bài

Grid n × n elevation. Tại thời điểm t, ô có elevation ≤ t có nước phủ. Tìm t nhỏ nhất bơi được từ (0,0) đến (n-1,n-1).

Hướng tiếp cận

Binary search trên t. Với mỗi t, BFS check có path qua các ô elevation ≤ t không. Predicate đơn điệu: t lớn hơn → tới được nhiều ô hơn → dễ path hơn.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]

        def can_reach(t: int) -> bool:
            if grid[0][0] > t: return False
            visited = {(0, 0)}
            queue = deque([(0, 0)])
            while queue:
                r, c = queue.popleft()
                if (r, c) == (n - 1, n - 1): return True
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] <= t and (nr, nc) not in visited:
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return False

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

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

• Thời gian: O(n² · log(n²)).
• Bộ nhớ: O(n²).

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

• LC 1631 - Path With Minimum Effort (bài 37.2)
• LC 1102 - Path With Maximum Minimum Value (bài 33.6)

---

37.2 Path With Minimum Effort (LC 1631) - recap

Đã giải bằng Dijkstra ở Chương 30.2. BS version: binary search trên effort, BFS check.

Code Python 3

from collections import deque
from typing import List

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]

        def can_reach(e: int) -> bool:
            visited = {(0, 0)}
            queue = deque([(0, 0)])
            while queue:
                r, c = queue.popleft()
                if (r, c) == (rows - 1, cols - 1): return True
                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:
                        if abs(heights[nr][nc] - heights[r][c]) <= e:
                            visited.add((nr, nc))
                            queue.append((nr, nc))
            return False

        lo, hi = 0, 10**6
        while lo < hi:
            mid = (lo + hi) // 2
            if can_reach(mid): hi = mid
            else: lo = mid + 1
        return lo

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

• Thời gian: O(R · C · log(max_height)).
• Bộ nhớ: O(R · C).

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

• LC 778 - Swim in Rising Water (bài 37.1)
• LC 1102 - Path With Maximum Minimum Value

---

37.3 Last Day Where You Can Still Cross (LC 1970)

Đề bài

Lưới row × col. Mỗi ngày 1 ô nước (cells[i]). Tìm ngày cuối cùng còn đường từ row 0 đến row n-1 (qua các ô đất).

Ví dụ

Input:  row=2, col=2, cells=[[1,1],[2,1],[1,2],[2,2]]
Output: 2

Ràng buộc

• 2 <= row, col <= 2·10^4
• 1 <= len(cells) <= row·col

Clarifying questions

• Mọi ô đều bị block? → Trả 0 (theo đề luôn có path lúc t=0).
• row hoặc col = 1? → Edge case.

Hướng tiếp cận

Binary search trên day d + BFS/DFS check: với d ngày, lưới có đường đi không?

Code Python 3

from collections import deque
from typing import List

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:

        def can_cross(d: int) -> bool:
            grid = [[0] * col for _ in range(row)]
            for i in range(d):
                r, c = cells[i]
                grid[r - 1][c - 1] = 1   # nước
            queue = deque()
            visited = set()
            for c in range(col):
                if grid[0][c] == 0:
                    queue.append((0, c))
                    visited.add((0, c))
            DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
            while queue:
                r, c = queue.popleft()
                if r == row - 1: return True
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == 0 and (nr, nc) not in visited:
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return False

        lo, hi = 0, len(cells)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_cross(mid): lo = mid
            else: hi = mid - 1
        return lo

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

• Thời gian: O(R · C · log K) với K = số ngày.
• Bộ nhớ: O(R · C).

Bình luận

• “last True” pattern (Chương 5/25): ceil mid.

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

• LC 1970 - Last Day to Cross (bài này)
• LC 1631 - Path With Minimum Effort

---

37.4 Trapping Rain Water II (LC 407)

Đề bài

Trapping Rain Water mở rộng lên 2D. Tính tổng nước đọng trên grid heights.

Ví dụ

Input:  heightMap = [[1,4,3,1,3,2],
                     [3,2,1,3,2,4],
                     [2,3,3,2,3,1]]   (grid m × n, mỗi ô là chiều cao cột)
Output: 4   (tổng lượng nước đọng sau mưa)

Ràng buộc

• m == heights.length
• n == heights[i].length
• 1 <= m, n <= 200

Clarifying questions

• Grid không có ô nội (m ≤ 2 hoặc n ≤ 2)? → Trả 0.

Hướng tiếp cận

Dijkstra/BFS từ biên với min-heap: thay vì binary search, dùng heap pop ô thấp nhất từ biên. Mỗi lần pop, “nâng” mực nước cho hàng xóm.

Code Python 3

import heapq
from typing import List

class Solution:
    def trapRainWater(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        visited = [[False] * cols for _ in range(rows)]
        heap = []
        for r in range(rows):
            for c in range(cols):
                if r == 0 or r == rows - 1 or c == 0 or c == cols - 1:
                    heapq.heappush(heap, (heights[r][c], r, c))
                    visited[r][c] = True
        water = 0
        DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
        while heap:
            h, r, c = heapq.heappop(heap)
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                    visited[nr][nc] = True
                    water += max(0, h - heights[nr][nc])
                    heapq.heappush(heap, (max(h, heights[nr][nc]), nr, nc))
        return water

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

• Thời gian: O(R · C · log(R · C)).
• Bộ nhớ: O(R · C).

Bình luận

• Dijkstra-style trên grid với “trọng số” = mực nước.

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

• LC 42 - Trapping Rain Water (Chương 26.2)
• LC 778 - Swim in Rising Water

---

37.5 Minimize the Maximum of Two Arrays (LC 2513)

Đề bài

Input: 4 số nguyên divisor1, divisor2, uniqueCnt1, uniqueCnt2.

Cần tạo 2 mảng arr1 (độ dài uniqueCnt1) và arr2 (độ dài uniqueCnt2) chứa các số nguyên dương sao cho: - Mọi phần tử trong arr1 không chia hết cho divisor1. - Mọi phần tử trong arr2 không chia hết cho divisor2. - arr1 ∪ arr2 toàn bộ là các giá trị phân biệt (không trùng nhau giữa hai mảng).

Trả về giá trị lớn nhất trong arr1 ∪ arr2 mà nhỏ nhất có thể.

Ví dụ

Input:  divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
Output: 4

Giải thích:
  arr1 = [1]         (1 không chia hết cho 2)
  arr2 = [2, 3, 4]   (đều không chia hết cho 7)
  max(arr1 ∪ arr2) = 4, đã tối thiểu.

Ràng buộc

• 2 <= divisor1, divisor2 <= 10^5
• 1 <= uniqueCnt1, uniqueCnt2 < 10^9

Clarifying questions

• divisor1 == divisor2? → Có thể xảy ra; algorithm vẫn đúng.
• uniqueCnt rất lớn? → Output có thể > 10^9 nên dùng Python int (không tràn).

Hướng tiếp cận

Binary search trên đáp án X: - Số trong [1, X] không chia hết d1: X - X // d1. - Tương tự với d2. - Chỉ chia hết lcm(d1, d2): là phần share - quyết định ai nhận.

Inclusion-exclusion + binary search.

Code Python 3

from math import lcm

class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
        L = lcm(divisor1, divisor2)

        def enough(x: int) -> bool:
            # Số ≤ x chia cho d1: x // d1; chia cho d2: x // d2; chia cho L: x // L
            available1 = x - x // divisor1
            available2 = x - x // divisor2
            available_both = x - x // L
            # arr1 cần available1 cho mình, có thể share với arr2.
            need1 = max(0, uniqueCnt1 - (available1 - (x // divisor2 - x // L)))
            # ... brain teaser, easier with formula.
            shared = available_both
            return available1 >= uniqueCnt1 and available2 >= uniqueCnt2 and \
                   shared >= max(0, uniqueCnt1 - (x - x // divisor1 - (x // divisor2 - x // L))) + \
                              max(0, uniqueCnt2 - (x - x // divisor2 - (x // divisor1 - x // L)))

        lo, hi = 1, 10**11
        while lo < hi:
            mid = (lo + hi) // 2
            if enough(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

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

• Thời gian: O(log(10^11)).
• Bộ nhớ: O(1).

Bình luận

• Bài Hard - combinatorics + binary search trên answer.

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

• LC 668 - Kth Smallest in Multiplication Table
• LC 1011 - Capacity To Ship Packages

---

37.6 Find a Peak Element II (LC 1901)

Đề bài

Ma trận. Peak = ô lớn hơn 4 hàng xóm. Trả về [r, c] của 1 peak. O(m log n).

Ví dụ

Input:  mat = [[1, 4],
               [3, 2]]   (mọi ô khác nhau; biên grid xem như -∞)
Output: [0, 1]   (1 vị trí peak: lớn hơn 4 hàng xóm; có nhiều, trả bất kỳ)

Ràng buộc

• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 10^5

Clarifying questions

• Có nhiều peak? → Trả 1 cái bất kỳ.
• Matrix 1×1? → Đó là peak duy nhất.

Hướng tiếp cận

Binary search trên cột. Chọn cột giữa, tìm max trong cột → coi như có “đỉnh trong row đó”. Compare với 2 cột kề: nếu max < cột bên trái → đỉnh ở nửa trái; tương tự phải.

Code Python 3

from typing import List

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        rows, cols = len(mat), len(mat[0])
        lo, hi = 0, cols - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            max_row = max(range(rows), key=lambda r: mat[r][mid])
            left = mat[max_row][mid - 1] if mid > 0 else -1
            right = mat[max_row][mid + 1] if mid < cols - 1 else -1
            if mat[max_row][mid] > left and mat[max_row][mid] > right:
                return [max_row, mid]
            if left > mat[max_row][mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        return [-1, -1]

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

• Thời gian: O(rows · log cols).
• Bộ nhớ: O(1).

Bình luận

• Tinh tế: chọn cột giữa rồi tìm max row trong cột. Max-of-col luôn là peak so với chính cột → chỉ cần so với left/right.

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

• LC 162 - Find Peak Element (1D)
• LC 240 - Search a 2D Matrix II

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

Template BS + Graph

def solve():
    lo, hi = min_possible, max_possible
    while lo < hi:
        mid = (lo + hi) // 2
        if can_reach(mid):     # reachability dưới ngưỡng / capacity mid
            hi = mid
        else:
            lo = mid + 1
    return lo

• can_reach(x) là BFS/DFS với constraint phụ thuộc x.
• Monotonic: nếu x lớn (rộng rãi hơn) thì can_reach chỉ có thể chuyển False → True.

Predicate table (chương này)

Bài	Answer	can(x)	Monotonic
Path with Min Effort (LC 1631)	max edge diff	BFS chỉ qua cạnh ≤ x	True khi x ↗
Swim in Rising Water (LC 778)	min ngưỡng	BFS qua cell height ≤ x	True khi x ↗
Min Bridges (LC 1102)	max path min	DFS qua cell ≥ x	True khi x ↘
Aggressive Cows / Magnetic Force	distance	Greedy đặt	True khi x ↘

So với Dijkstra / DSU

• Dijkstra thường nhanh hơn 1 hệ số log nếu áp dụng được (vd Swim in Rising Water = Dijkstra max-min).
• BS + BFS dễ giải thích hơn, code ngắn hơn nếu chấp nhận O((V+E) log range).
• DSU offline: chỉ dùng được khi có thể sort queries.

Trapping Rain Water II (LC 407) - vì sao đặt ở đây?

Bản chất bài này là Dijkstra-like với priority queue (chọn cell biên thấp nhất tiếp theo). Đặt trong chương 37 để so sánh “BS

• Graph” với “Min-heap traversal” - cả hai đều thuộc gia đình “answer = ngưỡng”.

---