DSAPrep
MediumArrays & Hashing

Product of Array Except Self

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 product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2

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

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.
Follow-up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
View original on LeetCode ↗

The tempting shortcut is to compute the total product once and divide it by nums[i] for each answer — but division is explicitly disallowed, and it would break on a zero anyway. The actual insight: answer[i] is the product of everything before i times everything after i. Those two pieces can each be built with a simple running pass.

Brute Force

Time O(n²)Space O(1)

For each index, multiply every other element.

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = []
        for i in range(n):
            product = 1
            for j in range(n):
                if j != i:
                    product *= nums[j]
            result.append(product)
        return result

Correct, but for each of the n output positions it redoes an O(n) multiplication pass — O(n²) total, recomputing overlapping products from scratch every time.

Prefix × Suffix Products

OptimalTime O(n)Space O(1)

answer[i] is (product of nums[0..i-1]) * (product of nums[i+1..n-1]). Build the prefix products left-to-right directly into the answer array, then sweep right-to-left multiplying in the suffix products with a single running variable — no division, and no second array needed.

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [1] * n


        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]


        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]


        return answer

Tracing nums = [1, 2, 3, 4] — first the left-to-right prefix pass (before the multiply, answer[i] is set to the running prefix product of everything to its left):

i
1
0
1
1
1
2
1
3
prefix = 1
1 / 4
resultcurrent

answer[0] = prefix (1, product of nothing to the left). Update prefix to 1*1 = 1.

Then the right-to-left suffix pass multiplies each slot by everything to its right:

1
0
1
1
2
2
i
6
3
suffix = 1
1 / 4
result

answer[3] *= suffix (1, nothing to the right yet) -> 6, unchanged. Update suffix to 1*4 = 4.

Correctness: after the prefix pass, answer[i] holds the product of everything strictly to the left of i. Multiplying in the suffix pass’s running product — everything strictly to the right of i — gives exactly the product of all elements except nums[i], with no division and no risk of dividing by a zero.

Complexity: two linear passes over the array — O(n) time. Only two scalar running variables (prefix, suffix) are used beyond the output array, which the problem explicitly excludes from the space count — O(1) extra space, answering the follow-up.