DSA With AI
Week 1 ยท Arrays & Hashing

Product of Array Except Self

Return an array where each position contains the product of all other positions, without using division.

Medium Arrays & Hashing Week 1 Practice runner

Frame the problem

  • Division is not allowed in the standard problem.
  • Zeros must work naturally.
  • The output array does not count as extra space in the common follow-up.
1. Reveal example inputs and outputs

Example 1

Input:

product_except_self([
  1,
  2,
  3,
  4
])

Output:

[
  24,
  12,
  8,
  6
]

Example 2

Input:

product_except_self([
  -1,
  1,
  0,
  -3,
  3
])

Output:

[
  0,
  0,
  9,
  0,
  0
]
2. Brute force first

How would you multiply every other element for each index? Which products are recomputed many times?

3. Reveal the insight ladder
  1. The product except self is product of everything to the left times everything to the right.
  2. First pass stores prefix products.
  3. Second pass multiplies by a rolling suffix product.
  4. Zeros require no special case with this approach.
4. Dry run before code
  1. nums = [1, 2, 3, 4].
  2. Prefix pass creates [1, 1, 2, 6].
  3. Suffix pass multiplies by 24, 12, 4, 1 as it moves from right to left, producing [24, 12, 8, 6].
5. Reveal final Python solution 
def product_except_self(nums):
    result = [1] * len(nums)
    prefix = 1
    for i, value in enumerate(nums):
        result[i] = prefix
        prefix *= value

    suffix = 1
    for i in range(len(nums) - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

Complexity: Time O(n), extra space O(1) beyond the output array.

Interview narration

  • I decompose the product into left and right sides.
  • The output array can hold prefix products before it becomes the final answer.
  • The suffix pass completes each position without division.

Common traps

  • Using division and failing on zeros.
  • Allocating separate left and right arrays when the follow-up asks for O(1) extra space.
  • Updating prefix or suffix before storing it at the current index.

Follow-up drills

1. Why does this handle zeros?

Every position is built from actual products on both sides. If a zero is outside the current index, it appears in one of those rolling products and correctly makes the answer zero.

2. What if division were allowed?

You still need careful zero handling: no zeros means total_product / nums[i], one zero means only the zero index gets product of nonzero values, two zeros means all outputs are zero.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.