Search a 2D Matrix: làm phẳng chỉ số ma trận thành một binary search

Bài trước trong series đã thiết lập template binary search: left, right, mid, thu hẹp window một đơn vị ở mỗi phía. LeetCode 74 đặt cùng template đó vào ngữ cảnh 2D và yêu cầu bạn nhận ra rằng cấu trúc 2D chỉ là vỏ bề ngoài. Bóc lớp đó ra, bạn có đúng một binary search, không phải hai.

Những gì constraints buộc bạn phải làm

Bài toán đảm bảo hai điều. Thứ nhất, mỗi hàng được sắp xếp theo thứ tự không giảm. Thứ hai — và đây là phần quyết định — phần tử đầu tiên của mỗi hàng lớn hơn phần tử cuối cùng của hàng trước đó.

Hai tính chất này cộng lại có nghĩa là không có khoảng trống nào khi vượt ranh giới giữa các hàng: phần tử cuối của hàng i luôn nhỏ hơn phần tử đầu của hàng i+1. Đọc ma trận từ trái sang phải, từ trên xuống dưới:

[[ 1,  3,  5,  7],
 [10, 11, 16, 20],
 [23, 30, 34, 60]]

Trải phẳng: 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60. Hoàn toàn được sắp xếp. Không có phần tử nào lệch thứ tự, dù bạn vượt qua ranh giới hàng ở đâu. Bố cục 2D chỉ là bề ngoài.

Yêu cầu complexity là O(log(m _ n)). Constraints cho biết m và n tối đa là 100, nên m _ n không quá 10,000. Với input nhỏ như vậy, ngay cả brute force cũng qua được. Nhưng bài yêu cầu rõ ràng O(log(m _ n)) — loại bỏ brute force như một đáp án cuối và trỏ thẳng vào binary search trên tất cả m _ n phần tử.

Pattern ở đây là "virtual 1D array": một cấu trúc 2D có thể được xử lý như 1D vì thứ tự được bảo toàn hoàn hảo qua các ranh giới chiều. Binary search trên flattened index, sau đó unmap. Đó là toàn bộ mental model.

Brute force: O(m * n)

Duyệt qua từng ô. Đây là điểm khởi đầu hiển nhiên, và cũng là cách bỏ qua hoàn toàn tính chất thú vị của ma trận.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        for row in matrix:
            for num in row:
                if num == target:
                    return True
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        foreach (int[] row in matrix)
            foreach (int num in row)
                if (num == target) return true;
        return false;
    }
}

O(m _ n) time, O(1) space. Không đáp ứng yêu cầu. Đáng để viết một lần để thấy rõ những gì đang bị lãng phí — từng ô được duyệt theo thứ tự, không có early termination nào dựa trên cấu trúc đã sắp xếp. Bạn có thể cải thiện một chút bằng cách break khỏi vòng lặp trong ngay khi num > target, vì mỗi hàng đã sắp xếp. Nhưng worst case vẫn là O(m _ n). Không đủ.

Two-step binary search: O(log m + log n)

Một bước trung gian tự nhiên hơn: binary search để tìm hàng ứng viên trước, sau đó binary search trong hàng đó. Bạn chọn hàng bằng cách kiểm tra xem target có nằm trong khoảng [row[0], row[-1]] không. Nếu target < row[0], hàng đang xét nằm quá thấp. Nếu target > row[-1], hàng đang xét nằm quá cao.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        top, bottom = 0, m - 1
 
        while top <= bottom:
            mid_row = (top + bottom) // 2
            if target < matrix[mid_row][0]:
                bottom = mid_row - 1
            elif target > matrix[mid_row][n - 1]:
                top = mid_row + 1
            else:
                # target nằm trong khoảng của hàng này, tìm trong hàng
                left, right = 0, n - 1
                while left <= right:
                    mid_col = (left + right) // 2
                    if matrix[mid_row][mid_col] == target:
                        return True
                    elif matrix[mid_row][mid_col] < target:
                        left = mid_col + 1
                    else:
                        right = mid_col - 1
                return False
 
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int top = 0, bottom = m - 1;
 
        while (top <= bottom) {
            int midRow = top + (bottom - top) / 2;
            if (target < matrix[midRow][0])
                bottom = midRow - 1;
            else if (target > matrix[midRow][n - 1])
                top = midRow + 1;
            else {
                int left = 0, right = n - 1;
                while (left <= right) {
                    int midCol = left + (right - left) / 2;
                    if (matrix[midRow][midCol] == target) return true;
                    else if (matrix[midRow][midCol] < target) left = midCol + 1;
                    else right = midCol - 1;
                }
                return false;
            }
        }
        return false;
    }
}

