อาเรย์ สตริง และการวัดผลในทางปฏิบัติ

อาเรย์ (array) คือโครงสร้างข้อมูลที่พื้นฐานที่สุด เป็นรากฐานของแทบทุกโครงสร้างที่ซับซ้อนกว่า และเมื่อเรา วัดเวลาจริง ของการทำงานบนอาเรย์ Big O ก็จะเลิกเป็นเพียงสัญลักษณ์บนกระดาน แต่กลายเป็นสิ่งที่จับต้องได้

เมื่อเลขคณิต O(1) นี้ซึมเข้าไปในสัญชาตญาณแล้ว สี่แพทเทิร์น — two pointers, sliding window, prefix sums และ การดำเนินการแบบ in-place — จะเปลี่ยนการเข้าถึงด้วยดัชนีที่เร็วนี้ให้กลายเป็นชัยชนะเชิง asymptotic บนโจทย์จริง นี่คือครึ่งหลังของบทเรียนนี้

แนวคิดหลัก

อาเรย์เก็บข้อมูลใน หน่วยความจำที่ต่อเนื่องกัน (contiguous memory) — ช่องเก็บข้อมูลเรียงติดกันเป็นแถวเดียว ไม่มีช่องว่าง

เพราะข้อมูลเรียงต่อกันและแต่ละสมาชิกมีขนาดเท่ากัน คอมพิวเตอร์จึง คำนวณตำแหน่ง ของสมาชิกตัวที่ i ได้ทันทีด้วยเลขคณิตง่าย ๆ:

ที่อยู่ของ arr[i] = ที่อยู่เริ่มต้น + (i × ขนาดของแต่ละสมาชิก)

การคูณและบวกหนึ่งครั้งจบ ไม่ว่าอาเรย์จะยาวแสนช่องหรือล้านช่อง — นี่คือเหตุผลที่การเข้าถึงด้วยดัชนี (index access) เป็น O(1)

ข้อคิด: ความเร็วของอาเรย์ไม่ได้มาจาก “เวทมนตร์” แต่มาจากการจัดวางข้อมูลให้ที่อยู่คำนวณได้

แต่ความต่อเนื่องนี้ก็มีราคา หากเราต้องการ แทรกสมาชิกตรงกลาง ช่องที่อยู่ถัดไปทั้งหมดต้อง ขยับ ไปด้านหลังหนึ่งช่องเพื่อเปิดที่ว่าง ยิ่งแทรกใกล้ต้นเท่าไร ยิ่งต้องขยับมากเท่านั้น ในกรณีแย่สุดต้องขยับเกือบทุกตัว จึงเป็น O(n)

ต้นทุนของแต่ละการดำเนินการ

การดำเนินการ	Big O	เหตุผลสั้น ๆ
เข้าถึงด้วยดัชนี arr[i]	O(1)	คำนวณที่อยู่ได้ทันทีด้วยเลขคณิต
ต่อท้าย (append)	O(1) เฉลี่ย	เขียนลงช่องว่างท้ายสุด (ดู amortized ด้านล่าง)
แทรกหน้าสุด (insert-front)	O(n)	ทุกตัวต้องขยับไปด้านหลัง ๑ ช่อง
แทรกกลาง (insert-middle)	O(n)	ตัวที่อยู่หลังจุดแทรกต้องขยับทั้งหมด
ลบ (delete)	O(n)	ตัวที่อยู่หลังจุดลบต้องขยับมาเติมช่องว่าง
ค้นหาค่า (search)	O(n)	ต้องไล่ดูทีละตัวจนกว่าจะเจอ (ถ้าไม่เรียงลำดับ)

หมายเหตุเรื่อง append: การต่อท้ายของ list ใน Python เป็น O(1) แบบ เฉลี่ยถัวเฉลี่ย (amortized) เพราะบางครั้งเมื่อช่องเต็ม ระบบต้องขยายอาเรย์และคัดลอกของเดิม ซึ่งเป็น O(n) แต่เกิดนาน ๆ ครั้ง เมื่อเฉลี่ยตลอดการต่อท้ายหลายครั้งจึงถือว่าเป็น O(1)

อาเรย์กับลิงก์ลิสต์: พนันคนละแบบเรื่องหน่วยความจำ

ลิงก์ลิสต์ (linked list) วางเดิมพันตรงข้ามกับอาเรย์ แทนที่จะเป็นก้อนหน่วยความจำต่อเนื่องก้อนเดียว แต่ละสมาชิกอยู่ใน node ของตัวเองที่กระจัดกระจายอยู่ที่ไหนก็ได้ในหน่วยความจำ พร้อมตัวชี้ (pointer) ไปยัง node ถัดไป การอ้อมผ่านตัวชี้นี้คือหัวใจทั้งหมด — การแทรกหน้าสุดเป็น O(1) (แค่เปลี่ยนตัวชี้ head) แต่ไม่มีทางลัดทางเลขคณิตไปยัง “สมาชิกตัวที่ i” — ต้องเดินไล่ทีละ node จาก head เท่านั้น การเข้าถึงด้วยดัชนีจึงตกลงมาเป็น O(n)

การดำเนินการ	อาเรย์	ลิงก์ลิสต์
เข้าถึงด้วยดัชนี x[i]	O(1)	O(n) — ต้องเดินไล่จาก head
แทรก/ลบหน้าสุด	O(n) — ทุกตัวต้องขยับ	O(1) — แค่เปลี่ยนตัวชี้ head
แทรก/ลบท้ายสุด	O(1) เฉลี่ย	O(1) ถ้ามีตัวชี้ tail ไม่งั้น O(n)
แทรก/ลบเมื่อมีตัวชี้ไปยังตำแหน่งแล้ว	O(n) — ยังต้องขยับ	O(1) — ไม่ต้องขยับ แค่เปลี่ยนตัวชี้เพื่อนบ้าน
หน่วยความจำส่วนเกินต่อสมาชิก	ไม่มี	ตัวชี้หนึ่งตัว (หรือสองตัวถ้าเป็น doubly linked)

ข้อคิด: ไม่มีโครงสร้างไหน “ดีกว่า” เสมอไป อาเรย์ชนะเมื่อคุณอ่านด้วยตำแหน่งบ่อย ๆ — กรณีคลาสสิกคือสิ่งที่คุณจะนึกเข้าถึงด้วยดัชนีตามธรรมชาติ เช่นตารางค้นหา (lookup table) ส่วนลิงก์ลิสต์ชนะเมื่อคุณแทรก/ลบที่ตำแหน่งที่รู้อยู่แล้วบ่อย ๆ และแทบไม่ต้องกระโดดไปตำแหน่งที่ i

การเข้าถึงแบบสุ่มปลดล็อก binary search

