Product of Array Except Self

Difficulty: Medium

Problem

You are given an integer array `nums`. Create a new array `result` such that `result[i]` equals the product of **all** numbers in `nums` **except** `nums[i]`.

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

If the input is `nums = [1, 2, 3, 4]`, then: - `result[0]` = 2 × 3 × 4 = 24 - `result[1]` = 1 × 3 × 4 = 12 - `result[2]` = 1 × 2 × 4 = 8 - `result[3]` = 1 × 2 × 3 = 6

Return the `result` array.

Example

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: For each index i, multiply every element except nums[i].

Index 0: (2×3×4)=24
Index 1: (1×3×4)=12
Index 2: (1×2×4)=8
Index 3: (1×2×3)=6

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)