LeetCode #73 Set Matrix Zeroes: ใช้แถวแรกเป็นสมุดจด

Set Matrix Zeroes ให้แก้ matrix ในที่เดิม: ถ้า cell ใดเป็นศูนย์ ต้องเปลี่ยนทั้งแถวและคอลัมน์ของมันเป็นศูนย์ครับ กับดักคือห้ามเขียนศูนย์ทันทีที่พบ เพราะศูนย์ที่เราเพิ่งสร้างจะลามต่อเหมือนทำหมึกหกแล้วเข้าใจผิดว่าเป็นตราประทับเดิม

วิธี 1: ทำสำเนา matrix

เก็บต้นฉบับ O(mn) แล้วเดินสำเนาเพื่อสั่งศูนย์ใน matrix จริง วิธีนี้เข้าใจง่ายและดีเป็น oracle ใน test แต่ใช้หน่วยความจำเท่าข้อมูลทั้งก้อน เวลาใน implementation ตรงไปตรงมาอาจสูงถึง O(mn(m+n)) ถ้าเขียนทั้งแถว/คอลัมน์ซ้ำ

วิธี 2: เก็บ set ของแถวและคอลัมน์

รอบแรกบันทึก index ของทุกแถว/คอลัมน์ที่มีศูนย์ รอบสองเขียน cell เป็นศูนย์เมื่อ index อยู่ใน set เวลา O(mn) พื้นที่ O(m+n) อ่านง่ายและเป็นทางเลือกที่ดีในงานจริงเมื่อ memory ไม่ตึง

วิธี 3: ใช้แถวแรกกับคอลัมน์แรกเป็น marker

ใช้ cell แถวแรกและคอลัมน์แรกเป็นสมุดจดว่าต้องล้างแถว/คอลัมน์ใด แต่ matrix[0][0] อยู่ร่วมกัน จึงต้องมี boolean แยกสองตัวสำหรับ “แถวแรกมีศูนย์ไหม” และ “คอลัมน์แรกมีศูนย์ไหม” จากนั้น mark เฉพาะด้านใน, ล้างด้านในตาม marker แล้วค่อยล้างขอบเป็นขั้นสุดท้าย เวลา O(mn) พื้นที่ช่วย O(1)

from __future__ import annotations

import unittest


def set_zeroes_sets(matrix: list[list[int]]) -> None:
    rows: set[int] = set()
    cols: set[int] = set()
    for row, values in enumerate(matrix):
        for col, value in enumerate(values):
            if value == 0:
                rows.add(row)
                cols.add(col)
    for row, values in enumerate(matrix):
        for col in range(len(values)):
            if row in rows or col in cols:
                matrix[row][col] = 0


def set_zeroes_constant(matrix: list[list[int]]) -> None:
    first_row = any(value == 0 for value in matrix[0])
    first_col = any(row[0] == 0 for row in matrix)
    for row in range(1, len(matrix)):
        for col in range(1, len(matrix[0])):
            if matrix[row][col] == 0:
                matrix[row][0] = 0
                matrix[0][col] = 0
    for row in range(1, len(matrix)):
        for col in range(1, len(matrix[0])):
            if matrix[row][0] == 0 or matrix[0][col] == 0:
                matrix[row][col] = 0
    if first_row:
        matrix[0] = [0] * len(matrix[0])
    if first_col:
        for row in matrix:
            row[0] = 0


class SetMatrixZeroesTests(unittest.TestCase):
    def test_methods_and_boundaries(self):
        cases = [
            ([[1, 1, 1], [1, 0, 1], [1, 1, 1]], [[1, 0, 1], [0, 0, 0], [1, 0, 1]]),
            ([[0, 1], [1, 1]], [[0, 0], [0, 1]]),
            ([[1]], [[1]]),
        ]
        for source, expected in cases:
            for solve in (set_zeroes_sets, set_zeroes_constant):
                matrix = [row[:] for row in source]
                solve(matrix)
                self.assertEqual(matrix, expected)


if __name__ == "__main__":
    unittest.main()

import java.util.Arrays;

public class Main {
    static void setZeroes(int[][] matrix) {
        boolean firstRow = false;
        boolean firstCol = false;
        for (int value : matrix[0]) if (value == 0) firstRow = true;
        for (int[] row : matrix) if (row[0] == 0) firstCol = true;
        for (int r = 1; r < matrix.length; r++) {
            for (int c = 1; c < matrix[0].length; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }
        for (int r = 1; r < matrix.length; r++) {
            for (int c = 1; c < matrix[0].length; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
            }
        }
        if (firstRow) Arrays.fill(matrix[0], 0);
        if (firstCol) for (int[] row : matrix) row[0] = 0;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        setZeroes(matrix);
        assert Arrays.deepEquals(matrix, new int[][] {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}});
        int[][] edge = {{0, 1}, {1, 1}};
        setZeroes(edge);
        assert Arrays.deepEquals(edge, new int[][] {{0, 0}, {0, 1}});
        System.out.println("2 assertions passed");
    }
}

Edge cases ที่ต้องลอง

• ศูนย์อยู่ที่ matrix[0][0] ซึ่งเป็น marker ร่วม
• ศูนย์อยู่เฉพาะแถวแรกหรือเฉพาะคอลัมน์แรก
• matrix ขนาด 1×1, หนึ่งแถว หรือหนึ่งคอลัมน์
• มีศูนย์หลายจุดตัดกัน
• โจทย์รับประกัน matrix ไม่ว่าง; งานจริงควร guard input ว่างก่อนอ่าน matrix[0]

Decision table

เงื่อนไข	สำเนาทั้งก้อน	Row/column sets	First-row markers
input ใหญ่	หน่วยความจำสูง	ดี	ดีที่สุด
extra memory	O(mn)	O(m+n)	O(1)
readability	ง่าย	ง่ายที่สุด	ต้องรักษาลำดับ
sorted input	ไม่เกี่ยว	ไม่เกี่ยว	ไม่เกี่ยว
streaming	ไม่เหมาะ เพราะต้องย้อนแก้	เก็บ marker ได้แต่ยังต้องเขียนย้อนหลัง	ไม่เหมาะ
mutation input	มี	มี	มีตามโจทย์

สำหรับสัมภาษณ์ที่บังคับ constant space ผมเลือก first-row markers เป็น default แต่ใน production ที่ memory ไม่ใช่คอขวด set มักอ่านง่ายกว่าและลด bug จากการล้างขอบผิดลำดับ

Recap

• อย่าเขียนศูนย์ทันทีในรอบค้นหา
• แยกสถานะแถวแรกและคอลัมน์แรก
• mark ด้านในก่อน ล้างด้านใน แล้วค่อยล้างขอบ
• เทสต์ 1×1 และศูนย์ที่มุมซ้ายบน