Product of Array Except Self
Return an array where answer[i] is the product of every element except nums[i]. Solve it in O(n) without using division.
A way to picture it
People stand in a line, and each wants the product of everybody else. Walk down the line carrying a left basket of everything behind you, then walk back carrying a right basket. Each person just multiplies the two baskets.
How to approach it
answer[i] = (product of everything left of i) × (product of everything right of i). Two sweeps build both halves, and no division is needed.
Example
Input: {"nums":[1,2,3,4]}. Output: [24,12,8,6].
Complexity: O(n) time and O(1) extra space. Two sweeps; the output array doesn't count as extra space.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.