Product of Array Except Self
Medium · Arrays & Hashing · Array · Prefix Sum
Problem
Given an array nums, return an array out where out[i] is the product of every element except nums[i].
Solve it without using division, in O(n) time.
Examples
Input: nums = [1,2,3,4] Output: [24,12,8,6]
24 = 2·3·4, 12 = 1·3·4, and so on.
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
Zeros make every other slot 0.
Constraints
- 2 <= len(nums) <= 10^5
- The product of any prefix or suffix fits in a 32-bit integer
- Division is not allowed
Approaches
- Prefix and suffix arrays — time O(n), space O(n)
Follow-up
Can you solve it using only O(1) extra space? (The output array does not count as extra space.)
Related problems
Start free on Cariara · Coding problems · System design studio
