Medium · Prefix and Suffix Products
Understand → Visualise → Practice.
Return an array where position i is the product of every input value except nums[i], without division.
The product of all values except nums[i] is (product of values before i) × (product of values after i). Two passes collect both without division.
Walk left to right, writing the running product of earlier values into out[i] before multiplying in nums[i].
Walk right to left with another running product, multiplying it into out[i].
Each position now holds left × right, with no division and O(1) extra space.
O(n) time and O(1) extra space apart from the output.
Dividing the total product by nums[i] fails as soon as the array contains a zero.
Read the full guides first: Big-O and Complexity, Arrays and Dynamic Arrays, Prefix Sums and Difference Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.