Arrays & Strings
Two passes instead of one
Why it matters
Feature pipelines often derive one output per input position while excluding that position's own value. Recomputing the rest of a large row for every output multiplies the work, and division is unsafe when values can be zero. The result must be produced in linear time without division or another output-sized workspace.
Example
Product of Array Except Self
Given nums, return an array answer where answer[i] is the product of every element in nums except nums[i].
- Input
- nums = [1, 2, 3, 4]
- Output
- [24, 12, 8, 6]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Product of Array Except Self
nums = [1, 2, 3, 4]→[24, 12, 8, 6]
The baseline, Multiply the others for each index, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
For [1, 2, 3, 4], answer[2] combines the left product 1 × 2 with the right product 4 to make 8. Rather than rescan the other three values for every index, collect left and right products across two passes.
For nums = [1, 2, 3, 4], the forward pass writes products from the left into answer: [1, 1, 2, 6]. At index 2, for example, 2 is 1 × 2, the product before the 3.
The backward pass carries the product to the right. It starts at 1 after the 4, then grows to 4, 12, and 24. Multiplying those values into [1, 1, 2, 6] produces [24, 12, 8, 6]. Because neither pass divides, zeros need no special case.
Visual anchor
Product of Array Except Self
nums
answer
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.