ToolMight LogoToolMight
MediumArrays & HashingPattern: Prefix and Suffix ProductsPattern: Space Optimization

Product of Array Except Self

Return an array where output[i] is the product of all elements in nums except nums[i], without using the division operation in O(n) time.

Problem Statement

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.

Examples & Constraints

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: Only index 2 excludes the zero, giving (-1)*1*(-3)*3 = 9. All other indices include 0.
Constraints
  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Prefix & Suffix Running Products (O(1) Extra Space)

Optimal Approach
Time:O(n)
Space:O(1)

First pass: store the running product of all elements to the left of i. Second pass: traverse from right to left while multiplying by the running suffix product in O(1) auxiliary space.

Time ComplexityO(n)

We perform one forward pass of length N and one backward pass of length N. Total operations are 2N = O(n).

Space ComplexityO(1)

The output array does not count toward auxiliary space complexity. Only a single scalar suffix variable is used.

Underlying algorithmic logic

Why Division Is Forbidden

If division were allowed, you could calculate the total product of all elements P and set ans[i] = P / nums[i].
However:

  1. If the array contains a zero 0, division by zero crashes or produces an undefined result.
  2. If there are multiple zeros, every element is zero.
  3. The problem explicitly tests your ability to decompose array dependencies into prefix and suffix relationships.

The Decomposition Mental Model: Left * Right

Notice that for any index i:
product_except_i = (product of all elements left of i) * (product of all elements right of i)

We can compute this in two linear sweeps using the output array itself:

  1. Prefix Sweep (Left to Right):
  • Initialize answer[0] = 1 (no elements exist to the left of index 0).
  • For i from 1 to n - 1: answer[i] = answer[i - 1] * nums[i - 1]
  • Now, answer[i] holds the product of all elements to the left of i.
  1. Suffix Sweep (Right to Left):
  • Maintain a running scalar variable suffix = 1.
  • For i from n - 1 down to 0:
  • Multiply answer[i] *= suffix.
  • Update suffix *= nums[i] for the next element to the left.
  1. Return answer.

Step-by-step execution walkthrough

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

Initialize answer array. Prefix pass sets answer[0] = 1.

answer = [1, ?, ?, ?]
2
Prefix Sweep

answer[1] = 1*1 = 1. answer[2] = 1*2 = 2. answer[3] = 2*3 = 6.

prefix answer = [1, 1, 2, 6]
3
Suffix Sweep (From Right)

suffix = 1. i = 3: answer[3] = 6*1 = 6; suffix = 1*4 = 4. i = 2: answer[2] = 2*4 = 8; suffix = 4*3 = 12.

answer[3]=6, answer[2]=8
4
Finish Leftmost Indices

i = 1: answer[1] = 1*12 = 12; suffix = 12*2 = 24. i = 0: answer[0] = 1*24 = 24.

Final answer: [24, 12, 8, 6]
Advantages
  • •Optimal O(n) runtime with zero division operations
  • •O(1) auxiliary memory using the output array for prefix products
Trade-offs
  • •Requires two full sequential passes over the array

Code Implementations

Copy & paste production-ready solutions for Prefix & Suffix Running Products (O(1) Extra Space) in your language of choice

File: solution.py
Python
def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [1] * n
    # Step 1: Prefix products
    for i in range(1, n):
        res[i] = res[i - 1] * nums[i - 1]
    # Step 2: Suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]
    return res
if __name__ == "__main__":
    test1 = [1, 2, 3, 4]
    test2 = [-1, 1, 0, -3, 3]
    print("test1:", product_except_self(test1))
    print("test2:", product_except_self(test2))
Interactive visualizer available

Understand Array & Matrix Visually

Explore sequential element access, subsegment manipulations, insertion, deletion, and 2D grid matrix walks. Test live edge cases and watch memory state transitions step-by-step.

Launch Array & Matrix Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

2 approaches(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Valid Anagram

Determine whether two strings have the exact same character frequencies. A core problem demonstrating the power of fixed-size frequency buckets over O(n log n) sorting.

2 approaches(O(n))
Learn logic