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.