เพราะ arr[mid] มีต้นทุน O(1) ไม่ว่า mid จะอยู่ตรงไหน อาเรย์ที่ เรียงลำดับแล้ว จึงทำให้เราตัดทิ้งครึ่งหนึ่งของตัวเลือกที่เหลือได้ในทุกขั้นตอน — เช็คสมาชิกตรงกลาง แล้วแล้วแต่ว่ามันใหญ่ไปหรือเล็กไป ก็ไปต่อเฉพาะครึ่งซ้ายหรือครึ่งขวาเท่านั้น

def binary_search(arr: list[int], target: int) -> int:
    left: int = 0
    right: int = len(arr) - 1
    while left <= right:
        mid: int = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

ทุกการเปรียบเทียบตัดพื้นที่ค้นหาลงครึ่งหนึ่ง งานทั้งหมดจึงเป็น O(log n) — สำหรับข้อมูลพันล้านรายการ ใช้การเปรียบเทียบไม่เกินราว ๓๐ ครั้ง

ข้อคิด: binary search ทำงานได้ก็เพราะอาเรย์ให้การเข้าถึงแบบสุ่มที่เป็น O(1) ลองเอาเทคนิค “กระโดดไปตรงกลาง” แบบเดียวกันไปใช้กับลิงก์ลิสต์ดู การกระโดดเองก็มีต้นทุน O(n) แล้ว (ยังต้องเดินไปให้ถึงอยู่ดี) ทำให้ประโยชน์ทั้งหมดหายไป การเข้าถึงแบบสุ่มคือสมมติฐานที่ทำให้อัลกอริทึมนี้เป็นไปได้ ไม่ใช่รายละเอียดปลีกย่อย

สตริงคืออาเรย์ของอักขระ

สตริงก็คือ ลำดับของอักขระ เรียงต่อกัน — มองได้ว่าเป็นอาเรย์ของตัวอักษร การเข้าถึง s[i] จึงเป็น O(1) เช่นเดียวกับอาเรย์

แต่ใน Python สตริงเป็น immutable (เปลี่ยนแปลงไม่ได้) เมื่อเราดู “แก้” สตริง จริง ๆ แล้ว Python ต้องสร้างสตริงใหม่ทั้งก้อนและคัดลอกอักขระเดิมทั้งหมดมาใส่

นี่คือกับดักคลาสสิก — การ ต่อสตริงในลูป:

# ❌ กับดัก O(n²) — ต่อสตริงทีละตัวในลูป
def build_bad(n: int) -> str:
    result = ""
    for i in range(n):
        result = result + str(i)   # สร้างสตริงใหม่ทุกรอบ คัดลอกของเดิมทั้งหมด
    return result

ทุกครั้งที่ result + str(i) ทำงาน Python ต้องคัดลอกอักขระทั้งหมดที่สะสมไว้ออกมาก้อนใหม่ รอบที่ ๑ คัดลอก ๑ ตัว รอบที่ ๒ คัดลอก ๒ ตัว … รวมกันคือ 1 + 2 + ... + n ≈ n²/2 จึงเป็น O(n²)

วิธีแก้คือเก็บชิ้นส่วนไว้ในลิสต์ก่อน แล้วค่อย รวมครั้งเดียว ด้วย "".join():

# ✅ วิธีแก้ O(n) — เก็บใส่ลิสต์ แล้ว join ครั้งเดียว
def build_good(n: int) -> str:
    parts: list[str] = []
    for i in range(n):
        parts.append(str(i))       # append เป็น O(1) เฉลี่ย
    return "".join(parts)          # คัดลอกทั้งหมดเพียงครั้งเดียว

ข้อคิด: ปัญหาเดียวกัน วิธีคิดต่างกัน — ผลต่างคือ O(n²) กับ O(n) ซึ่งเมื่อ n ใหญ่ขึ้น คือความต่างระหว่าง “เสร็จทันที” กับ “ค้างทั้งวัน”

วัดด้วยตัวเอง

ทฤษฎีน่าเชื่อ แต่การได้เห็นตัวเลขขึ้นจอด้วยตาตัวเองคนละเรื่อง ลองใช้ time.perf_counter วัดเวลาจริงของทั้งสองวิธี ที่ขนาด n = ๑ พัน, ๑ หมื่น, ๑ แสน:

import time

def build_bad(n: int) -> str:
    result = ""
    for i in range(n):
        result = result + str(i)
    return result

def build_good(n: int) -> str:
    parts: list[str] = []
    for i in range(n):
        parts.append(str(i))
    return "".join(parts)

for n in (1_000, 10_000, 100_000):
    t0 = time.perf_counter()
    build_bad(n)
    t_bad = time.perf_counter() - t0

    t0 = time.perf_counter()
    build_good(n)
    t_good = time.perf_counter() - t0

    print(f"n={n:>7}  bad={t_bad:.4f}s  good={t_good:.4f}s")

วิธีอ่านผล: ทุกครั้งที่ n เพิ่มขึ้น ๑๐ เท่า

• ถ้าเวลาเพิ่มราว ๑๐ เท่า → เส้นโค้งเป็นเชิงเส้น O(n) (นี่คือ build_good)
• ถ้าเวลาเพิ่มราว ๑๐๐ เท่า → เส้นโค้งเป็นกำลังสอง O(n²) (นี่คือ build_bad)

ตัวคูณที่เพิ่มขึ้นนี่แหละคือ ลายเซ็นของเส้นโค้ง — Big O ที่เคยเป็นนามธรรม ปรากฏออกมาเป็นตัวเลขบนหน้าจอ

Two Pointers: ย่อพื้นที่ค้นหาโดยไม่ต้องวนซ้อนกัน

ลองนึกภาพสองคนเริ่มต้นจากปลายทั้งสองข้างของทางเดิน แล้วเดินเข้าหากัน พร้อมสังเกตสิ่งที่ผ่านไประหว่างทาง — นี่คือแนวคิดทั้งหมด แทนที่จะวนลูปซ้อนเทียบทุกคู่ (O(n²)) เราเก็บดัชนีสองตัวคือ left กับ right แล้วขยับตามสิ่งที่สังเกตเห็น แต่ละตัวชี้ขยับไปข้างหน้าอย่างมาก n ครั้งตลอดทั้งการทำงาน งานทั้งหมดจึงเป็น O(n)

ตัวอย่างที่ ๑ — กลับด้านอาเรย์แบบ in-place (ตัวชี้เริ่มจากปลายทั้งสองข้างแล้วบรรจบกัน):

def reverse_in_place(arr: list[int]) -> None:
    left: int = 0
    right: int = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

ตารางแกะรอยสำหรับ arr = [1, 2, 3, 4, 5]:

ขั้นตอน	left	right	arr หลังสลับ
1	0	4	[5, 2, 3, 4, 1]
2	1	3	[5, 4, 3, 2, 1]
—	2	2	ลูปจบ (left == right)

ตัวอย่างที่ ๒ — หาคู่ตัวเลขที่บวกกันได้เป้าหมาย ในอาเรย์ที่ เรียงลำดับแล้ว (ปลายทั้งสองข้าง แต่ตัวชี้ตัวไหนขยับขึ้นกับผลเปรียบเทียบ):

def find_pair_with_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left: int = 0
    right: int = len(nums) - 1
    while left < right:
        current_sum: int = nums[left] + nums[right]
        if current_sum == target:
            return (nums[left], nums[right])
        elif current_sum < target:
            left += 1   # ผลรวมยังน้อยไป มีแค่ left ที่ใหญ่ขึ้นเท่านั้นที่ช่วยได้
        else:
            right -= 1  # ผลรวมมากไป มีแค่ right ที่เล็กลงเท่านั้นที่ช่วยได้
    return None

ตารางแกะรอยสำหรับ nums = [1, 3, 4, 6, 8, 10], target = 12:

ขั้นตอน	left	right	nums[left]	nums[right]	sum	การกระทำ
1	0	5	1	10	11	sum < target → left += 1
2	1	5	3	10	13	sum > target → right -= 1
3	1	4	3	8	11	sum < target → left += 1
4	2	4	4	8	12	sum == target → คืนค่า (4, 8)

การเรียงลำดับก่อนมีต้นทุน O(n log n) แต่การค้นหาเองเป็นเพียง O(n) — เทียบกับการวนลูปซ้อนเทียบทุกคู่แบบไร้เดียงสาซึ่งเป็น O(n²) เสมอไม่ว่าจะเรียงลำดับหรือไม่

ตัวอย่างที่ ๓ — ลบสมาชิกซ้ำในอาเรย์ที่เรียงลำดับแล้วแบบ in-place (ตัวชี้ทั้งสองเคลื่อนไปทิศทาง เดียวกัน — คู่ “slow/fast”):

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow: int = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1   # จำนวนสมาชิกที่ไม่ซ้ำ ซึ่งตอนนี้ถูกอัดแน่นไว้ด้านหน้า

ตารางแกะรอยสำหรับ nums = [1, 1, 2, 2, 3]:

fast	nums[fast]	nums[slow]	การกระทำ	slow หลังจากนั้น	array หลังจากนั้น
1	1	1	เหมือนกัน → ข้าม	0	[1, 1, 2, 2, 3]
2	2	1	ต่างกัน → slow += 1, เขียนทับ	1	[1, 2, 2, 2, 3]
3	2	2	เหมือนกัน → ข้าม	1	[1, 2, 2, 2, 3]
4	3	2	ต่างกัน → slow += 1, เขียนทับ	2	[1, 2, 3, 2, 3]

ผลลัพธ์: มีสมาชิกไม่ซ้ำ slow + 1 = 3 ตัว อยู่ใน nums[0:3] = [1, 2, 3] — เสร็จในรอบเดียว O(n) โดย ไม่ต้องใช้ อาเรย์เสริมเลย

ข้อคิด: สัญญาณว่าโจทย์ต้องการ two pointers คือ ข้อมูลถูกเรียงลำดับแล้ว (หรือปฏิบัติเสมือนเรียงลำดับได้) และวิธีไร้เดียงสาจะต้องเทียบทุกคู่ด้วยลูปซ้อน two pointers เปลี่ยน O(n²) นั้นให้เป็น O(n) โดยใช้ลำดับที่เรียงแล้ว (หรือส่วนที่ผ่าน/ยังไม่ผ่านการเยี่ยมชม) เพื่อตัดทิ้งคู่ทั้งช่วงในคราวเดียว

Sliding Window: ใช้ผลลัพธ์เดิมซ้ำแทนที่จะคำนวณใหม่

ลองนึกภาพเลื่อนหน้าต่างจริง ๆ ไปบนแถบกระดาษ: เมื่อหน้าต่างเลื่อนไปทางขวาหนึ่งขั้น มันจะเสียตัวอักษรซ้ายสุดไปและได้ตัวอักษรใหม่ทางขวาเข้ามาหนึ่งตัว — ส่วนตรงกลางไม่เปลี่ยนแปลงเลย อัลกอริทึม sliding window ใช้ประโยชน์จากส่วนที่ซ้อนทับกันนี้แหละ แทนที่จะคำนวณหน้าต่างทั้งอันใหม่ทุกครั้งที่เลื่อน

ตัวอย่างที่ ๑ — หน้าต่างขนาดคงที่: ผลรวมมากที่สุดของสมาชิกติดกัน k ตัว:

def max_sum_subarray(nums: list[int], k: int) -> int:
    window_sum: int = sum(nums[:k])
    best: int = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]   # บวกตัวใหม่ ลบตัวเก่าที่หลุดหน้าต่างออก
        best = max(best, window_sum)
    return best

ตารางแกะรอยสำหรับ nums = [2, 1, 5, 1, 3, 2], k = 3:

i	สมาชิกใหม่	สมาชิกที่หลุดออก	window_sum	best
เริ่มต้น	—	—	2+1+5 = 8	8
3	1	2	8 + 1 - 2 = 7	8
4	3	1	7 + 3 - 1 = 9	9
5	2	5	9 + 2 - 5 = 6	9

ผลรวมมากที่สุดคือ 9 จากหน้าต่าง [5, 1, 3] หากไม่ใช้การเลื่อน การคำนวณ sum(nums[i:i+k]) ใหม่ทุกขั้นตอนมีต้นทุน O(n·k) แต่การใช้ผลรวมสะสมซ้ำทำให้เหลือ O(n)

ตัวอย่างที่ ๒ — หน้าต่างขนาดไม่คงที่: สตริงย่อยที่ยาวที่สุดที่ไม่มีอักขระซ้ำ:

def longest_unique_substring(s: str) -> int:
    seen: set[str] = set()
    left: int = 0
    best: int = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

ตารางแกะรอยสำหรับ s = "pwwkew":

right	ตัวอักษร	การลบใน while	left หลังจากนั้น	หน้าต่าง	best
0	p	ไม่มี	0	"p"	1
1	w	ไม่มี	0	"pw"	2
2	w	ลบ p, ลบ w (2 รอบ)	2	"w"	2
3	k	ไม่มี	2	"wk"	2
4	e	ไม่มี	2	"wke"	3
5	w	ลบ w (1 รอบ)	3	"kew"	3