O(log m + log n) time, O(1) space. Về mặt toán học bằng O(log(m _ n)) — log m + log n = log(m _ n) theo quy tắc tích logarithm. Về complexity thì ổn. Nhưng bạn đang viết hai binary search riêng biệt với một nhánh điều kiện kết nối. Chạy được, chỉ là làm nhiều hơn mức cần thiết.

Binary search đầu tìm hàng. Binary search thứ hai tìm cột. Hai bài toán riêng, trong khi thực ra chỉ có một.

Nước đi tối ưu: làm phẳng thành mảng 1D ảo

Giải pháp gọn nhất bỏ qua hoàn toàn bước tìm hàng. Vì toàn bộ ma trận đọc như một sequence 1D đã sắp xếp, hãy xử lý nó như vậy. Đặt left = 0, right = m * n - 1, và chạy một binary search tiêu chuẩn. Công việc bổ sung duy nhất: chuyển đổi mid ngược lại thành tọa độ 2D để đọc giá trị thực.

Công thức mapping chỉ hai dòng:

row = mid // n
col = mid % n

mid // n là phép chia nguyên cho số cột — đó là số hàng đầy đủ nằm trước index mid. mid % n là phần dư — vị trí trong hàng đó. Chiều ngược lại: index = row * n + col. Một hệ tọa độ, hai cách biểu diễn.

Luồng quyết định trông như thế này:

Trace qua target = 3 trên ma trận 3x4, từng bước:

Virtual array: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Indices:         0  1  2  3   4   5   6   7   8   9  10  11

Bước 1: left=0, right=11  -> mid=5  -> row=5//4=1, col=5%4=1 -> matrix[1][1]=11
         11 > 3  -> right = 4

Bước 2: left=0, right=4   -> mid=2  -> row=2//4=0, col=2%4=2 -> matrix[0][2]=5
         5 > 3   -> right = 1

Bước 3: left=0, right=1   -> mid=0  -> row=0//4=0, col=0%4=0 -> matrix[0][0]=1
         1 < 3   -> left = 1

Bước 4: left=1, right=1   -> mid=1  -> row=1//4=0, col=1%4=1 -> matrix[0][1]=3
         3 == 3  -> return True

Bốn lần lặp. Không có bước tìm hàng. Không có vòng lặp lồng nhau. Index arithmetic xử lý hết.

Bây giờ trace target = 13 (trường hợp không tìm thấy):

Bước 1: left=0,  right=11 -> mid=5  -> matrix[1][1]=11  -> 11<13 -> left=6
Bước 2: left=6,  right=11 -> mid=8  -> matrix[2][0]=23  -> 23>13 -> right=7
Bước 3: left=6,  right=7  -> mid=6  -> matrix[1][2]=16  -> 16>13 -> right=5
Bước 4: left=6,  right=5  -> left > right -> thoát vòng lặp

left > right — vòng lặp thoát sạch, return False.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
 
        while left <= right:
            mid = (left + right) // 2
            row, col = mid // n, mid % n
            val = matrix[row][col]
 
            if val == target:
                return True
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
 
        return False

public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int left = 0, right = m * n - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int row = mid / n;
            int col = mid % n;
            int val = matrix[row][col];
 
            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
 
        return false;
    }
}

O(log(m * n)) time, O(1) space. Một lần duyệt, không có branching để quyết định vào hàng nào. Đây là version tôi sẽ ship.

So sánh các approach

Công thức cần ghi nhớ đúng

Việc chuyển đổi index hay gây nhầm lẫn đúng một lần. Quy tắc: row = mid // n, col = mid % n — chia cho số cột, không phải số hàng. Rất dễ bị đảo ngược.

Nghĩ theo cách cụ thể. Nếu bạn có 4 cột và đang ở virtual index 9: row = 9 // 4 = 2 (hàng thứ ba, zero-indexed), col = 9 % 4 = 1. Kiểm tra: trong ma trận ví dụ, matrix[2][1] = 30, và virtual index 9 thực sự chứa 30. Công thức hoạt động vì mỗi hàng chứa đúng n phần tử — cứ sau n phần tử, bạn tiến xuống một hàng.

