Product of Array Except Self

Medium · Arrays & Hashing

Given an integer array nums, return a new array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. You must solve it without using the division operator and in O(n) time. The algorithm should not use division to compute the products.

Examples

Input:  nums = [1,2,3,4]
Output: [24,12,8,6]
Why:    For index 0: 2*3*4=24; for index 1: 1*3*4=12; for index 2: 1*2*4=8; for index 3: 1*2*3=6.

Input:  nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Why:    Since there is a zero in the array, every product except at the zero's own index becomes 0, and at the zero's index the product of the rest is 9.

Constraints

2 <= nums.length <= 10^5; -30 <= nums[i] <= 30; the product of any prefix or suffix of nums fits in a 32-bit integer; division is not allowed and the solution should run in O(n) time

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Product of Array Except Self

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Product of Array Except Self. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.