Product Except Self

Interview Problem Intermediate Medium Prefix Sum Array

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.productExceptSelf(nums). Return output[i] equal to the product of every nums value except nums[i]. Do not use division; use O(1) auxiliary space excluding output.

Starter code

class Solution:
    def productExceptSelf(self, nums):
        pass

Test cases

positive

{
  "args": [
    [
      1,
      2,
      3,
      4
    ]
  ]
}

Expected: [24,12,8,6]

Wizard outline

Step 1: Initialize Solution.productExceptSelf
Replace the empty starter with the first real state owned by Solution.productExceptSelf. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Positive case
Complete the readable core algorithm for one representative Interview case. Store prefix products in output and multiply a rolling suffix product during a reverse pass.
Step 4: Harden the One Zero boundary
Repair the reviewed boundary and pass the complete submission contract. Before the reverse pass output[i] equals the product left of i. The rolling suffix equals the product right of i, so their multiplication is exactly every value except nums[i].

Footguns and prerequisites

Division-based total products break on zeros and violate the contract.
arrays strings two pointers sliding window

Reviewed references

LeetCode 238 — Product of Array Except Self

Practice prerequisites

Build Prefix Aggregates(opens in a new tab)
Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing product except self as a complete Interview Problem.

Recommended approach and implementation

Write prefix products into output left-to-right, then multiply a rolling suffix product right-to-left.

Why it works: Before the reverse pass output[i] equals the product left of i. The rolling suffix equals the product right of i, so their multiplication is exactly every value except nums[i].

class Solution:
    def productExceptSelf(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        output = [1] * len(nums)
        prefix = 1
        for index, value in enumerate(nums):
            output[index] = prefix
            prefix *= value
        suffix = 1
        for index in range(len(nums) - 1, -1, -1):
            output[index] *= suffix
            suffix *= nums[index]
        return output