ข้อ 7 · LC238 Product of Array Except Self 🟡

ขั้นที่ 1 · วิธีแรกที่ทุกคนคิดออก และทำไมโจทย์ห้าม

วิธีแรกที่คิดออกคือคูณทุกตัวให้ได้ผลรวมก่อน แล้วเอาไปหารด้วย nums[i] ทีละตำแหน่ง ซึ่งเร็วและสั้นมาก

โจทย์ห้ามใช้การหารไว้ตรง ๆ แต่เหตุผลที่ลึกกว่านั้นคือ วิธีนั้นพังจริงเมื่อในลิสต์มีเลข 0

def wrong(nums):
    total = 1
    for x in nums:
        total *= x
    return [total // x for x in nums]

def right(nums):
    n = len(nums)
    pre = [1]*n
    suf = [1]*n
    for i in range(1, n):
        pre[i] = pre[i-1] * nums[i-1]
    for i in range(n-2, -1, -1):
        suf[i] = suf[i+1] * nums[i+1]
    return [pre[i]*suf[i] for i in range(n)]

print("nums = [1,2,3,4]")
print("   หารได้ ->", wrong([1,2,3,4]), "| กวาดสองรอบ ->", right([1,2,3,4]))
print()
print("nums = [-1,1,0,-3,3]  (มีเลข 0)")
try:
    print("   หาร ->", wrong([-1,1,0,-3,3]))
except ZeroDivisionError as e:
    print("   หาร -> ZeroDivisionError:", e, "  <- พังเพราะหารด้วย 0")
print("   กวาดสองรอบ ->", right([-1,1,0,-3,3]), "  <- ทำงานได้ปกติ")

nums = [1,2,3,4]
   หารได้ -> [24, 12, 8, 6] | กวาดสองรอบ -> [24, 12, 8, 6]

nums = [-1,1,0,-3,3]  (มีเลข 0)
   หาร -> ZeroDivisionError: integer division or modulo by zero   <- พังเพราะหารด้วย 0
   กวาดสองรอบ -> [0, 0, 9, 0, 0]   <- ทำงานได้ปกติ

เคสแรกให้ผลตรงกัน ทำให้คนคิดว่าวิธีหารใช้ได้ แต่เคสที่สองพังทันที

และถ้าจะฝืนแก้ด้วยการนับจำนวน 0 แล้วแยกเคส โค้ดจะยาวและมีเงื่อนไขเยอะขึ้นเรื่อย ๆ จนไม่คุ้ม

ขั้นที่ 2 · กุญแจของข้อนี้

กุญแจคือเปลี่ยนมุมมองจาก ผลคูณทั้งหมดแล้วเอาตัวเองออก มาเป็น ประกอบขึ้นจากสองฝั่ง

ให้นึกภาพว่าเรายืนอยู่ที่ตำแหน่งหนึ่งในแถว หันซ้ายคูณทุกตัวที่เห็น หันขวาคูณทุกตัวที่เห็น แล้วเอาสองค่ามาคูณกัน

ผลคูณสองฝั่งนี้รวมกันครอบคลุมทุกตัวยกเว้นตัวที่เรายืนอยู่พอดี จึงไม่ต้องหารอะไรเลย

และเราไม่ต้องหันซ้ายหันขวาใหม่ทุกตำแหน่ง เพราะค่าฝั่งซ้ายของตำแหน่งถัดไป ก็คือค่าฝั่งซ้ายของตำแหน่งนี้คูณด้วยตัวที่เพิ่งเดินผ่าน

ขั้นที่ 3 · เดินตามโค้ดทีละสเต็ป

โค้ดข้างล่างพิมพ์การสะสมทุกก้าว ให้ดูว่าค่าใหม่มาจากค่าเดิมคูณอะไร

nums = [1, 2, 3, 4]
n = len(nums)
prefix = [1]*n
for i in range(1, n):
    prefix[i] = prefix[i-1] * nums[i-1]
    print(f"  prefix[{i}] = prefix[{i-1}]({prefix[i-1]}) x nums[{i-1}]({nums[i-1]}) = {prefix[i]}")
print("prefix =", prefix)
suffix = [1]*n
for i in range(n-2, -1, -1):
    suffix[i] = suffix[i+1] * nums[i+1]
    print(f"  suffix[{i}] = suffix[{i+1}]({suffix[i+1]}) x nums[{i+1}]({nums[i+1]}) = {suffix[i]}")
print("suffix =", suffix)
ans = [prefix[i]*suffix[i] for i in range(n)]
for i in range(n):
    print(f"  answer[{i}] = {prefix[i]} x {suffix[i]} = {ans[i]}  (ทุกตัวยกเว้น nums[{i}]={nums[i]})")
print("คำตอบ:", ans)

  prefix[1] = prefix[0](1) x nums[0](1) = 1
  prefix[2] = prefix[1](1) x nums[1](2) = 2
  prefix[3] = prefix[2](2) x nums[2](3) = 6
prefix = [1, 1, 2, 6]
  suffix[2] = suffix[3](1) x nums[3](4) = 4
  suffix[1] = suffix[2](4) x nums[2](3) = 12
  suffix[0] = suffix[1](12) x nums[1](2) = 24
suffix = [24, 12, 4, 1]
  answer[0] = 1 x 24 = 24  (ทุกตัวยกเว้น nums[0]=1)
  answer[1] = 1 x 12 = 12  (ทุกตัวยกเว้น nums[1]=2)
  answer[2] = 2 x 4 = 8  (ทุกตัวยกเว้น nums[2]=3)
  answer[3] = 6 x 1 = 6  (ทุกตัวยกเว้น nums[3]=4)
คำตอบ: [24, 12, 8, 6]

สังเกตว่า prefix[0] เป็น 1 และ suffix[3] เป็น 1 เพราะตำแหน่งริมไม่มีอะไรอยู่ทางนั้น และค่า 1 คือค่ากลางของการคูณที่ไม่เปลี่ยนผลลัพธ์

จุดที่คนพลาดคือ index ในการคูณ ต้องเป็น nums[i-1] ไม่ใช่ nums[i] เพราะเราต้องการทุกตัวที่อยู่ ก่อน i ไม่รวมตัว i เอง

ขั้นที่ 4 · รับคำท้าเรื่อง O(1) พื้นที่เพิ่ม

โจทย์ท้าให้ใช้พื้นที่เพิ่มแค่ O(1) โดยไม่นับลิสต์คำตอบ ซึ่งทำได้ด้วยการยุบสองลิสต์ให้เหลือหนึ่ง

วิธีคือใช้ลิสต์คำตอบเก็บค่า prefix ไปก่อนในรอบแรก แล้วรอบสองใช้ตัวแปรเดียวเดินย้อนกลับ คูณค่า suffix เข้าไปทับทีละตำแหน่ง

เทคนิคนี้ใช้ได้เพราะตอนเดินย้อนกลับ ตำแหน่งที่เรากำลังคูณทับ เราอ่านค่า prefix ของมันไปแล้วเรียบร้อย จึงไม่มีข้อมูลไหนหาย