Solution For Product Of Array Except Self
Problem Statement:
Given an array nums
of n integers where n > 1, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
Example:
Input: [1,2,3,4] Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Solution:
To solve this problem, we can use two additional arrays to store the product of all elements to the left and right of the current element respectively. Then, we can simply multiply the corresponding elements of these two arrays to get the final result.
Let’s take the example of the input [1, 2, 3, 4].
Create a new array
left
of the same size asnums
. Initializeleft[0]
to 1.Iterate from 1 to n-1 and for each index i of nums, compute
left[i]
asnums[i-1] * left[i-1]
. The value ofleft
array after this operation would be [1, 1, 2, 6].Create another new array
right
of the same size asnums
. Initializeright[n-1]
to 1.Iterate from n-2 to 0 and for each index i of nums, compute
right[i]
asnums[i+1] * right[i+1]
. The value ofleft
array after this operation would be [24, 12, 4, 1].Create the final output array
output
of the same size asnums
.Iterate from 0 to n-1 and for each index i of nums, compute
output[i]
asleft[i] * right[i]
. The value ofoutput
array after this operation would be [24, 12, 8, 6].
Here’s the Python code for the solution:
def productExceptSelf(nums):
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(1, n):
left[i] = nums[i-1] * left[i-1]
for i in range(n-2, -1, -1):
right[i] = nums[i+1] * right[i+1]
output = [1] * n
for i in range(n):
output[i] = left[i] * right[i]
return output
Time Complexity:
The time complexity of the solution is O(n) as we are iterating through the input array three times, once for left
array, once for right
array, and once for calculating the output
array.
Step by Step Implementation For Product Of Array Except Self
public int[] productExceptSelf(int[] nums) { // The length of the input array int length = nums.length; // The left and right arrays have the product of the elements to the left and right of the index, respectively int[] left = new int[length]; int[] right = new int[length]; // Final answer array to be returned int[] answer = new int[length]; // First element of left array is always 1 left[0] = 1; // First element of right array is always 1 right[length - 1] = 1; // Construct the left array for (int i = 1; i < length; i++) { left[i] = nums[i - 1] * left[i - 1]; } // Construct the right array for (int j = length - 2; j >= 0; j--) { right[j] = nums[j + 1] * right[j + 1]; } // Construct the answer array for (int k = 0; k < length; k++) { answer[k] = left[k] * right[k]; } return answer; }
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # The length of the input array length = len(nums) # The answer array to be returned answer = [0]*length # answer[i] contains the product of all the elements to the left # Note: for the element at index '0', there are no elements to the left, # so the answer[0] would be 1 answer[0] = 1 for i in range(1, length): # answer[i - 1] already contains the product of elements to the left of 'i - 1' # Simply multiplying it with nums[i - 1] would give the product of all # elements to the left of index 'i' answer[i] = nums[i - 1] * answer[i - 1] # R contains the product of all the elements to the right # Note: for the element at index 'length - 1', there are no elements to the right, # so the R would be 1 R = 1; for i in reversed(range(length)): # For the index 'i', R would contain the # product of all elements to the right. We update R accordingly answer[i] = answer[i] * R R *= nums[i] return answer
/** * @param {number[]} nums * @return {number[]} */ var productExceptSelf = function(nums) { // create an empty array with same length as input array let output = new Array(nums.length); // fill the output array with 1's output.fill(1); // initialize two variables for tracking left side product and right side product let left = 1; let right = 1; // loop through input array from left to right for (let i = 0; i < nums.length; i++) { // at each iteration, update left side product and store it in output array output[i] = left; // update left side product for next iteration left *= nums[i]; } // loop through input array from right to left for (let j = nums.length - 1; j >= 0; j--) { // at each iteration, update right side product right *= nums[j]; // update output array with right side product output[j] *= right; } return output; };
vectorproductExceptSelf(vector & nums) { int n = nums.size(); vector res(n); int left = 1; for (int i = 0; i < n; ++i) { if (i > 0) left = left * nums[i - 1]; res[i] = left; } int right = 1; for (int i = n - 1; i >= 0; --i) { if (i < n - 1) right = right * nums[i + 1]; res[i] *= right; } return res; }
public int[] ProductExceptSelf(int[] nums) { // The length of the input array int length = nums.Length; // The left and right arrays have the product of all the elements to the left and right of the index, respectively int[] left = new int[length]; int[] right = new int[length]; // Final answer array to be returned int[] answer = new int[length]; // L[i] contains the product of all the elements to the left // Note: for the element at index '0', there are no elements to the left, so L[0] would be 1 left[0] = 1; for (int i = 1; i < length; i++) { left[i] = nums[i - 1] * left[i - 1]; } // R[i] contains the product of all the elements to the right // Note: for the element at index 'length - 1', there are no elements to the right, so R[length - 1] would be 1 right[length - 1] = 1; for (int i = length - 2; i >= 0; i--) { right[i] = nums[i + 1] * right[i + 1]; } // Constructing the answer array for (int i = 0; i < length; i++) { // For the first element, R[i] would be product except self // For the last element of the array, product except self would be L[i] // Else, multiple product of all elements to the left and to the right answer[i] = left[i] * right[i]; } return answer; }