← Pointer Manipulation

Micro-Drill #133 — Product except self (no div)

Pointer Manipulation Target: 15s

Prefix/suffix product arrays avoid division. O(n) time, O(1) extra space with in-place right pass.

n = len(a)
res = [1] * n
for i in range(1, n): res[i] = res[i-1] * a[i-1]
right = 1
for i in range(n-2, -1, -1):
    right *= a[i+1]
    res[i] *= right

Type it from memory. Go.

Practice Problems

• 238. Product of Array Except Self
• 42. Trapping Rain Water

Related Coding Drills

• Drill #133 — Product of Array Except Self Medium
• Drill #8 — Range sum query (prefix sum) Easy