← all entries
A-006● Day 062026.05.08mediumleetcode #238neetcode150

Product of Array Except Self

#array#prefix-sum
↗ leetcode #238 · product-of-array-except-self
01

Problem

· problem
P.006

Product of Array Except Self

↗ leetcode #238

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.

constraints
  • · 2 ≤ nums.length ≤ 10⁵
  • · −30 ≤ nums[i] ≤ 30
  • · Division operation is forbidden
  • · answer[i] guaranteed to fit in 32-bit integer
// paraphrased summary — see source for full text
examples
example 1input → output
[1,2,3,4]
[24,12,8,6]
example 2input → output
[-1,1,0,-3,3]
[0,0,9,0,0]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What happens if the array contains zeros?
  • ☐
    Can I modify the input array?
  • ☐
    Why can't we use division?
  • ☐
    Why not compute the total product first and then divide?
  • ☐
    Would using a hash map to store intermediate products be clearer?
  • ☐
    Do negative numbers require special handling?
  • ☐
    Do we need separate arrays for prefix and suffix products?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize result array with 1s
○
res = [1] * (len(nums))
○
res = [0] * (len(nums))
○
res = nums[:]
step 2· Left-to-right prefix loop│ nested
○
for i in range(1, len(nums)):
○
for i in range(len(nums)):
○
for i in range(len(nums) - 1):
step 3· Accumulate prefix product│ │ nested
○
res[i] = res[i-1] * nums[i-1]
○
res[i] = res[i-1] * nums[i]
○
res[i] += res[i-1] * nums[i-1]
step 4· Initialize postfix variable
○
postfix = 1
○
postfix = 0
○
postfix = nums[-1]
step 5· Right-to-left suffix loop│ nested
○
for i in range(len(nums) - 1, -1, -1):
○
for i in range(len(nums)):
○
for i in range(len(nums) - 1, 0, -1):
step 6· Multiply result by postfix│ │ nested
○
res[i] *= postfix
○
res[i] = postfix
○
res[i] += postfix
step 7· Accumulate postfix for next iteration│ │ nested
○
postfix *= nums[i]
○
postfix += nums[i]
○
postfix = nums[i]
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def productExceptSelf(self, nums: List[int]) -> List[int]:
3
        res = [1] * (len(nums))
4
5
        for i in range(1, len(nums)):
6
            res[i] = res[i-1] * nums[i-1]
7
        postfix = 1
8
        for i in range(len(nums) - 1, -1, -1):
9
            res[i] *= postfix
10
            postfix *= nums[i]
11
        return res
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[1,2,3,4]
→
[24,12,8,6]
case 2
[-1,1,0,-3,3]
→
[0,0,9,0,0]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.