ในที่นี้ left ขยับไปข้างหน้าเท่านั้น ตลอดการทำงานจึงขยับได้มากสุด n ครั้งรวมกัน — เมื่อรวมกับ right ที่วนรอบเดียว อัลกอริทึมนี้จึงเป็น O(n) ไม่ใช่ O(n²) แบบที่จะเกิดขึ้นถ้าเช็คทุกสตริงย่อย

ข้อคิด: sliding window ใช้ได้เมื่อคุณกำลังสแกนหาช่วงต่อเนื่อง (อาเรย์ย่อยหรือสตริงย่อย) และสามารถอัปเดตคำตอบสะสมทีละนิดได้แทนที่จะคำนวณใหม่ทั้งหมด หน้าต่างขนาดคงที่: เลื่อนทีละหนึ่ง บวกหนึ่ง ลบหนึ่ง หน้าต่างขนาดไม่คงที่: ขยาย right ไปเรื่อย ๆ จนเงื่อนไขพัง แล้วหด left จนเงื่อนไขกลับมาเป็นจริงอีกครั้ง

Prefix Sums: จ่ายครั้งเดียว ถามได้ฟรี

ลองนึกถึงยอดรวมสะสมบนใบเสร็จ: ถ้าคุณเก็บผลรวมสะสมไว้ระหว่างไล่ดูรายการ คำถาม “ใช้เงินไปเท่าไรระหว่างรายการที่ ๓ ถึงรายการที่ ๗” ก็แค่ลบยอดสะสมสองค่าเท่านั้น — ไม่ต้องบวกใหม่เลยสักตัว

def build_prefix_sums(nums: list[int]) -> list[int]:
    prefix: list[int] = [0] * (len(nums) + 1)
    for i in range(len(nums)):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix: list[int], left: int, right: int) -> int:
    # ผลรวมของ nums[left..right] แบบรวมปลายทั้งสองข้าง
    return prefix[right + 1] - prefix[left]

ตารางแกะรอยสำหรับ nums = [4, 2, 6, 1, 3, 8] (การสร้างอาเรย์ prefix):

i	nums[i]	prefix[i + 1]
0	4	4
1	2	6
2	6	12
3	1	13
4	3	16
5	8	24

prefix = [0, 4, 6, 12, 13, 16, 24] ทีนี้ range_sum(prefix, 1, 4) — ผลรวมของ nums[1..4] = [2, 6, 1, 3] — คือ prefix[5] - prefix[1] = 16 - 4 = 12 ตรงกับ 2+6+1+3=12 โดยไม่ต้องบวกสมาชิกแม้แต่ตัวเดียวใหม่

การสร้างอาเรย์ prefix มีต้นทุน O(n) เพียงครั้งเดียว หลังจากนั้น ทุก คำถามผลรวมช่วง (range-sum query) มีต้นทุนแค่ O(1) การตอบ q คำถามแบบไร้เดียงสา (บวกใหม่ทุกครั้ง) มีต้นทุน O(n·q) แต่ด้วย prefix sums เหลือแค่ O(n + q) รวมทั้งหมด

ข้อคิด: prefix sums คือทางเลือกที่ถูกต้องเมื่ออาเรย์ต้นฉบับหยุดนิ่ง (หรือแทบไม่เปลี่ยน) และคุณจะถูกถามคำถามผลรวมช่วงบ่อย ๆ คุณแลกต้นทุนครั้งเดียว O(n) กับคำตอบ O(1) ตลอดไปหลังจากนั้น — เป็นการแลกเปลี่ยนแบบคลาสสิกคือ “คำนวณล่วงหน้าครั้งเดียว ถามได้บ่อย”

การดำเนินการแบบ In-Place: แลกเวลาคิดกับหน่วยความจำที่ไม่ต้องเพิ่ม

การดำเนินการแบบ in-place คือการจัดเรียงอาเรย์เดิมใหม่โดยใช้หน่วยความจำเสริมคงที่เท่านั้น — O(1) auxiliary space — แทนที่จะสร้างอาเรย์ที่สองมาเก็บผลลัพธ์ มันคือความต่างระหว่างการจัดเรียงหนังสือบนชั้นเดิม กับการต้องมีชั้นที่สองมาพักหนังสือไว้ชั่วคราว

ตัวอย่าง — หมุนอาเรย์ไปทางขวา k ตำแหน่งด้วยการกลับด้านสามครั้ง โดยใช้ two-pointer reverse ตัวเดิมจากก่อนหน้าซ้ำ:

def reverse_range(nums: list[int], start: int, end: int) -> None:
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start += 1
        end -= 1

def rotate_right(nums: list[int], k: int) -> None:
    n: int = len(nums)
    k %= n
    reverse_range(nums, 0, n - 1)   # กลับด้านทั้งอาเรย์
    reverse_range(nums, 0, k - 1)   # กลับด้าน k ตัวแรกกลับคืน
    reverse_range(nums, k, n - 1)   # กลับด้านส่วนที่เหลือกลับคืน

ตารางแกะรอยสำหรับ nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

ขั้นตอน	เรียกฟังก์ชัน	array หลังจากนั้น
0	เริ่มต้น	[1, 2, 3, 4, 5, 6, 7]
1	reverse_range(0, 6)	[7, 6, 5, 4, 3, 2, 1]
2	reverse_range(0, 2)	[5, 6, 7, 4, 3, 2, 1]
3	reverse_range(3, 6)	[5, 6, 7, 1, 2, 3, 4]

ผลลัพธ์: [5, 6, 7, 1, 2, 3, 4] — หมุนไปทางขวา ๓ ตำแหน่งถูกต้อง โดยใช้แค่ตัวแปรจำนวนคงที่ (start, end, n, k) ไม่ว่า nums จะใหญ่แค่ไหน เทียบกับ nums[-k:] + nums[:-k] ซึ่งถูกต้องเช่นกันและอ่านง่ายกว่า แต่สร้างสำเนา slice สองก้อนแล้วต่อกันเป็นลิสต์ใหม่ทั้งหมด มีต้นทุนหน่วยความจำเสริม O(n) แทนที่จะเป็น O(1)

ข้อคิด: การดำเนินการแบบ in-place สร้างขึ้นจากส่วนประกอบเดียวกันกับ two pointers — reverse_range ข้างต้นคือแพทเทิร์น “สลับแล้วบรรจบ” แบบเดียวกับตัวอย่าง two-sum เป๊ะ การมองเห็นการประกอบกันแบบนี้ต่างหากที่ทำให้คุณสร้าง “หมุน” “แบ่งพาร์ทิชัน” และ “ลบซ้ำ” ได้จากส่วนประกอบเล็ก ๆ ที่ใช้ซ้ำได้ชิ้นเดียว แทนที่จะต้องคิดกลเม็ดใหม่ทุกครั้ง

