Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 238 Product of Array Except Self - Walkthrough

Prefix and suffix products

Compute product of all elements except self for arr=[1,2,3,4]arr = [1, 2, 3, 4] without division. Prefix products: [1,1,2,6][1, 1, 2, 6] (product of elements before ii). Suffix products: [24,12,4,1][24, 12, 4, 1] (product of elements after ii).

Answer: prefix[i]×suffix[i]prefix[i] \times suffix[i]. For index 00: 1×24=241 \times 24 = 24. For index 11: 1×12=121 \times 12 = 12. For index 22: 2×4=82 \times 4 = 8. For index 33: 6×1=66 \times 1 = 6. Result: [24,12,8,6][24, 12, 8, 6]. This handles zeros correctly: if one zero exists, only its position has nonzero result.