Skip to main content
DSA patterns

Product of Array Except Self

mediumArrays and hashingMetaAmazonAccentureWipro

Problem statement

You are given an integer array nums. Return an array answer where answer[i] is the product of every value in nums except nums[i].

You can't use division, and the whole thing has to run in O(n) time — so you can't just compute the total product once and divide it by each value (that also breaks the moment a zero shows up). This shape comes up whenever you need "everyone else's total" per item, like splitting a shared cost among team members based on what everyone but them contributed.

Examples

Example 1

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

Output: [24,12,8,6]

Explanation: answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, answer[2] = 1*2*4 = 8, answer[3] = 1*2*3 = 6.

Example 2

Input: nums = [-1,1,0,-3,3]

Output: [0,0,9,0,0]

Explanation: Every position except index 2 has a zero somewhere else in the array, so its product is 0. answer[2] = -1*1*-3*3 = 9, the product of everything except the zero itself.

Hints

Hint 1: Without the no-division rule, this would be easy: multiply everything, then divide by nums[i]. Since you can't divide, think about what you'd need to know about the values before i and the values after i separately.

Approach

Optimal: Prefix in output, running suffix

Intuition

The follow-up asks for O(1) extra space, not counting the output array. The prefix/suffix approach uses two full arrays — but you don't need to keep both around at once. Write the prefix products directly into the output array in the first pass. Then, in a second pass from right to left, keep just one running number for the suffix product and multiply it into each slot of the output array as you go. The output array ends up holding exactly what prefix[i] * suffix[i] would have, but you never allocated a second array.

Steps

  1. Set answer[0] = 1, then fill left to right: answer[i] = answer[i-1] * nums[i-1]. After this pass, answer[i] holds the product of everything to the left of i — the same as prefix[i] before.
  2. Start a single running number suffix = 1.
  3. Walk from the last index down to 0: multiply answer[i] by suffix, then update suffix *= nums[i] for the next (more-to-the-left) index.
  4. Return answer.

Dry run

nums = [1, 2, 3, 4]

After the left-to-right pass: answer = [1, 1, 2, 6] (the prefix products).

i (right to left) answer[i] *= suffix suffix *= nums[i]
3 6 * 1 = 6 suffix = 1*4 = 4
2 2 * 4 = 8 suffix = 4*3 = 12
1 1 * 12 = 12 suffix = 12*2 = 24
0 1 * 24 = 24 suffix = 24*1 = 24

answer = [24, 12, 8, 6], matching the prefix/suffix approach with one array instead of three.

Edge cases: the same zero handling still applies — a zero anywhere in nums folds into either the prefix pass or the suffix pass for every other index, sending their answer to 0.

Complexity

Time O(n) - one left-to-right pass to build the prefix products, one right-to-left pass to fold in the suffix products. Two passes total, so the work is O(n).

Space O(1) - extra — only the single running `suffix` value and the loop counter use extra memory; the answer array is the output array itself.

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


if __name__ == "__main__":
    print(Solution().productExceptSelf([1, 2, 3, 4]))       # [24, 12, 8, 6]
    print(Solution().productExceptSelf([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]
RecapThe whole problem in a few lines, for the night before
  • Spot it: for each index, the product of every other element, and division is not allowed
  • Idea: result[i] = product of everything to the left times product of everything to the right; build the left products first, then multiply in a running right product
  • Cost: O(n) time, O(1) extra space (the output is not counted)
  • Trap: dividing by the total product breaks when the array has a zero

Interview follow-ups

  • What if nums also updates in place, one value at a time, and you need the full answer array after every update?

    Recomputing the whole O(n) pass after every single update would make m updates cost O(n*m). Instead, keep a running total product and a count of how many zeros are currently in nums. If there are zero zeros, every answer[i] equals total / nums[i] (division is fine here since you're not solving the original no-division constraint, just this follow-up); if there's exactly one zero, only that index gets a non-zero answer, equal to the product of every non-zero value; if there are two or more zeros, every answer is 0. Updating the total and the zero count after a single value change is O(1), though computing any one answer[i] on demand is still O(1) with this running state — a segment tree over products would be the general-purpose fix if you needed range updates instead of single-value ones.

  • Can you do this without ever allocating extra arrays, in a language where you can't write into the output array while still reading nums (nums and answer must stay independent copies)?

    Yes — the two-pass idea still works with O(1) extra scalars even without reusing the output array as scratch space in the first pass. Compute the prefix products directly into answer as shown, since answer is the required output and writing into it doesn't touch nums; the second, right-to-left pass only needs the single running suffix variable, never a second array. The only case where you'd need real extra arrays is if the output itself had to be treated as read-only during construction, which isn't a normal constraint for this problem.

Frequently asked questions

Two reasons. First, the problem explicitly forbids division. Second, even if it didn't, that trick breaks the moment any value in nums is 0 — you'd be dividing by zero for every other index, and the one index that actually has a non-zero answer becomes impossible to recover without redoing the work anyway. The prefix/suffix approach sidesteps this entirely because it never divides.

The same shape — "everyone else's total, for each item" — shows up when splitting a shared resource or cost proportionally to what everyone but that item contributed: allocating a shared budget across teams based on everyone else's spend, or computing each replica's share of total load excluding itself for a rebalancing decision. It's a good check for whether someone reaches for prefix/suffix products instead of reaching for division and getting tripped up by zeros.

It uses O(1) extra memory beyond the output array — a single running suffix value and a loop counter. The output array itself still needs to exist to hold n results, but the problem explicitly says the output array doesn't count against the space bound, since you have to produce it no matter what.

Every index's answer becomes 0, because the product of "everything except nums[i]" still includes at least one of the other zeros. Only when there's exactly zero or exactly one zero in the whole array can any position have a non-zero answer — with one zero, only that zero's own index gets a non-zero product (the product of everything else); with zero zeros, every index gets a non-zero product.