Chương trình tìm chỉ số cột trái nhất có giá trị 1 trong ma trận nhị phân Python

Cho ma trận nhị phân 2D, mỗi hàng được sắp xếp tăng dần (các 0 đứng trước 1). Tìm chỉ số cột trái nhất chứa giá trị 1. Trả về -1 nếu không có 1 nào.

Ví dụ

Ma trận:

[[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 0]]

Cột 2 (0-indexed) là cột trái nhất có 1 → kết quả: 2.

Thuật toán (Tối ưu O(m+n) - Bắt đầu từ góc trên bên phải)

1. Khởi tạo i = 0 (hàng đầu), j = cols - 1 (cột cuối).
2. leftmost = -1.
3. Khi i < rows và j >= 0:
   • Nếu matrix[i][j] == 0: chuyển xuống hàng sau (i++).
   • Ngược lại (gặp 1): cập nhật leftmost = j, chuyển sang cột trước (j--).
4. Trả về leftmost.

Triển khai Python

class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return -1
        
        rows = len(matrix)
        cols = len(matrix[0])
        i, j = 0, cols - 1
        leftmost = -1
        
        while i < rows and j >= 0:
            if matrix[i][j] == 0:
                i += 1
            else:
                leftmost = j
                j -= 1
        return leftmost

# Test
ob = Solution()
matrix = [
    [0, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 0]
]
print(ob.solve(matrix))  # Output: 2

Độ phức tạp

• Thời gian: O(m + n) - mỗi bước hoặc tăng hàng hoặc giảm cột.
• Không gian: O(1).

Tốt hơn so với binary search từng hàng O(m log n).