MediumArrays
Product of Array Except Self
amazonmicrosoftapplelinkedinlyft
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Examples
Example 1
Input
nums = [1,2,3,4]
Output
[24,12,8,6]
answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, answer[2] = 1*2*4 = 8, answer[3] = 1*2*3 = 6.
Example 2
Input
nums = [-1,1,0,-3,3]
Output
[0,0,9,0,0]
Because there is a zero in the array at index 2, most products will be 0. answer[2] = (-1)*1*(-3)*3 = 9.
Constraints
- 2 <= nums.length <= 105
- -30 <= nums[i] <= 30
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Optimal complexity
Time
O(n)
Space
O(1)
One problem, two ways to prep
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.