Product Of Array Except Self

                                            
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> output(n, 1);
        
        int leftProduct = 1;
        for (int i = 0; i < n; i++) {
            output[i] *= leftProduct;
            leftProduct *= nums[i];
        }
        
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            output[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return output;
    }
};

                                            
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] output = new int[n];
        int leftProduct = 1;
        for (int i = 0; i < n; i++) {
            output[i] = leftProduct;
            leftProduct *= nums[i];
        }
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            output[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        return output;
    }
}

                                            
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        output = [1] * n
        left = 1
        right = 1
        
        for i in range(n):
            output[i] *= left
            left *= nums[i]
        
        for i in range(n-1, -1, -1):
            output[i] *= right
            right *= nums[i]
        
        return output

                                            
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    if(nums == NULL || numsSize == 0) {
        *returnSize = 0;
        return result;
    }
    
    int* left = (int*)malloc(numsSize * sizeof(int));
    int* right = (int*)malloc(numsSize * sizeof(int));
    
    left[0] = 1;
    right[numsSize - 1] = 1;
    
    for(int i = 1; i < numsSize; i++) {
        left[i] = left[i - 1] * nums[i - 1];
    }
    
    for(int i = numsSize - 2; i >= 0; i--) {
        right[i] = right[i + 1] * nums[i + 1];
    }
    
    for(int i = 0; i < numsSize; i++) {
        result[i] = left[i] * right[i];
    }
    
    *returnSize = numsSize;
    
    free(left);
    free(right);
    
    return result;
}

                                            
public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
        
        return result;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const n = nums.length;
    const output = new Array(n).fill(1);
    
    let leftProduct = 1;
    for (let i = 0; i < n; i++) {
        output[i] *= leftProduct;
        leftProduct *= nums[i];
    }
    
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        output[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return output;
};

                                            
function productExceptSelf(nums: number[]): number[] 
{
    const n = nums.length;
    const output: number[] = [];
    
    let leftProduct = 1;
    for (let i = 0; i < n; i++) {
        output[i] = leftProduct;
        leftProduct *= nums[i];
    }
    
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        output[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    
    return output;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function productExceptSelf($nums) {
        $n = count($nums);
        $output = array_fill(0, $n, 1);
        
        $leftProduct = 1;
        for ($i = 0; $i < $n; $i++) {
            $output[$i] *= $leftProduct;
            $leftProduct *= $nums[$i];
        }
        
        $rightProduct = 1;
        for ($i = $n - 1; $i >= 0; $i--) {
            $output[$i] *= $rightProduct;
            $rightProduct *= $nums[$i];
        }
        
        return $output;
    }
}

                                            
class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        var output = [Int](repeating: 1, count: nums.count)
        
        var leftProduct = 1
        for i in 0..<nums.count {
            output[i] *= leftProduct
            leftProduct *= nums[i]
        }
        
        var rightProduct = 1
        for i in stride(from: nums.count - 1, through: 0, by: -1) {
            output[i] *= rightProduct
            rightProduct *= nums[i]
        }
        
        return output
    }
}

                                            
class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        val n = nums.size
        val output = IntArray(n) { 1 }
        
        var leftProduct = 1
        for (i in 0 until n) {
            output[i] *= leftProduct
            leftProduct *= nums[i]
        }
        
        var rightProduct = 1
        for (i in n - 1 downTo 0) {
            output[i] *= rightProduct
            rightProduct *= nums[i]
        }
        
        return output
    }
}

                                            
class Solution {
  List<int> productExceptSelf(List<int> nums) {
    int n = nums.length;
    List<int> output = List.filled(n, 1);

    int leftProduct = 1;
    for (int i = 0; i < n; i++) {
      output[i] *= leftProduct;
      leftProduct *= nums[i];
    }

    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
      output[i] *= rightProduct;
      rightProduct *= nums[i];
    }

    return output;
  }
}

                                            
func productExceptSelf(nums []int) []int {
    n := len(nums)
    result := make([]int, n)

    // Calculate the product of all elements to the left of each element
    leftProduct := 1
    for i := 0; i < n; i++ {
        result[i] = leftProduct
        leftProduct *= nums[i]
    }

    // Calculate the product of all elements to the right of each element
    rightProduct := 1
    for i := n - 1; i >= 0; i-- {
        result[i] *= rightProduct
        rightProduct *= nums[i]
    }

    return result
}

                                            
# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
    n = nums.length
    result = Array.new(n, 1)
    
    left_product = 1
    (0...n).each do |i|
        result[i] *= left_product
        left_product *= nums[i]
    end
    
    right_product = 1
    (n-1).downto(0).each do |i|
        result[i] *= right_product
        right_product *= nums[i]
    end
    
    return result