Phiên bản C# dùng left + (right - left) / 2 thay vì (left + right) / 2 để tránh integer overflow khi left và right lớn. Với constraints của LeetCode (m, n <= 100, nên right tối đa là 9999) điều này không quan trọng trên thực tế. Nhưng đây là thói quen đúng cần giữ cho những bài có index lớn hơn.

Các edge case cần biết

Ma trận 1x1 — [[5]], target = 5 hoặc target = 3. left = right = 0, một lần lặp. Code xử lý cả hai mà không cần case đặc biệt: target tìm thấy thì return True ngay; target không tìm thấy thì thoát sau một lần shrink khi left > right.

Target nhỏ hơn minimum của ma trận — target nhỏ hơn matrix[0][0]. Lần so sánh mid đầu tiên cho giá trị lớn hơn target, nên right co lại. Sau vài bước left > right và vòng lặp thoát sạch. Không cần xử lý đặc biệt vì invariant của binary search tự nhiên loại trừ toàn bộ khoảng.

Target lớn hơn maximum của ma trận — target lớn hơn matrix[m-1][n-1]. Đối xứng — left tăng vượt qua right. Thoát sạch tương tự.

Ma trận một hàng — ma trận 1x4 có n = 4, nên mid // 4 = 0 với mọi mid trong [0, 3]. Bạn luôn ở hàng 0. Công thức hoạt động mà không cần điều chỉnh.

Ma trận một cột — ma trận 4x1 có n = 1, nên mid // 1 = mid và mid % 1 = 0. Bạn luôn ở cột 0. Tương tự.

Guard cho ma trận rỗng — constraints đảm bảo 1 <= m, n <= 100 nên ma trận rỗng không thể xuất hiện. Check if not matrix or not matrix[0] trong Python (hoặc null/length check trong C#) là defensive code. Đáng giữ lại; chi phí bằng không.

Approach này không hoạt động khi nào

LeetCode 240 — Search a 2D Matrix II — có setup bề ngoài gần giống nhưng bỏ đi đảm bảo rằng phần tử đầu hàng sau vượt qua phần tử cuối hàng trước. Không có tính chất đó, ma trận không đọc như một sequence 1D đã sắp xếp khi trải phẳng. Bạn không thể flatten và binary search. Cần một approach hoàn toàn khác — staircase search bắt đầu từ góc trên phải hoặc dưới trái, chạy trong O(m + n).

Đảm bảo trong LeetCode 74 là thứ làm cho việc làm phẳng hợp lệ. Khi gặp bài sorted-matrix, hãy kiểm tra rõ ràng: nếu "phần tử đầu của hàng i+1 > phần tử cuối của hàng i" được nêu ra, flatten và chạy một binary search. Nếu không, bạn đang ở lãnh thổ LeetCode 240 và thuật toán thay đổi hoàn toàn.

Vị trí bài này trong series

Template binary search cốt lõi đã xuất hiện ở bài trước. Bài này dùng đúng template đó — điểm thêm duy nhất là hai dòng coordinate mapping. Đây là chỗ tốt để thấy rằng binary search không bị ràng buộc với mảng 1D; nó gắn với thứ tự đã sắp xếp và khả năng chia đôi không gian tìm kiếm ở mỗi bước. Vỏ bọc 2D ở đây chỉ là chi tiết phụ.

Các bài tiếp theo trong series (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array) khó hơn vì thứ tự đã sắp xếp bị phá vỡ. Bạn không còn có thể so sánh mid với target và biết nửa nào "sạch". Invariant bạn duy trì trở nên tinh tế hơn nhiều.

Related problems

• LeetCode 240 — Search a 2D Matrix II: Cùng cấu trúc bề mặt, đảm bảo khác nhau. Hàng và cột được sắp xếp riêng lẻ, nhưng không có cross-row ordering. Trick flatten không dùng được; dùng staircase search thay.
• LeetCode 33 — Search in Rotated Sorted Array: Binary search trên mảng đã sắp xếp bị cắt và xoay. Invariant duy trì khác nhau — ở mỗi bước bạn xác định nửa nào vẫn còn được sắp xếp liên tục.
• LeetCode 153 — Find Minimum in Rotated Sorted Array: Liên quan chặt chẽ với bài 33. Binary search không tìm giá trị cụ thể mà tìm rotation pivot.
• LeetCode 378 — Kth Smallest Element in a Sorted Matrix: Binary search trên giá trị thay vì index, trong ma trận sắp xếp theo hàng và cột độc lập. Hình dạng khác nhưng cùng tư duy "nghĩ sáng tạo về thứ bạn đang tìm kiếm."