Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Build every product without division: The Mirror Products.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Prefix and suffix products matches the clues
- 2Keep this true after every move: before each backward step, answer[i] holds the left product and suffix holds the right product
- 3Reach the result within O(n) time, O(1) extra space beyond output
Rules and pressure
- Target cost: O(n) time, O(1) extra space beyond output
- State rule: before each backward step, answer[i] holds the left product and suffix holds the right product
Lesson 1 of 3
Live algorithm trace
Prefix and suffix products
Complete execution1 of 7
Initialize neutral output values and a prefix product of 1.
1
answer = [1] * n2
prefix = 13
store prefix, then multiply by nums[i]4
suffix = 15
multiply answer[i] by suffix6
multiply suffix by nums[i]7
return answeranswer = [1, 1, 1, 1]prefix = 1
Truth to preserve / Cost target
Truth to preserve
before each backward step, answer[i] holds the left product and suffix holds the right product
Cost target
O(n) time, O(1) extra space beyond output
Each answer needs everything to its left and everything to its right. A forward pass stores left products, then a backward pass multiplies in a rolling right product without dividing.
Your call · What should guide every step of this algorithm?