Product of Array Except Self

Updated on 03 July, 2025
Product of Array Except Self header image

Problem Statement

In this challenge, you are provided with an integer array named nums. Your task is to create a new array called answer, where each element answer[i] is calculated as the product of all elements in nums excluding nums[i] itself. The crucial part of the requirement is that this has to be achieved without using the division operation, keeping the computational efficiency in mind with a target time complexity of O(n). The result must also fit within a 32-bit integer, ensuring computational feasibility for a broad range of input sizes.

Examples

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 input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Approach and Intuition

The main challenge here is calculating the product of all array elements except the current one for each array position, without the use of division, and in linear time. Here's how we can approach this:

  1. Use two arrays to store interim product values:

    • One array (left_products) where each element at index i holds the product of all the numbers to the left of index i in nums.
    • Another array (right_products) where each element at index i holds the product of all the numbers to the right of index i in nums.
  2. First, fill the left_products array:

    • Initialize left_products[0] to 1 because there are no numbers to the left of the first element.
    • For each subsequent index i, compute left_products[i] as left_products[i-1] * nums[i-1], propagating the product of all previous numbers from the left.
  3. Similarly, populate the right_products array:

    • Initialize right_products[n-1] (where n is the length of nums) to 1 because there are no numbers to the right of the last element.
    • Populate the array from right to left where right_products[i] is computed as right_products[i+1] * nums[i+1].
  4. Once these two arrays are filled, the answer for each index i can be directly calculated by multiplying left_products[i] and right_products[i].

  5. This approach uses additional storage for the left_products and right_products arrays but ensures that each element of the 'answer' array is computed in linear time by leveraging the precomputed products.

This method cleverly circumvents the need for direct division by employing the concept of prefix and suffix products, thus adhering to the problem's constraints and ensuring efficiency.

Solutions

  • C++
cpp
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> product(size);
    
        product[0] = 1;
        for (int i = 1; i < size; i++) {
            product[i] = nums[i - 1] * product[i - 1];
        }
    
        int rightProduct = 1;
        for (int i = size - 1; i >= 0; i--) {
            product[i] = product[i] * rightProduct;
            rightProduct *= nums[i];
        }
    
        return product;
    }
};

The solution provided computes the product of all elements of an array except for the element at each index without using division, which is optimized for time complexity.

  • First, initialize a vector product of the same size as the input nums array.
  • Set the first element of product to 1 since there are no elements to the left of the first element.
  • Use a forward loop starting from index 1 to precompute the product of all elements to the left of the current element and store it in product.
  • Initialize a variable rightProduct to 1 to store the product of elements to the right of the current index.
  • Iterate backwards over the nums array. Update each element in the product array by multiplying it with rightProduct. Update rightProduct with the product of the current element in nums.

This approach allows each element of the output array to be the product of all the other elements in the input array except the one at its own index using linear time complexity O(n), where n is the number of elements in the input array, and avoids the use of division.

  • Java
java
class Solution {
    
    public int[] calcProductExceptSelf(int[] numbers) {
        int n = numbers.length;
        int[] result = new int[n];
        result[0] = 1;
            
        for (int idx = 1; idx < n; idx++) {
            result[idx] = numbers[idx - 1] * result[idx - 1];
        }
    
        int rightProduct = 1;
        for (int idx = n - 1; idx >= 0; idx--) {
            result[idx] *= rightProduct;
            rightProduct *= numbers[idx];
        }
    
        return result;
    }
}

The problem "Product of Array Except Self" requires computing an output array where each element at index i is the product of all the input array's elements except the one at index i itself. Here is a clear and concise explanation of how the Java solution addresses this problem:

  • Start by defining a method called calcProductExceptSelf which accepts an integer array numbers.
  • Initialize the length n of the input array and declare an output array result of the same length, setting the first element to 1.
  • Use a forward loop to construct the result array where each result[idx] is computed as the product of all numbers to the left of idx. This is achieved by multiplying the previous product (result[idx-1]) with the previous number (numbers[idx-1]).
  • Initialize a variable rightProduct to 1 to capture the product of elements to the right of the current index when iterating backward through the array.
  • In the reverse loop, update each result[idx] by multiplying it with rightProduct and then update rightProduct to include the current number (numbers[idx]).
  • Finally, return the completed result array.

This approach leverages a combination of prefix and postfix product calculations, avoiding the use of division and ensuring linear time complexity. This method is efficient and robust for large datasets.

  • Python
python
class Solution:
    def productOfOthers(self, nums: List[int]) -> List[int]:
    
        n = len(nums)
        output = [0] * n
        output[0] = 1
    
        for j in range(1, n):
            output[j] = nums[j - 1] * output[j - 1]
    
        right_product = 1
        for j in reversed(range(n)):
            output[j] = output[j] * right_product
            right_product *= nums[j]
    
        return output

The Python3 solution involves creating a list output where each element is the product of all the elements of the input list nums except the element at the same index. This is achieved without using division, following these steps:

  1. Initialize an output list of the same length as nums, with the first element set to 1 (since there's no left element to multiply).
  2. Traverse the input list, accumulating the product of numbers to the left of the current element. Store this cumulative product in the corresponding index of the output list.
  3. Initialize a variable right_product to 1 to keep track of the product of elements to the right of the current element as the list is traversed in reverse order.
  4. Iterate over the nums list from the end to the beginning. For each element:
    • Multiply the current index of the output list by right_product.
    • Update right_product to be the product of right_product and the current element of the nums.

This method ensures that the output list comprehensively contains the product of all the other numbers except itself for each position, leveraging the accumulative products from both directions. This approach is efficient, bypassing the need for nested loops, thus operating within a linear time complexity.

Comments

No comments yet.