loading

Product of Array Except Self — Step-by-Step Visualization

mediumLeetCode #238ArrayPrefix Sum

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. The algorithm must run in O(n) time and without using the division operation.

Algorithm Pattern

Prefix and Suffix Products

Key Idea

For any index `i`, the product of all elements except `nums[i]` is (product of elements before `i`) * (product of elements after `i`). We can precalculate these 'prefix' and 'suffix' products in O(n) time. To save space, we can store the prefix products in the result array and then multiply by suffix products in a second pass.

Step-by-Step Approach

  1. Initialize `res = [1] * len(nums)`.
  2. Iterate forward: `prefix *= nums[i]`, store in `res` for next index.
  3. Iterate backward: `postfix *= nums[i]`, multiply with `res[i]` and store.
  4. Return `res`.

Common Gotchas

  • No division allowed.
  • Prefix and Postfix (Suffix) must be tracked carefully.
  • O(n) time and O(1) extra space (excluding the result array).

Related Problems

← All problems