LeetCode 238 Product of Array Except Self - Example and Complexity Analysis

Trace nums = [2, 3, 4, 5].

First pass (prefix products):

• Initialize: result = [1, 1, 1, 1], leftProduct = 1
• i = 0: result[0] = 1. Update leftProduct = 1 × 2 = 2.
• i = 1: result[1] = 2. Update leftProduct = 2 × 3 = 6.
• i = 2: result[2] = 6. Update leftProduct = 6 × 4 = 24.
• i = 3: result[3] = 24. After: result = [1, 2, 6, 24].

Second pass (multiply by suffix):

• Initialize: rightProduct = 1
• i = 3: result[3] = 24 × 1 = 24. Update rightProduct = 1 × 5 = 5.
• i = 2: result[2] = 6 × 5 = 30. Update rightProduct = 5 × 4 = 20.
• i = 1: result[1] = 2 × 20 = 40. Update rightProduct = 20 × 3 = 60.
• i = 0: result[0] = 1 × 60 = 60. Final: [60, 40, 30, 24].

Two passes through $n$ elements. $O(n)$ time. Output array doesn't count as extra space. $O(1)$ extra space.