Search a 2D Matrix

Bài toán

Cho một ma trận m x n số nguyên có tính chất:

1. Mỗi hàng được sắp xếp tăng dần từ trái sang phải.
2. Số đầu tiên của mỗi hàng luôn lớn hơn số cuối cùng của hàng trước đó.

Viết hàm tìm target có trong ma trận hay không. Độ phức tạp yêu cầu $O(\log(m \cdot n))$.

Ví dụ:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Phân Tích & Tiếp Cận

Cách 1: Double Binary Search

1. BS để tìm Hàng tiềm năng (vì số đầu mỗi hàng cũng tăng dần).
2. BS trong Hàng đó để tìm số.

Cách 2: Virtual Flattening (Mảng phẳng ảo) - Hay nhất

Với tính chất đề bài, nếu ta nối các hàng lại với nhau, ta sẽ được một mảng 1 chiều sắp xếp tăng dần hoàn hảo. Mảng ảo này có kích thước Total = m * n. Index ảo chạy từ 0 đến Total - 1.

Vấn đề: Làm sao ánh xạ từ Virtual Index sang tọa độ (row, col) thực tế?

• row = Math.floor(mid / COLS)
• col = mid % COLS

function searchMatrix(matrix: number[][], target: number): boolean {
    const ROWS = matrix.length;
    const COLS = matrix[0].length;
    
    let left = 0;
    let right = ROWS * COLS - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        // Quy đổi index ảo mid thành tọa độ thật
        const r = Math.floor(mid / COLS);
        const c = mid % COLS;
        
        const midVal = matrix[r][c];

        if (midVal === target) {
            return true;
        } else if (midVal < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

• Time Complexity: $O(\log(m \cdot n))$. Chúng ta thực hiện đúng 1 lần Binary Search trên không gian $m \cdot n$.
• Space Complexity: $O(1)$. Ta không tạo mảng mới, chỉ tính toán chỉ số.

Pattern Nhận Diện

Khi gặp Matrix mà có tính chất sắp xếp liên tục nối đuôi nhau, hãy nghĩ đến việc phẳng hóa ảo (Virtual Flattening) để đưa về bài toán Binary Search cơ bản.