Product of Array Except Self ใน Python

สร้างอาร์เรย์ output ที่ output[i] = ผลคูณของทุกตัวยกเว้น nums[i] ห้ามใช้หาร

ตัวอย่าง

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]

แนวคิด: Prefix & Suffix Product

1. คำนวณ prefix product (ผลคูณทางซ้าย) และ suffix product (ทางขวา)
2. output[i] = prefix[i-1] * suffix[i+1]
3. ทำได้ใน O(n) time, O(1) extra space (ไม่นับ output)

โค้ด (Optimized Space)

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        output = [1] * n
        
        # Prefix pass
        prefix = 1
        for i in range(n):
            output[i] = prefix
            prefix *= nums[i]
        
        # Suffix pass
        suffix = 1
        for i in range(n-1, -1, -1):
            output[i] *= suffix
            suffix *= nums[i]
        
        return output

# ทดสอบ
sol = Solution()
print(sol.productExceptSelf([1, 3, 5, 7, 9]))  # [945, 315, 189, 135, 105]

ผลลัพธ์

[945, 315, 189, 135, 105]

สรุป

สองรอบ loop เดียว ไม่ต้องใช้ array เสริม เทคนิคคลาสสิกสำหรับสัมภาษณ์