Back to Arrays & Hashing
Medium
Product of Array Except Self
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
Input:nums = [1,2,3,4]
Output:[24,12,8,6]
For each index, the result is the product of all other elements.
Input:nums = [-1,1,0,-3,3]
Output:[0,0,9,0,0]
The zeroes in the array cause most products to be zero.
Constraints
2 <= nums.length <= 10^5-30 <= nums[i] <= 30
Approach
Create two arrays: `L` and `R`. `L[i]` will contain the product of all elements to the left of `i`, and `R[i]` will contain the product of all elements to the right of `i`. After filling these two arrays in O(n) time, the product except self at index `i` is simply `L[i] * R[i]`.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This uses O(n) space for the L and R arrays, which can be optimized further.
Solution.java
class Solution { public int[] productExceptSelf(int[] nums) { int length = nums.length; int[] L = new int[length]; int[] R = new int[length]; int[] answer = new int[length];
// L[i] contains the product of all the elements to the left L[0] = 1; for (int i = 1; i < length; i++) { L[i] = nums[i - 1] * L[i - 1]; }
// R[i] contains the product of all the elements to the right R[length - 1] = 1; for (int i = length - 2; i >= 0; i--) { R[i] = nums[i + 1] * R[i + 1]; }
// Answer is the product of L and R for (int i = 0; i < length; i++) { answer[i] = L[i] * R[i]; }
return answer; }}