โจทย์จากโลกจริง

สมมติคุณเขียนสคริปต์สร้าง รายงานหรือไฟล์ log ขนาดใหญ่ โดยรวมข้อความทีละบรรทัด:

# ระบบทำงานเร็วตอนทดสอบกับ log สั้น ๆ ไม่กี่ร้อยบรรทัด
report = ""
for line in log_lines:          # แต่ใน production มีหลายแสนบรรทัด
    report = report + line + "\n"

ตอนทดสอบกับข้อมูลเล็กมันเร็วปกติ แต่พอนำขึ้น production ที่มี log หลายแสนบรรทัด สคริปต์กลับ ช้าลงเรื่อย ๆ จนแทบหยุดนิ่ง

วินิจฉัย: การต่อสตริงในลูปเป็น O(n²) ทุกบรรทัดที่เพิ่มทำให้ Python คัดลอกข้อความที่สะสมไว้ทั้งหมดใหม่ ยิ่งรายงานยาว แต่ละรอบยิ่งช้า

แก้ไข:

# ✅ เก็บใส่ลิสต์ แล้ว join ครั้งเดียว — O(n)
parts: list[str] = []
for line in log_lines:
    parts.append(line)
report = "\n".join(parts)

ข้อคิด: บั๊กด้านสมรรถนะมักหลบซ่อนได้สนิทในชุดข้อมูลขนาดเล็ก แล้วโผล่มาทำร้ายเราเมื่อขึ้น production — การคิดเรื่อง Big O ตั้งแต่แรกคือเกราะป้องกันที่ถูกที่สุด

เกินกว่าตัวอย่างเดียวนี้

สี่แพทเทิร์นข้างต้นไม่ใช่แค่กลเม็ดสำหรับสัมภาษณ์งาน — มันคือเทคนิคเดียวกันที่ระบบ production พึ่งพาอยู่ตลอดเวลา:

• Two pointers — รวม log stream ที่เรียงลำดับแล้วสองสายจากเซิร์ฟเวอร์คนละเครื่อง หรือลบข้อมูลซ้ำในชุด record ที่เรียงลำดับแล้วก่อนเขียนลงดิสก์
• Sliding window — rate limiter (“ผู้ใช้คนนี้ยิง request มากี่ครั้งใน ๖๐ วินาทีที่ผ่านมา”) และ streaming analytics ที่คำนวณค่าเฉลี่ยเคลื่อนที่โดยไม่ต้องสแกนประวัติทั้งหมดใหม่ทุกครั้ง
• Prefix sums — แดชบอร์ดที่ตอบคำถาม “รายได้รวมระหว่างสองวันที่” ซึ่งคำนวณล่วงหน้าไว้ทุกคืน ทำให้ทุกครั้งที่โหลดแดชบอร์ดตอบได้ทันทีแทนที่จะบวกข้อมูลนับล้านแถวใหม่
• In-place operations — ระบบฝังตัวหรือระบบที่จำกัดหน่วยความจำ ซึ่งการเพิ่มหน่วยความจำของอาเรย์เป็นสองเท่าเพียงเพื่อขยับข้อมูลไม่ใช่ตัวเลือกที่ทำได้

แบบฝึกหัด

ข้อ ๑ — สคริปต์หนึ่งใช้เวลา 0.5 วินาทีเมื่อ n = 10,000 ถ้าอัลกอริทึมเป็น O(n²) คาดว่าจะใช้เวลาเท่าไรเมื่อ n = 100,000?

เฉลย

n เพิ่ม ๑๐ เท่า สำหรับ O(n²) เวลาเพิ่ม 10² = 100 เท่า ดังนั้น 0.5 × 100 = 50 วินาที

ข้อ ๒ — โค้ดด้านล่างสร้าง CSV จากข้อมูลและช้ามากเมื่อข้อมูลใหญ่ จงระบุปัญหาและแก้ให้เป็น O(n)

csv = "id,name\n"
for row in rows:
    csv = csv + str(row.id) + "," + row.name + "\n"

เฉลย

ปัญหา: ต่อสตริง csv = csv + ... ในลูป เป็น O(n²)

parts: list[str] = ["id,name"]
for row in rows:
    parts.append(f"{row.id},{row.name}")
csv = "\n".join(parts) + "\n"

ข้อ ๓ — คุณมีอาเรย์ ๑ ล้านสมาชิกและต้องเพิ่มข้อมูลใหม่เข้าไปบ่อย ๆ ควรใช้ append (ต่อท้าย) หรือ insert(0, x) (แทรกหน้าสุด)? เพราะอะไร?

เฉลย

ควรใช้ append เพราะเป็น O(1) เฉลี่ย — เขียนลงท้ายโดยไม่ต้องขยับใคร ส่วน insert(0, x) เป็น O(n) เพราะทุกสมาชิกต้องขยับไปด้านหลัง ๑ ช่องทุกครั้ง หากต้องเพิ่มจากด้านหน้าบ่อย ๆ ควรพิจารณาใช้ collections.deque ซึ่งเพิ่มหน้า/หลังเป็น O(1)

ข้อ ๔ — เมื่อเพิ่ม n จาก ๑,๐๐๐ เป็น ๔,๐๐๐ (เพิ่ม ๔ เท่า) เวลาทำงานเพิ่มจาก 0.1s เป็น 1.6s อัลกอริทึมนี้น่าจะเป็น Big O เท่าไร?

เฉลย

เวลาเพิ่ม 1.6 / 0.1 = 16 เท่า เมื่อ n เพิ่ม ๔ เท่า 16 = 4² จึงเป็น O(n²)

ข้อ ๕ — ทายผลลัพธ์: แกะรอย find_pair_with_sum (ฟังก์ชัน two-pointer จากบทเรียนนี้) บน nums = [1, 2, 4, 6, 10], target = 8 มันคืนคู่ไหน และเปรียบเทียบไปกี่ครั้ง?

เฉลย

ขั้นตอน	left	right	sum	การกระทำ
1	0 (1)	4 (10)	11	sum > target → right -= 1
2	0 (1)	3 (6)	7	sum < target → left += 1
3	1 (2)	3 (6)	8	sum == target → คืนค่า (2, 6)

มันคืนค่า (2, 6) หลังเปรียบเทียบ ๓ ครั้ง — น้อยกว่าจำนวนคู่แบบ O(n²) ที่ลูปซ้อนจะต้องเช็คมาก

ข้อ ๖ — จงหาบั๊ก (และจุดที่พลาดโอกาสปรับให้เร็วขึ้น) ในโค้ด max-sum แบบหน้าต่างคงที่นี้:

def max_sum_subarray_buggy(nums: list[int], k: int) -> int:
    best: int = 0
    for i in range(len(nums) - k):
        best = max(best, sum(nums[i:i + k]))
    return best

