0238.Product of Array Except Self

• Link: 238. Product of Array Except Self - Medium
• Track: NeetCode150

Question

• Example 1:
  • Input: nums = [1,2,3,4]
  • Output: [24,12,8,6]

Restate the problem

• Given integer array nums
• Calculate the product of all elements except nums[i]
• Return the array res
• Requirement
  • Do not use division

Edge Case

• If length == 1, return [1]
• support nums has zeros

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Prefix	O(n)	O(1)
Method 2	Separate prefix + suffix	O(n)	O(n)

Method 1 - Prefix

Explain:

nums = [1,2,3,4]
prefix = [1,1,2,6]
suffix = [24,12,4,1]
 
result = prefix * suffix = [24,12,8,6]

Approach

• Initialize res with all 1s.
• Left pass (prefix):
  Maintain prefix = product(nums[0..i-1]).
  Set res[i] = prefix, then update prefix *= nums[i].
• Right pass (suffix):
  Maintain suffix = product(nums[i+1..n-1]).
  Multiply res[i] *= suffix, then update suffix *= nums[i].
• res[i] = (left product) * (right product).

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
 
        prefix = 1
        for idx in range(n):              # from 0 to 3
            res[idx] *= prefix
            prefix *= nums[idx]
        
        suffix = 1
        for idx in range(n - 1, -1, -1):  # from 3 to 0
            res[idx] *= suffix            # suffix is product of nums[i+1..] 
            suffix *= nums[idx]           # 1 -> 4 -> 12 -> 24
        
        return res

Complexity

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

Method 2 - Separate prefix + suffix

Approach

1. Create a prefix array and a suffix array.
2. Fill the prefix array with left-side products.
3. Fill the suffix array with right-side products.
4. Multiply prefix[i] and suffix[i] to get the result.

Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        
        cur = 1
        prefix = [1] * n
        for i in range(1, n):
            cur *= nums[i - 1]
            prefix[i] = cur
 
        cur = 1
        suffix = [1] * n
        for i in range(n - 2, -1, -1):
            cur *= nums[i + 1]
            suffix[i] = cur
        
        res = [1] * n
        for i in range(n):
            res[i] = prefix[i] * suffix[i]
        
        return res

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Common mistake

• Suffix, right-side product