Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/238.html
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.
Example 1:
Input: nums = [1,2,3,4] Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
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.
Follow up: Can you solve the problem in O(1)
extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Algorithm
Related: 1740-Find-Distance-in-a-Binary-Tree
For a certain number, if we know the product of all the numbers before it, and also know the product of all the numbers after it, then the multiplication of the before and after is the result we want.
So we only need to create these two arrays separately and traverse from the two directions back and forth of the array, to create the multiplication and accumulation product arrays.
Algorithm - Follow up
We can optimize the above method space complexity.
Since the final result is to be multiplied into the result res
, it is not necessary to store the product in a separate array, but directly accumulate into the result res
.
- We traverse from the front first, and store the accumulation of the product in the result
res
- Then start traversing from the back, using a temporary variable right, initialized to 1
- Then keep accumulating each time, and finally get the correct result
Code
-
import java.util.Arrays; public class Product_of_Array_Except_Self { public static void main(String[] args) { Product_of_Array_Except_Self out = new Product_of_Array_Except_Self(); Solution s = out.new Solution(); System.out.println(Arrays.toString(s.productExceptSelf(new int[]{1,2,3,4}))); // output: [24,12,8,6] } // combine below solution, 2 for loops into 1 loop class Solution { // @note: int[] is definitely possible to be overflowed, the problem set is troublesome itself public int[] productExceptSelf(int[] nums) { if (nums == null || nums.length == 0) { return nums; } // product from index=0 to index=i-1 position. // @note: excluding current index, fromLeft[i] = nums[0] * nums[1] * ... * nums[i-1] int[] result = new int[nums.length]; result[0] = 1; for (int i = 1; i < nums.length; i++) { result[i] = nums[i - 1] * result[i - 1]; // here excluding current nums[] value } // product from index=n-1 to current position int fromRight = 1; for (int i = nums.length - 1; i >= 0; i--) { // `fromRight` is excluding current-index, at below line result[i] *= fromRight; // here result[] is same as below fromLeft[] fromRight *= nums[i]; // here fromRight value is fromRight[i], for next loop index=i+1, fromRight index=i } return result; } } class Solution_space { public int[] productExceptSelf(int[] nums) { if (nums == null || nums.length == 0) { return nums; } // product from index=0 to index=i-1 position. // @note: excluding current index, fromLeft[i] = nums[0] * nums[1] * ... * nums[i-1] int[] fromLeft = new int[nums.length]; fromLeft[0] = 1; for (int i = 1; i < nums.length; i++) { fromLeft[i] = nums[i - 1] * fromLeft[i - 1]; // here excluding current nums[] value } // product from index=n-1 to current position int[] fromRight = new int[nums.length]; fromRight[nums.length - 1] = 1; for (int i = nums.length - 2; i >= 0; i--) { fromRight[i] = nums[i + 1] * fromRight[i + 1]; } int[] result = new int[nums.length]; for (int i = 0; i < nums.length; i++) { result[i] = fromLeft[i] * fromRight[i]; } return result; } } } ############ class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] ans = new int[n]; for (int i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (int i = n - 1, right = 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; } }
-
// OJ: https://leetcode.com/problems/product-of-array-except-self/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> productExceptSelf(vector<int>& A) { vector<int> ans = A; int N = A.size(), prod = 1; for (int i = N - 2; i >= 0; --i) ans[i] = ans[i + 1] * A[i]; for (int i = 0; i < N; ++i) { ans[i] = prod * (i + 1 < N ? ans[i + 1] : 1); prod *= A[i]; } return ans; } };
-
class Solution(object): # better way def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ dp = [1] * len(nums) for i in range(1, len(nums)): dp[i] = dp[i - 1] * nums[i - 1] prod = 1 for i in reversed(range(0, len(nums))): dp[i] = dp[i] * prod prod *= nums[i] return dp ############ class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) ans = [0] * n left = right = 1 for i, v in enumerate(nums): ans[i] = left left *= v for i in range(n - 1, -1, -1): ans[i] *= right right *= nums[i] return ans
-
func productExceptSelf(nums []int) []int { n := len(nums) ans := make([]int, n) left, right := 1, 1 for i, v := range nums { ans[i] = left left *= v } for i := n - 1; i >= 0; i-- { ans[i] *= right right *= nums[i] } return ans }
-
function productExceptSelf(nums: number[]): number[] { const n = nums.length; let ans = new Array(n); for (let i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (let i = n - 1, right = 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; }
-
/** * @param {number[]} nums * @return {number[]} */ var productExceptSelf = function (nums) { const n = nums.length; let ans = new Array(n); for (let i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (let i = n - 1, right = 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; };
-
impl Solution { pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> { let mut dp_left = vec![1_i32; nums.len()]; let mut dp_right = vec![1_i32; nums.len()]; for i in 1..nums.len() { dp_left[i] = dp_left[i - 1] * nums[i - 1]; } for i in (0..(nums.len() - 1)).rev() { dp_right[i] = dp_right[i + 1] * nums[i + 1]; } dp_left .into_iter() .enumerate() .map(|(i, x)| x * dp_right[i]) .collect() } }
-
public class Solution { public int[] ProductExceptSelf(int[] nums) { int n = nums.Length; int[] ans = new int[n]; for (int i = 0, left = 1; i < n; ++i) { ans[i] = left; left *= nums[i]; } for (int i = n - 1, right = 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; } }