Skip to content

Shelf Inventory Snapshot

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Shelf Inventory Snapshot

A store tracks daily units sold per shelf in a list nums. For each shelf, corporate wants the product of every other shelf's number, and you are not allowed to use the division operator.

Given nums, return a list answer where answer[i] is the product of all elements of nums except nums[i].

def product_except_self(nums):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Arrays, Prefix Products, Two-Pass Accumulation

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: Why can't we just compute the total product and divide by nums[i] for each shelf?

    • A: The problem explicitly forbids the division operator. Division would also break when a shelf sold 0 units, since dividing by zero is undefined.

  • Q: What happens when the list contains a zero?

    • A: Every position except the zero's position gets a product of 0. The zero's own position gets the product of all the other elements. If there are two or more zeros, every position is 0.

  • Q: Can the list contain negative numbers?

    • A: Yes. The second example includes -1 and -3; multiplication handles signs naturally, so no special-casing is needed.
HAPPY CASE
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, answer[2] = 1*2*4 = 8, answer[3] = 1*2*3 = 6.

EDGE CASE
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: The zero at index 2 forces every other position's product to 0. Index 2 itself gets (-1)*1*(-3)*3 = 9.

Input: nums = [0, 0, 2]
Output: [0, 0, 0]
Explanation: With two zeros in the list, every "product of the others" includes at least one zero, so the entire answer is 0s.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Array Accumulation Problems, we can consider the following approaches:

  • Prefix Products: The product of everything except nums[i] is exactly (product of everything left of i) × (product of everything right of i). This mirrors the prefix-sum pattern, but with multiplication.
  • Two-Pass Accumulation: Build the left-side products in a forward pass, then fold in the right-side products with a backward pass using a single running variable.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
For each shelf i, split the answer into two halves: the product of all shelves before i (its prefix product) and the product of all shelves after i (its suffix product). A forward pass fills the answer list with prefix products; a backward pass multiplies each entry by a running suffix product. No division is ever needed.

1) Create an `answer` list of the same length as `nums`, filled with 1s.
2) Forward pass with a running variable `prefix = 1`:
   a) For each index i from left to right, set answer[i] = prefix.
   b) Then update prefix = prefix * nums[i].
   (After this pass, answer[i] holds the product of all elements left of i.)
3) Backward pass with a running variable `suffix = 1`:
   a) For each index i from right to left, multiply answer[i] by suffix.
   b) Then update suffix = suffix * nums[i].
4) Return `answer`.

⚠️ Common Mistakes

  • Multiplying nums[i] into the running product before writing it into answer[i], which incorrectly includes the current shelf in its own product.
  • Reaching for division with a "total product" — it violates the problem constraint and crashes on zeros.
  • Building full prefix and suffix arrays when a single running variable suffices for the backward pass, wasting O(N) extra space.

4: I-mplement

Implement the code to solve the algorithm.

def product_except_self(nums):
    n = len(nums)
    answer = [1] * n

    # Forward pass: answer[i] holds the product of everything left of i
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

    # Backward pass: multiply in the product of everything right of i
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums = [1, 2, 3, 4]

    • Forward pass: answer = [1, 1, 2, 6] (each entry is the product of the elements to its left).
    • Backward pass: suffix runs 1 → 4 → 12 → 24, giving answer = [124, 112, 24, 61] = [24, 12, 8, 6].
    • Output: [24, 12, 8, 6]

  • Input: nums = [-1, 1, 0, -3, 3]

    • Forward pass: answer = [1, -1, -1, 0, 0].
    • Backward pass: suffix runs 1 → 3 → -9 → 0 → 0, giving answer = [0, 0, 9, 0, 0].
    • Output: [0, 0, 9, 0, 0] (only the zero's own position survives with the product of the other shelves).

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of shelves in nums.

  • Time Complexity: O(N) because we make exactly two linear passes over the list.
  • Space Complexity: O(1) extra space (excluding the answer list required for the output), since each pass uses only a single running product variable.

Clone this wiki locally