end

                                            
object Solution {
    def productExceptSelf(nums: Array[Int]): Array[Int] = {
        val n = nums.length
        val result = new Array[Int](n)
        
        var productLeft = 1
        for (i <- 0 until n) {
            result(i) = productLeft
            productLeft *= nums(i)
        }
        
        var productRight = 1
        for (i <- n - 1 to 0 by -1) {
            result(i) *= productRight
            productRight *= nums(i)
        }
        
        result
    }
}

                                            
impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut output = vec![1; n];
        
        let mut left_product = 1;
        for i in 0..n {
            output[i] *= left_product;
            left_product *= nums[i];
        }
        
        let mut right_product = 1;
        for i in (0..n).rev() {
            output[i] *= right_product;
            right_product *= nums[i];
        }
        
        output
    }
}

To solve this coding challenge, the goal is to create an array

answer

where each element

answer[i]

is the product of all elements in the input array

nums

except

nums[i]

. The computation should be efficient, done in O(n) time complexity, and should not use division. Below, the plan will be comprehensively explained before presenting the pseudocode solution.

Explanation

Problem Analysis

Given an integer array

nums

, the challenge is to compute an array

answer

such that, for each index

i

answer[i]

is equal to the product of all elements of

nums

except

nums[i]

. Using division would make the problem straightforward (compute the total product of the array and divide by each element), but as division is not allowed, we need to find an alternative approach.

Approach

To solve this problem without division and in O(n) time complexity, a two-pass strategy can be employed:

First Pass (Left Products): Traverse the array from left to right. For each element at index
i

, compute the product of all the elements to the left of
i

.
Second Pass (Right Products): Traverse the array from right to left. For each element at index
i

, compute the product of all the elements to the right of
i

.

During each pass, maintain running products that will store intermediate results. By the end of the two passes, multiplicatively combine the results from left and right passes to get the final array of products.

Step-by-Step Explanation:

Initialization:

Create an output array
answer

initialized with 1s. This array will eventually store our result.
Initialize
left_product

to
1

. This variable keeps track of the product of all elements to the left of the current index during the first pass.
Initialize
right_product

to
1

. This variable keeps track of the product of all elements to the right of the current index during the second pass.

First Pass (Left to Right):

For each index
i

from
0

to
n-1

(where
n

is the length of the input array), set
answer[i]

to
left_product

.
Update
left_product

by multiplying it with
nums[i]

.

Second Pass (Right to Left):

For each index
i

from
n-1

to
0

, multiply
answer[i]

by
right_product

.
Update
right_product

by multiplying it with
nums[i]

.

By combining the products of elements to the left and right at each index, we can achieve the desired result in O(n) time and O(1) space (ignoring the space used for the output array).

Step-by-Step Pseudocode

Below is the pseudocode detailed with comments:

Initialization

                                            
function productExceptSelf(nums):
    # Step 1: Initialize variables
    n = length(nums)  # Get the length of input array
    answer = array of size n initialized with 1s  # The resulting array
    
    left_product = 1  # Initialize left product tracker
    right_product = 1  # Initialize right product tracker

First Pass: Compute Left Products

                                            
    # Step 2: Traverse the array from left to right
    for i = 0 to n-1:
        answer[i] = left_product  # Assign current left product to answer array
        left_product = left_product * nums[i]  # Update left product

Second Pass: Compute Right Products

                                            
    # Step 3: Traverse the array from right to left
    for i = n-1 to 0:
        answer[i] = answer[i] * right_product  # Multiply current right product with corresponding value in answer array
        right_product = right_product * nums[i]  # Update right product

Return the Result

                                            
    # Step 4: Return the computed result array
    return answer

Summarizing, we have developed an efficient method to solve the given coding challenge by breaking the problem down into parts and using a two-pass approach to compute the required product except self array, adhering to the constraints provided. This approach ensures linear time complexity and constant space complexity (excluding the output array).