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].

1. Create a new array left of the same size as nums. Initialize left[0] to 1.
2. Iterate from 1 to n-1 and for each index i of nums, compute left[i] as nums[i-1] * left[i-1]. The value of left array after this operation would be [1, 1, 2, 6].
3. Create another new array right of the same size as nums. Initialize right[n-1] to 1.
4. Iterate from n-2 to 0 and for each index i of nums, compute right[i] as nums[i+1] * right[i+1]. The value of left array after this operation would be [24, 12, 4, 1].
5. Create the final output array output of the same size as nums.
6. Iterate from 0 to n-1 and for each index i of nums, compute output[i] as left[i] * right[i]. The value of output 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;
};

vector productExceptSelf(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; 
}