Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 238 Product of Array Except Self - Prefix and Suffix

Two directions

Think about what "all elements except ii" means. It's all elements to the left of ii times all elements to the right of ii. Build two arrays:

1.1. prefix[i]prefix[i] = product of all elements before index ii

2.2. suffix[i]suffix[i] = product of all elements after index ii Then answer[i]=prefix[i]×suffix[i]answer[i] = prefix[i] \times suffix[i]. You're using the same "precompute to answer in O(1)O(1)" idea, but with products instead of sums, and in both directions.