เฉลย

มีสองปัญหา:

๑. บั๊ก off-by-one: range(len(nums) - k) ข้ามหน้าต่างสุดท้ายที่ถูกต้องไป ควรเป็น range(len(nums) - k + 1) — ไม่งั้นสำหรับ nums = [1, 2, 3], k = 2 หน้าต่างที่เริ่มจากดัชนี 1 ([2, 3]) จะไม่ถูกเช็คเลย ๒. พลาดโอกาสปรับให้เร็วขึ้น: sum(nums[i:i+k]) คำนวณหน้าต่างทั้งอันใหม่ทุกรอบ มีต้นทุนรวม O(n·k) ควรใช้เทคนิค sliding window แบบผลรวมสะสมจากบทเรียนนี้แทน (บวกตัวใหม่ ลบตัวที่หลุดหน้าต่างออกไป) เพื่อให้ได้ O(n)

def max_sum_subarray(nums: list[int], k: int) -> int:
    window_sum: int = sum(nums[:k])
    best: int = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

ข้อ ๗ — คุณต้องตอบคำถามผลรวมช่วง (range-sum query) ๑๐๐,๐๐๐ ครั้งบนอาเรย์นิ่ง ๑,๐๐๐,๐๐๐ ตัว (อาเรย์เองไม่เปลี่ยนแปลงเลย) จะเลือกวิธีไหน และความซับซ้อนเวลารวมเท่าไร?

เฉลย

เลือก prefix sums สร้างอาเรย์ prefix ครั้งเดียวด้วย O(n) แล้วตอบแต่ละคำถามใน q คำถามด้วย O(1) โดยลบค่า prefix สองค่า รวมทั้งหมด: O(n + q) — ในที่นี้ประมาณ 1,000,000 + 100,000 การดำเนินการ

วิธีไร้เดียงสา (บวกใหม่ทุกช่วงที่ถูกถามทุกครั้ง) มีต้นทุน O(n · q) ในกรณีแย่สุด — สูงถึง 10^11 การดำเนินการ ซึ่งจะไม่มีทางเสร็จในเวลาที่สมเหตุสมผล

ข้อ ๘ — ฟังก์ชัน rotate_right ในบทเรียนนี้ใช้ reverse_range (การสลับแบบ two-pointer) สามครั้ง แทนที่จะสร้างลิสต์ใหม่ด้วย slicing (nums[-k:] + nums[:-k]) ความซับซ้อนหน่วยความจำเสริม (auxiliary space) ของแต่ละวิธีเป็นเท่าไร และทำไมมันถึงสำคัญสำหรับอาเรย์ขนาดใหญ่มาก ๆ?

เฉลย

rotate_right ที่ใช้ reverse_range มีหน่วยความจำเสริม O(1) — มันแค่สลับสมาชิกภายในอาเรย์เดิมโดยใช้ตัวแปรดัชนีจำนวนคงที่ ไม่ว่าอาเรย์จะใหญ่แค่ไหน

nums[-k:] + nums[:-k] ถูกต้องและอ่านง่ายกว่า แต่มันสร้างสำเนา slice สองก้อนแล้วต่อกันเป็นลิสต์ใหม่ทั้งหมด มีต้นทุนหน่วยความจำเสริม O(n) สำหรับอาเรย์ที่มีสมาชิกหลายร้อยล้านตัว นี่คือความต่างระหว่างการดำเนินการที่พอดีในหน่วยความจำสบาย ๆ กับการดำเนินการที่อาจจะไม่พอ

วิพากษ์โค้ดจากปัญญาประดิษฐ์

วิพากษ์ที่ ๑ คุณขอให้ AI เขียนฟังก์ชันรวมรายชื่อผู้ใช้ทั้งหมดให้เป็นข้อความเดียวคั่นด้วยจุลภาค และได้โค้ดนี้กลับมา:

def join_names(users: list[str]) -> str:
    output = ""
    for name in users:
        output = output + name + ", "
    return output[:-2]   # ตัด ", " ตัวสุดท้ายออก

โค้ดนี้ ทำงานถูกต้อง แต่จงวัดเวลาเมื่อ len(users) = ๑๐,๐๐๐ และ ๑๐๐,๐๐๐ แล้วสังเกตว่าเวลาเพิ่มขึ้นเป็นกำลังสองหรือไม่ จากนั้นแก้ให้มีประสิทธิภาพ

เฉลย

ปัญหา: output = output + name + ", " ต่อสตริงในลูป เป็น O(n²) เมื่อ n เพิ่ม ๑๐ เท่า เวลาจะเพิ่มราว ๑๐๐ เท่า

แก้ด้วย ", ".join() ซึ่งเป็น O(n) และอ่านง่ายกว่า:

def join_names(users: list[str]) -> str:
    return ", ".join(users)

join จัดการตัวคั่นระหว่างกลางให้เอง ไม่ต้องตัด “, “ ท้ายสุด และคัดลอกอักขระเพียงครั้งเดียว

วิพากษ์ที่ ๒ คุณขอให้ AI: “เขียนฟังก์ชันเช็คว่าอาเรย์ที่ เรียงลำดับแล้ว มีตัวเลขคู่ไหนบวกกันได้เป้าหมายหรือไม่” และได้โค้ดนี้กลับมา:

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

อ่าน วิพากษ์ แล้วปรับปรุง คำตอบของ AI พลาดที่จะใช้ประโยชน์จากอะไรไป?

เฉลย

โค้ดนี้ ถูกต้อง — มันจะเจอคู่ถ้ามีอยู่จริง จุดที่ต้องวิพากษ์คือมันเป็น O(n²) และมองข้ามข้อมูลชิ้นเดียวที่โจทย์ให้มาฟรี ๆ ไปเลย นั่นคือ อาเรย์เรียงลำดับแล้ว คุณสมบัตินี้แหละคือสิ่งที่ทำให้ใช้แพทเทิร์น two pointers จากบทเรียนนี้ได้ ลดต้นทุนเหลือ O(n):

