What is the time and space complexity of Product of Array Except Self?

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

Product of Array Except Self

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Product of Array Except Self

Approach

Build the result in two passes without using division. First pass computes prefix products: result[i] holds the product of all elements before index i. Second pass multiplies in suffix products from right to left. Each result[i] becomes prefix[i] * suffix[i].

Complexity Analysis

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

Pattern

Prefix Product

Why It Works

The product of all elements except self at index i is the product of everything to its left times everything to its right. Two passes accumulate these partial products without needing division.

Updated Mar 2026