LeetCode 54 Spiral Matrix: เดินขอบให้ครบโดยไม่หลงมุม

โจทย์ Spiral Matrix ให้คืนสมาชิกของตารางตามเส้นทางขวา ลง ซ้าย ขึ้น แล้วหดกรอบเข้าหาศูนย์กลาง ความยากไม่ใช่การเดิน แต่คือไม่อ่านแถวหรือคอลัมน์กลางซ้ำเมื่อตารางเหลือเส้นเดียวครับ

สรุปโจทย์ด้วยคำของเรา

รับเมทริกซ์สี่เหลี่ยมที่แต่ละแถวยาวเท่ากัน คืน list ที่มีทุกช่องครั้งเดียวตามเข็มนาฬิกาจากมุมซ้ายบน เราต้องรองรับตารางแถวเดียว คอลัมน์เดียว สี่เหลี่ยมผืนผ้า และช่องเดียว

วิธีที่ 1: บีบขอบสี่ด้าน

ถือ top, bottom, left, right เหมือนเชือกกั้นพื้นที่ เดินขอบบนและขวาก่อน จากนั้นตรวจว่ายังเหลือหลายแถว/คอลัมน์จึงเดินขอบล่างกับซ้าย แล้วขยับเชือกเข้าด้านใน

• เวลา: O(rows × cols) เพราะอ่านทุกช่องครั้งเดียว
• หน่วยความจำเพิ่ม: O(1) ไม่นับ list คำตอบ
• จุดเสี่ยง: ต้องตรวจ top <= bottom และ left <= right ก่อนขอบย้อนกลับ

วิธีที่ 2: เดินตามทิศพร้อม visited set

ถือทิศขวา ลง ซ้าย ขึ้น ถ้าช่องถัดไปออกนอกตารางหรือเคยเยี่ยม ให้หมุนทิศ วิธีนี้จำลองภาพตรงไปตรงมาแต่ต้องเก็บทุกตำแหน่งที่ผ่าน

• เวลา: O(rows × cols)
• หน่วยความจำเพิ่ม: O(rows × cols)
• จุดเด่น: ปรับไปใช้กับ board ที่มีช่องห้ามผ่านได้ง่ายกว่า
• จุดเสี่ยง: state มากขึ้นและใช้หน่วยความจำเกินจำเป็นสำหรับตารางทึบ

import unittest


def spiral_boundaries(matrix):
    if not matrix or not matrix[0]:
        return []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    answer = []

    while top <= bottom and left <= right:
        answer.extend(matrix[top][left : right + 1])
        top += 1

        for row in range(top, bottom + 1):
            answer.append(matrix[row][right])
        right -= 1

        if top <= bottom:
            for col in range(right, left - 1, -1):
                answer.append(matrix[bottom][col])
            bottom -= 1

        if left <= right:
            for row in range(bottom, top - 1, -1):
                answer.append(matrix[row][left])
            left += 1

    return answer


def spiral_visited(matrix):
    if not matrix or not matrix[0]:
        return []
    rows, cols = len(matrix), len(matrix[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    row = col = direction = 0
    seen = set()
    answer = []

    for _ in range(rows * cols):
        answer.append(matrix[row][col])
        seen.add((row, col))
        dr, dc = directions[direction]
        next_row, next_col = row + dr, col + dc
        if not (0 <= next_row < rows and 0 <= next_col < cols) or (
            next_row,
            next_col,
        ) in seen:
            direction = (direction + 1) % 4
            dr, dc = directions[direction]
            next_row, next_col = row + dr, col + dc
        row, col = next_row, next_col
    return answer


class SpiralTests(unittest.TestCase):
    def test_square(self):
        matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
        expected = [1, 2, 3, 6, 9, 8, 7, 4, 5]
        self.assertEqual(spiral_boundaries(matrix), expected)
        self.assertEqual(spiral_visited(matrix), expected)

    def test_thin_shapes(self):
        self.assertEqual(spiral_boundaries([[1, 2, 3]]), [1, 2, 3])
        self.assertEqual(spiral_boundaries([[1], [2], [3]]), [1, 2, 3])

    def test_empty(self):
        self.assertEqual(spiral_boundaries([]), [])


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

Decision table

สถานการณ์	ขอบสี่ด้าน	ทิศ + visited
input ใหญ่	ดีที่สุด เพราะ memory คงที่	ใช้ memory ตามจำนวนช่อง
memory จำกัด	เหมาะ	ไม่เหมาะ
เน้น readability	ดีเมื่อคุ้น boundary	ภาพการเดินตรงกว่า
input มีช่องกีดขวาง	ต้องออกแบบใหม่	ปรับเงื่อนไขได้ง่ายกว่า
streaming input	ทั้งคู่ต้องเข้าถึงตารางตามตำแหน่ง	ทั้งคู่ไม่เหมาะกับ stream ทางเดียว
ห้ามแก้ input	ผ่าน	ผ่าน
input sorted	ไม่ช่วย เพราะโจทย์สนใจตำแหน่ง	ไม่ช่วย

Best default: วิธีบีบขอบสี่ด้าน เพราะเวลาเท่ากันแต่ไม่ต้องเก็บ visited และ contract ของโจทย์เป็นเมทริกซ์ทึบ

Edge cases ที่ควรท่องให้เป็นภาพ

• เมทริกซ์ว่างหรือแถวแรกว่าง
• เหลือแถวกลางเส้นเดียว: ห้ามเดินย้อนซ้ำ
• เหลือคอลัมน์กลางเส้นเดียว: ห้ามเดินขึ้นซ้ำ
• สี่เหลี่ยมผืนผ้าที่จำนวนแถวกับคอลัมน์ต่างกันมาก

Recap

• เดินขอบบนและขวาก่อน
• ตรวจขอบก่อนเดินล่างและซ้าย
• ทุกช่องต้องเข้าคำตอบครั้งเดียว
• เลือก boundary เป็นค่าเริ่มต้น; ใช้ visited เมื่อ board ไม่ทึบ