def has_pair_with_sum(nums: list[int], target: int) -> bool:
    left: int = 0
    right: int = len(nums) - 1
    while left < right:
        current_sum: int = nums[left] + nums[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return False

บทเรียน: คำตอบของ AI อาจถูกต้องในเชิงฟังก์ชันแต่ยังพลาดสัญญาณเชิงโครงสร้างในโจทย์ (การเรียงลำดับ, monotonicity, ความไม่ซ้ำ) ที่จะปลดล็อกแพทเทิร์นที่เร็วกว่าได้ การอ่านเพื่อดูว่า “มันสังเกตเห็นสิ่งที่มันได้รับมาหรือเปล่า” คือทักษะการตัดสิน ไม่ใช่แค่ทักษะไวยากรณ์

🎮 เกมเดฟ: อาเรย์และสตริงในเกม

ตารางกระเบื้อง (tilemap) ก็คืออาเรย์ 2 มิติล้วน ๆ — list ซ้อน list — การเข้าถึงกระเบื้องที่ (row, col) จึงมีต้นทุนแค่ O(1) เหมือนกับการเข้าถึงอาเรย์ 1 มิติทุกประการ การเช็คว่ากล่องสี่เหลี่ยมสองกล่องซ้อนทับกันไหม (AABB) ซึ่งใช้ตลอดเวลาสำหรับ hitbox และการตัดสิ่งที่อยู่นอกจอ (culling) ก็ย่อลงเหลือแค่การเทียบพิกัดสี่ครั้งแทนที่จะไล่สแกนทีละพิกเซล และ depth/z-order buffer ก็เป็นแค่อาเรย์ที่เข้าถึงด้วยลำดับการวาด สัญชาตญาณเรื่องเลขคณิตที่อยู่จากต้นบทเรียนนี้ ถูกนำมาใช้ซ้ำแค่ขยายเป็นสองมิติเท่านั้นเอง

ตัวอย่างที่ใช้งานจริง — เข้าถึง tilemap แบบ O(1) และเช็คการซ้อนทับแบบ AABB:

# ---- แทนแผนที่กระเบื้องด้วยอาเรย์ 2 มิติ ----
ROWS: int = 5
COLS: int = 8
EMPTY: int = 0
WALL: int = 1

tilemap: list[list[int]] = [[EMPTY] * COLS for _ in range(ROWS)]
tilemap[2][4] = WALL   # วางกำแพงที่ row=2, col=4

def get_tile(grid: list[list[int]], row: int, col: int) -> int | None:
    # เช็คขอบเขตก่อนเสมอ ไม่งั้นดัชนีเกินขอบจะทำให้โปรแกรมพัง ไม่ใช่แค่ทำงานผิด
    if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
        return None
    return grid[row][col]   # O(1): เข้าถึงดัชนีสองครั้ง ไม่ต้องไล่สแกน

def is_walkable(grid: list[list[int]], row: int, col: int) -> bool:
    tile: int | None = get_tile(grid, row, col)
    return tile is not None and tile != WALL


# ---- กล่องล้อมรอบ (Rect) และการเช็คซ้อนทับแบบ AABB ----
class Rect:
    def __init__(self, x: int, y: int, w: int, h: int) -> None:
        self.x: int = x
        self.y: int = y
        self.w: int = w
        self.h: int = h

# ❌ ไร้เดียงสา: ไล่เช็คทีละพิกเซล — O(w×h)
def overlaps_naive(a: Rect, b: Rect) -> bool:
    for px in range(a.x, a.x + a.w):
        for py in range(a.y, a.y + a.h):
            if b.x <= px < b.x + b.w and b.y <= py < b.y + b.h:
                return True
    return False

# ✅ AABB — เทียบพิกัดโดยตรง O(1) ไม่ว่ากล่องจะใหญ่แค่ไหน
def aabb_overlap(a: Rect, b: Rect) -> bool:
    return (
        a.x < b.x + b.w and a.x + a.w > b.x and   # ซ้อนทับกันบนแกน x ไหม
        a.y < b.y + b.h and a.y + a.h > b.y        # ซ้อนทับกันบนแกน y ไหม
    )

get_tile ไม่ต้องไล่สแกนเลย — มันคือเลขคณิต ที่อยู่เริ่มต้น + offset แบบเดียวกับต้นบทเรียนนี้ เพียงแค่ขยายไปสองมิติ ส่วน aabb_overlap เปลี่ยนการไล่สแกนทีละพิกเซลให้เหลือแค่การเปรียบเทียบสี่ครั้ง: กล่องสองกล่องจะ ไม่ ซ้อนทับกันก็ต่อเมื่อกล่องหนึ่งอยู่คนละฝั่งของอีกกล่องบนแกนใดแกนหนึ่งอย่างสมบูรณ์ ดังนั้น “ไม่แยกจากกันบนทั้งสองแกน” จึงเท่ากับ “ซ้อนทับกัน” พอดี

รูป: tilemap ขนาด 5×8 — tilemap[row][col] เข้าถึงกระเบื้องที่ถูกไฮไลต์ที่ (2, 4) ด้วยต้นทุน O(1)

แบบฝึกหัด

เกม ๑ จากตัวแปร tilemap ข้างต้น (5 แถว × 8 คอลัมน์ มีกำแพงที่ (2, 4)) get_tile(tilemap, 2, 4) จะคืนค่าอะไร แล้ว get_tile(tilemap, 0, 7) ล่ะ?

เฉลย

get_tile(tilemap, 2, 4) คืนค่า 1 (WALL) เพราะตำแหน่งนั้นถูกตั้งเป็นกำแพงไว้แล้ว get_tile(tilemap, 0, 7) คืนค่า 0 (EMPTY) — อยู่ในขอบเขต (คอลัมน์สุดท้ายของแถวแรก) แต่ไม่เคยถูกตั้งเป็นกำแพง

เกม ๒ นี่คือ get_tile เวอร์ชันมีบั๊กที่เช็คขอบเขตแค่แถวเดียว:

def get_tile_buggy(grid: list[list[int]], row: int, col: int) -> int:
    if row < 0 or row >= len(grid):
        return None
    return grid[row][col]

เรียก get_tile_buggy(tilemap, 2, 20) แล้วจะเกิดอะไรขึ้น? จงแก้บั๊ก

เฉลย

เพราะไม่ได้เช็คขอบเขตของ col เลย grid[row][20] จะโยน IndexError ทันที เนื่องจากแต่ละแถวมีแค่ 8 คอลัมน์ (ดัชนี 0-7) ทางแก้คือเช็ค col ด้วยแบบเดียวกับ get_tile เดิม:

if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
    return None

เกม ๓ แกะรอย aabb_overlap สำหรับ player = Rect(10, 10, 20, 20) กับ enemy = Rect(25, 15, 20, 20) ทั้งสองซ้อนทับกันไหม? เงื่อนไขไหนในสี่ข้อเป็นจริงบ้าง?

เฉลย

player ครอบ x ตั้งแต่ 10-30, y ตั้งแต่ 10-30 ส่วน enemy ครอบ x ตั้งแต่ 25-45, y ตั้งแต่ 15-35

• a.x < b.x+b.w → 10 < 45 → จริง
• a.x+a.w > b.x → 30 > 25 → จริง
• a.y < b.y+b.h → 10 < 35 → จริง
• a.y+a.h > b.y → 30 > 15 → จริง

ทั้งสี่เงื่อนไขเป็นจริงหมด → aabb_overlap คืนค่า True ซ้อนทับกัน

เกม ๔ คุณต้องวาดกระเบื้องทุกช่องบนจอทีละแถว จากซ้ายไปขวา บนลงล่าง เมื่อ tilemap เก็บแบบ row-major (tilemap[row][col], แต่ละแถวเป็น list ของตัวเอง) ควรวนลูป for row: for col: หรือ for col: for row: ถึงจะเข้ากับ layout ของหน่วยความจำมากกว่า (cache-friendly) เพราะอะไร?

เฉลย

ควรวน for row in range(ROWS): for col in range(COLS): โดยให้ col อยู่วงในสุด เพราะแต่ละแถวถูกเก็บต่อเนื่องกันเป็นก้อนเดียว (row-major) การไล่ col ในแถวเดียวกันจึงเข้าถึงหน่วยความจำที่ต่อเนื่องกัน ตรงข้ามกับการสลับลำดับ (for col: for row:) ซึ่งกระโดดข้ามไปมาระหว่างแถวต่าง ๆ ทุกครั้งที่ขยับหนึ่งช่อง ทำให้แคชของ CPU พลาดบ่อยกว่ามาก

โจทย์ท้าทายที่ ๑ — ขอบเขตของ flood-fill เขียนฟังก์ชัน flood_fill(grid, start_row, start_col, new_tile) ที่เติม new_tile ให้กับกระเบื้องทุกช่องที่ต่อเนื่องกันเริ่มจาก (start_row, start_col) เหมือนถังสี (paint bucket) ในโปรแกรมแต่งภาพ ระวังสองเรื่อง: (๑) ห้ามให้ index หลุดขอบเขตของ grid (๒) ห้ามเยี่ยมชมกระเบื้องเดิมซ้ำจนวนไม่รู้จบ

แนวทาง

ใช้ BFS/DFS พร้อม stack/queue เก็บพิกัดที่ต้องไปเยี่ยม ก่อนเข้าถึงพิกัดไหนให้เรียก get_tile (ซึ่งเช็คขอบเขตให้แล้วและคืน None เมื่อหลุดขอบ) แทนที่จะ index ตรง ๆ แล้วเติมเฉพาะกระเบื้องที่ค่ายังตรงกับค่าเดิมเท่านั้น — การเช็คค่าเดิมนี่แหละคือสิ่งที่ป้องกันการวนซ้ำไม่รู้จบ เพราะพอเติมแล้วค่าจะเปลี่ยนไปเป็น new_tile ทำให้ไม่ตรงเงื่อนไขอีกต่อไป:

def flood_fill(grid: list[list[int]], start_row: int, start_col: int, new_tile: int) -> None:
    old_tile: int | None = get_tile(grid, start_row, start_col)
    if old_tile is None or old_tile == new_tile:
        return
    stack: list[tuple[int, int]] = [(start_row, start_col)]
    while stack:
        row, col = stack.pop()
        if get_tile(grid, row, col) != old_tile:
            continue   # หลุดขอบเขต, เติมไปแล้ว, หรือคนละกระเบื้อง
        grid[row][col] = new_tile
        stack.extend([(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)])

โจทย์ท้าทายที่ ๒ — ตัดสไปรต์จากสไปรต์ชีต สไปรต์ชีต (sprite sheet) คือภาพใหญ่ภาพเดียวที่บรรจุสไปรต์ย่อยหลายอันเรียงเป็นตารางแบบ row-major เหมือน tilemap ทุกประการ กำหนดให้ SHEET_COLS และขนาดสไปรต์คงที่ (TILE_W × TILE_H) จงเขียนฟังก์ชันที่รับดัชนีสไปรต์เชิงเส้นตัวเดียว (0, 1, 2, …) แล้วคืนกรอบ (x, y, w, h) ของสไปรต์นั้นบนภาพชีต โดยไม่ต้องสแกนพิกเซลแม้แต่ตัวเดียว

แนวทาง

นี่คือสูตรเลขคณิตที่อยู่ ที่อยู่เริ่มต้น + (i × ขนาด) จากต้นบทเรียนนี้เป๊ะ เพียงแค่ขยายไปสองมิติ: แยกดัชนีเชิงเส้นออกเป็นแถวกับคอลัมน์ด้วย row, col = divmod(index, SHEET_COLS) แล้วคำนวณ x = col * TILE_W, y = row * TILE_H ทั้งหมดเป็น O(1):

def sprite_rect(index: int, sheet_cols: int, tile_w: int, tile_h: int) -> Rect:
    row: int = index // sheet_cols
    col: int = index % sheet_cols
    return Rect(col * tile_w, row * tile_h, tile_w, tile_h)

เจาะลึกเพิ่มเติม

• MIT 6.006 — Introduction to Algorithms: Lecture เรื่อง arrays และ dynamic arrays อธิบายต้นทุน append และการขยายอาเรย์ (ocw.mit.edu)
• CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein): บทเรื่อง arrays และ amortized analysis (โดยเฉพาะ aggregate / accounting / potential method)
• Sedgewick & Wayne — Algorithms (4th ed.), Princeton: บทเรื่องโครงสร้างข้อมูลพื้นฐาน (elementary data structures) ยึดโยงตารางเปรียบเทียบอาเรย์-กับ-ลิงก์ลิสต์ด้านบนเข้ากับโค้ดตัวอย่างที่ใช้งานได้จริงสไตล์ Java ที่พอร์ตมาใช้ได้เลย
• Goodrich, Tamassia & Goldwasser — Data Structures and Algorithms in Python: บทที่ 5 “Array-Based Sequences” คือเวอร์ชัน Python-native ของเนื้อหา dynamic array และ amortized append ในบทเรียนนี้เป๊ะ
• Skiena — The Algorithm Design Manual (3rd ed.): แข็งแรงเรื่องสัญชาตญาณ “เทคนิคไหนใช้ตอนไหน” — เนื้อหาเรื่อง two-pointer และ window technique เข้ากันได้ดีกับตัวอย่างที่แกะรอยไว้ข้างต้น
• Bhargava — Grokking Algorithms (2nd ed.): บทที่ 2 เปรียบเทียบอาเรย์กับลิงก์ลิสต์ด้วยภาพประกอบ เป็นทางลัดที่เป็นมิตรที่สุดสำหรับตารางเปรียบเทียบในบทเรียนนี้
• Python docs — เวลาในการทำงานของ list: TimeComplexity wiki สรุป Big O ของแต่ละการดำเนินการบน list
• Python docs — str: Text Sequence Type อธิบายความ immutable ของสตริงและเมท็อด join