1. Understand the problem

• Given an integer array nums, return an array answer such that answer[i] is the product of all elements of nums except nums[i].

• You cannot use division, and the solution must run in O(n) time.

• ✅ Example

Input:  [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Explanation:

For index 0 → 2 × 3 × 4 = 24

For index 1 → 1 × 3 × 4 = 12

For index 2 → 1 × 2 × 4 = 8

For index 3 → 1 × 2 × 3 = 6

2. Ask Clarify Questions

Ask the interviewer things like:

• Are there negative numbers? (✅ yes)

• Can zeros appear in the array? (✅ yes — handle carefully)

• What’s the expected time complexity? (✅ O(n))

• Can I use extra space? (Try O(1) besides output array)

• Will the array always have at least 2 elements?

3. Work Through Examples

1. Example 1: [1, 2, 3, 4]

Left products: → [1, 1, 2, 6] (product of all to the left)

Right products: → [24, 12, 4, 1] (product of all to the right)

Multiply them → [24, 12, 8, 6]

1. Example 2 (Edge Case with Zero): [1, 2, 0, 4]

Only one zero → all others become 0 except the position with zero → product of others = 1×2×4 = 8

✅ Output: [0, 0, 8, 0]

4. Brainstorm 2-3 Solutions

4.1. Naive Solution

• For each index, multiply all other elements.

• Time: O(n²)

• Space: O(1)

4.2. Optimized Solution (Prefix + Suffix Product)

Idea:

• Use two passes: one for prefix product, one for suffix product.

• Multiply them for each index.

5. Implement Solutions

5.1. Brute Force

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n

        for i in range(n):
            prod = 1
            for j in range(n):
                if i == j:
                    continue
                prod *= nums[j]

            res[i] = prod
        return res

• Time complexity: O(N^2).

• Space complexity: O(1) extra space, O(N) for output array.

5.2. Division

• Notes:

  • If you have 2 zeros, the full array must be [0, 0, 0, 0] => Because another 0 cause other product is 0.
  • If you have 1 zeros, the item zero become prod, otherwise 0 => [0, 0, prod, 0]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prod, zero_cnt = 1, 0
        for num in nums:
            if num:
                prod *= num
            else:
                zero_cnt +=  1
        if zero_cnt > 1: return [0] * len(nums)

        res = [0] * len(nums)
        for i, c in enumerate(nums):
            if zero_cnt: res[i] = 0 if c else prod
            else: res[i] = prod // c
        return res

• Time complexity: O(N).

• Space complexity: O(1) extra space, O(N) for output array.

5.3. Prefix & Suffix

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        pref = [0] * n
        suff = [0] * n

        pref[0] = suff[n - 1] = 1
        for i in range(1, n):
            pref[i] = nums[i - 1] * pref[i - 1]
        for i in range(n - 2, -1, -1):
            suff[i] = nums[i + 1] * suff[i + 1]
        for i in range(n):
            res[i] = pref[i] * suff[i]
        return res

• Time complexity: O(N).

• Space complexity: O(N).

5.4. Prefix & Suffix (Optimal)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * (len(nums))

        prefix = 1
        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        return res

• Time complexity: O(N).

• Space complexity:

  • O(1) extra space.
  • O(N) for the output array.