Product of Array Except Self

Difficulty: Medium

Problem

You are given an integer array `nums`. Build and return a new array `result` of the same length where each `result[i]` is what you get by multiplying together **every** value in `nums` **other than** the one at position `i`.

You must solve it **without using division**.

For example, with `nums = [2, 3, 5, 4]`: - `result[0]` = 3 × 5 × 4 = 60 - `result[1]` = 2 × 5 × 4 = 40 - `result[2]` = 2 × 3 × 4 = 24 - `result[3]` = 2 × 3 × 5 = 30

Example

Input: nums = [2, 3, 5, 4]
Output: [60, 40, 24, 30]
Explanation: For each index i, multiply every element except nums[i].

Index 0: (3×5×4)=60
Index 1: (2×5×4)=40
Index 2: (2×3×4)=24
Index 3: (2×3×5)=30

Brute-force approach

For every index i, loop through the entire array again and multiply all elements except the current one.

Steps

  1. Create an empty result array
  2. For each i, set product = 1
  3. Loop j from 0..n-1 and multiply nums[j] when j != i
  4. Store product into result[i]
  5. Return result

Time complexity: O(n²) · Space complexity: O(n)

Trade-offs

  • Too slow for large inputs due to nested loops
  • Repeats the same multiplications many times
  • Does not meet the intended O(n) time requirement

Optimal approach

Key insight: For each index i: result[i] = (product of everything left of i) × (product of everything right of i). We can compute these products efficiently using two linear passes.

Build the answer using prefix products and suffix products in two passes.

Steps

  1. Initialize result array
  2. Prefix pass: store product of left side in result
  3. Suffix pass: multiply product of right side into result
  4. Return result

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function productExceptSelf(nums):
    n = length(nums)
    result = new array of size n

    # prefix pass
    prefix = 1
    for i from 0 to n-1:
        result[i] = prefix
        prefix = prefix * nums[i]

    # suffix pass
    suffix = 1
    for i from n-1 down to 0:
        result[i] = result[i] * suffix
        suffix = suffix * nums[i]

    return result

Hints

  • Brute force is: for each i, multiply all j != i (O(n²))
  • Optimal uses prefix products and suffix products
  • You can store prefix products directly inside the result array
  • In the second pass, keep a running suffix product and multiply into result

Complexity questions

What is the time complexity of the brute force approach?

O(n²). For every i (n times), we run an inner loop over all elements (n times) → O(n²).

What is the time complexity of the prefix/suffix approach?

O(n). Two linear passes over the array → O(n).

What is the extra space complexity of the optimal approach (excluding output array)?

O(1). We only use two variables (prefix and suffix). The output array doesn’t count as extra space.

Why does result[i] = prefix[i] × suffix[i] give the correct answer?

Because prefix contains product of elements before i and suffix contains product after i. Multiplying left-side product and right-side product gives product of all elements except the current one.

Check your understanding of Product of Array Except Self

What should result[i] contain?

The product of all elements except nums[i]. result[i] is defined as product of all elements except nums[i].

Why is using division not allowed?

Because division breaks when the array contains zero(s). If you do totalProduct / nums[i], it fails when nums has zeros. The problem explicitly forbids division.

For nums = [1, 2, 3, 4], what should result[2] be?

8 (1 × 2 × 4). result[2] is the product of all elements except nums[2] (which is 3). So result[2] = 1 × 2 × 4 = 8.

Related problems

Keep practising