DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Product of Array Except Self

mediumArrays and hashing

Problem statement

You are given a list of integers nums. Build a list answer of the same length where answer[i] is the product of every value in nums except nums[i].

Do it in O(n) time and without using division. You can assume every product fits in a 32-bit integer.

Examples

Example 1

Input: nums = [2, 3, 4, 5]

Output: [60, 40, 30, 24]

Explanation: For index 0: 3 × 4 × 5 = 60. For index 3: 2 × 3 × 4 = 24.

Example 2

Input: nums = [3, 0, 2]

Output: [0, 6, 0]

Explanation: Only index 1 leaves the zero out, so only it is non-zero: 3 × 2 = 6.

Hints

Approach

Drop the helper arrays. Store the left products directly in answer, then sweep from the right with a single variable holding the product of everything to the right.

  1. Fill answer[i] with the left product, exactly as in the previous approach.
  2. Set suffix = 1. Walk i from the last index down to 0.
  3. Multiply answer[i] by suffix, then update suffix *= nums[i].

The order in step 3 matters: answer[i] must use the suffix before nums[i] is folded in, because nums[i] itself is excluded.

ComplexityTime O(n)Space O(1) extra
Python
class Solution:
def productExceptSelf(self, nums: list[int]) -> list[int]:
n = len(nums)
answer = [1] * n
for i in range(1, n):
answer[i] = answer[i - 1] * nums[i - 1]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer

Follow-up questions

  • Solve it if division is allowed. How do you handle one zero, and two or more zeros?
  • Return, for each index, the sum of all values except that one, but only within a window of k on each side.

Frequently asked questions

Dividing the total product by nums[i] breaks as soon as there is a zero: with one zero you would divide by zero, and with two every answer is zero. The prefix and suffix approach handles zeros with no special cases.

By convention, the space you must return is not counted. The optimal version uses only one extra variable, suffix, on top of it.

Very. Prefix sums are how you answer "total requests between minute 10 and minute 25" instantly from per-minute counters, and a left pass plus a right pass is a common way to compute a value that depends on both sides of a point in a time series.