grid47 Exploring patterns and algorithms
Oct 14, 2024
6 min read
Solution to LeetCode 238: Product of Array Except Self Problem
Given an integer array, your task is to return an array where each element at index ‘i’ is the product of all the elements of the original array except the element at index ‘i’. You are not allowed to use division in your solution, and the algorithm must run in O(n) time.
Problem
Approach
Steps
Complexity
Input: You are given an integer array 'nums'. The array will contain at least two elements.
Example: Input: nums = [2,3,4,5]
Constraints:
• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Output: Return an array where each element is the product of all the numbers in the array except the one at that index.
Example: Output: [60, 40, 30, 24]
Constraints:
Goal: The goal is to compute the product of all the elements except the current element at each index.
Steps:
• Create an array to store the product of all elements except the current element.
• First, iterate through the array to calculate the prefix products (product of elements before the current element).
• Then, iterate from the end of the array to calculate the suffix products (product of elements after the current element).
• Multiply the prefix and suffix values for each index to get the desired result.
Goal: The array will have at least two elements, and the product values will fit within a 32-bit integer.
Steps:
Assumptions:
• The input array will always contain at least two elements.
• There will be no division operations used in the solution.
• Input: Input: nums = [2,3,4,5]
• Explanation: For this example, the product of all elements except the current one would be: [60, 40, 30, 24]. The output array is constructed by calculating the product of all numbers except the current one for each index.
• Input: Input: nums = [1,0,3,4]
• Explanation: Here, the output array will be: [0, 0, 0, 0]. This is because the product for each index excludes the element at that index, and the array contains zeros.
Approach: The optimal approach is to compute the result in two passes: one for the prefix products and one for the suffix products, and multiply the two results for each element.
Observations:
• We cannot use division to simplify the problem.
• To avoid using extra space for the prefix and suffix arrays, we can modify the result array in place.
• The result can be built in two phases: one for the prefix products and another for the suffix products.
Steps:
• Step 1: Create a result array initialized to 1.
• Step 2: Calculate the prefix product by iterating from left to right.
• Step 3: Update the result array by multiplying it with the suffix product, iterating from right to left.
Empty Inputs:
• The list is guaranteed to have at least two elements, so no empty list cases.
Large Inputs:
• The solution should efficiently handle large arrays with up to 100,000 elements.
Special Values:
• Handle cases where the array contains zeroes. The result array should correctly reflect the multiplication of other elements.
Constraints:
• Make sure the output array fits within a 32-bit integer range.
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> pre(n, 1), suf(n, 1);
pre[0] = nums[0];
suf[n -1] = nums[n -1];
for(int i =1; i < n; i++)
pre[i] = pre[i -1] * nums[i];
for(int i = n -2; i >=0; i--)
suf[i] = suf[i +1] * nums[i];
vector<int> ans(n, 1);
for(int i =0; i < n; i++)
ans[i] = (i >0? pre[i -1]:1) * (i < n -1? suf[i +1]:1);
return ans;
}
Defines the function `productExceptSelf`, which takes a reference to a vector of integers (`nums`) and returns a vector of integers where each element is the product of all other elements except for the current one.
2 : Size of Array
int n = nums.size();
Stores the size of the input array `nums` in variable `n`.
3 : Initialize Prefix and Suffix Arrays
vector<int> pre(n, 1), suf(n, 1);
Initializes two auxiliary arrays, `pre` and `suf`, both of size `n`. `pre[i]` will store the product of all elements to the left of index `i`, and `suf[i]` will store the product of all elements to the right of index `i`.
4 : Set First Prefix Value
pre[0] = nums[0];
Sets the first element of the `pre` array to be equal to the first element of the `nums` array.
5 : Set Last Suffix Value
suf[n -1] = nums[n -1];
Sets the last element of the `suf` array to be equal to the last element of the `nums` array.
6 : Prefix Product Calculation
for(int i =1; i < n; i++)
Starts a loop from the second element (`i = 1`) to the last element of the array, calculating the prefix product for each index.
7 : Update Prefix Product
pre[i] = pre[i -1] * nums[i];
Updates the `pre[i]` array by multiplying the previous element's prefix product (`pre[i - 1]`) by the current element (`nums[i]`). This ensures that `pre[i]` holds the product of all elements to the left of index `i`.
8 : Suffix Product Calculation
for(int i = n -2; i >=0; i--)
Starts a loop from the second-to-last element (`i = n - 2`) down to the first element, calculating the suffix product for each index.
9 : Update Suffix Product
suf[i] = suf[i +1] * nums[i];
Updates the `suf[i]` array by multiplying the next element's suffix product (`suf[i + 1]`) by the current element (`nums[i]`). This ensures that `suf[i]` holds the product of all elements to the right of index `i`.
10 : Initialize Answer Array
vector<int> ans(n, 1);
Initializes the result array `ans` of size `n` with all elements set to 1.
11 : Compute Final Results
for(int i =0; i < n; i++)
Starts a loop to calculate the final result for each index `i` in the `ans` array.
12 : Calculate Product for Each Index
ans[i] = (i >0? pre[i -1]:1) * (i < n -1? suf[i +1]:1);
For each index `i`, the result is calculated by multiplying the prefix product (`pre[i - 1]`) and the suffix product (`suf[i + 1]`). If `i` is the first or last index, the appropriate product (prefix or suffix) is taken as 1.
13 : Return Final Result
return ans;
Returns the result array `ans`, which contains the product of all elements in the input array `nums` except for the current element.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we iterate through the list twice.
Best Case: O(1)
Worst Case: O(1)
Description: We use only constant extra space as we update the result array in place.
