Product of Array Except Self

12 May 2026 0 Likes

Problem Description

Given an integer array nums, return an array answer such that, answer[i] is equal to the product of all the elements of nums except nums[i].

You must write an algorithm that runs in O(n) time and without using the division operator.
Example 1:
Input: nums = [1,2,3,4]
 Output: [24,12,8,6]
Explanation:
For index 0 ā†’ 2 Ɨ 3 Ɨ 4 = 24
For index 1 ā†’ 1 Ɨ 3 Ɨ 4 = 12
For index 2 ā†’ 1 Ɨ 2 Ɨ 4 = 8
For index 3 ā†’ 1 Ɨ 2 Ɨ 3 = 6
Example 2:
Input: nums = [-1,1,0,-3,3]
 Output: [0,0,9,0,0]
Explanation:
For index 2, the product becomes:
(-1) Ɨ 1 Ɨ (-3) Ɨ 3 = 9

All other positions include the element 0, so their product becomes 0.
Example 3:
Input: nums = [2,3,4,5]
 Output: [60,40,30,24]
Explanation:
For each index, we multiply all remaining elements except the current element itself.

Constraints

The array contains at least 2 elements. The elements of the array may be positive, negative, or zero.

The solution must run in O(n) time complexity. Using the division operator is not allowed.

The output array should contain the product of all elements except the current index.

Understanding the Problem

The problem is asking us to calculate the product of all elements except the current element for every position in the array.

A simple way to understand the problem is by calculating the answer separately for every index. For example: nums = [1,2,3,4]

For index 0: 2 Ɨ 3 Ɨ 4 = 24
For index 1: 1 Ɨ 3 Ɨ 4 = 12
For index 2: 1 Ɨ 2 Ɨ 4 = 8
For index 3: 1 Ɨ 2 Ɨ 3 = 6

The final result becomes: [24,12,8,6]

The main challenge is to compute these products efficiently without using division and without repeatedly multiplying the same values again and again.

Hints

The first hint is to observe that for every index, the answer depends on:

Product of elements on the left
Product of elements on the right

Instead of recalculating products repeatedly, try storing intermediate results.

A useful observation is: answer[i] = leftProduct Ɨ rightProduct

where:
leftProduct ā†’ product of all elements before index i
rightProduct ā†’ product of all elements after index i

Think about how prefix products and suffix products can help achieve linear time complexity.

Solutions

BETTER

Prefix and Suffix Array Solution

This approach uses two additional arrays to store: Left products and Right products.

The left array stores the product of all elements appearing before the current index. The right array stores the product of all elements appearing after the current index.

For example: nums = [1,2,3,4]
Left products: [1,1,2,6]
Right products: [24,12,4,1]

Now for every index: result[i] = left[i] Ɨ right[i]

This avoids repeated multiplication operations and achieves much better efficiency than the brute-force solution.

The tradeoff is that extra arrays are used for storing intermediate computations.
public class B_ThreeExtraArrays {

    public int[] productExceptSelf(int[] nums) {

        int n = nums.length;

        int[] left = new int[n];
        int[] right = new int[n];
        int[] result = new int[n];

        left[0] = 1;

        for (int i = 1; i < n; i++) {

            left[i] = left[i - 1] * nums[i - 1];
        }

        right[n - 1] = 1;

        for (int i = n - 2; i >= 0; i--) {

            right[i] = right[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {

            result[i] = left[i] * right[i];
        }

        return result;
    }
}
class Solution:

    def productExceptSelf(self, nums):

        n = len(nums)

        left = [0] * n
        right = [0] * n
        result = [0] * n

        left[0] = 1

        for i in range(1, n):

            left[i] = left[i - 1] * nums[i - 1]

        right[n - 1] = 1

        for i in range(n - 2, -1, -1):

            right[i] = right[i + 1] * nums[i + 1]

        for i in range(n):

            result[i] = left[i] * right[i]

        return result
Time Complexity
O(n)
Space Complexity
O(n)
BRUTE FORCE

Nested Loop Product Calculation Solution

This approach calculates the product for every index separately using nested loops.

For each position i, we traverse the entire array again and multiply all elements except: nums[i]

For example: nums = [1,2,3,4]
For index 0: 2 Ɨ 3 Ɨ 4 = 24
For index 1: 1 Ɨ 3 Ɨ 4 = 12

This process is repeated for every index individually.

Although the logic is straightforward and easy to understand, many multiplication operations are repeated unnecessarily, making the solution inefficient for large arrays.
public class A_BruteForce {

    public int[] productExceptSelf(int[] nums) {

        int n = nums.length;

        int[] result = new int[n];

        for (int i = 0; i < n; i++) {

            int product = 1;

            for (int j = 0; j < n; j++) {

                if (i == j)
                    continue;

                product *= nums[j];

                if (product == 0)
                    break;
            }

            result[i] = product;
        }

        return result;
    }
}
class Solution:

    def productExceptSelf(self, nums):

        n = len(nums)

        result = [0] * n

        for i in range(n):

            product = 1

            for j in range(n):

                if i == j:
                    continue

                product *= nums[j]

                if product == 0:
                    break

            result[i] = product

        return result
Time Complexity
O(nĀ²)
Space Complexity
O(n)
OPTIMAL

Optimal Prefix and Suffix Product Solution

This approach optimizes space usage by storing prefix products directly inside the result array.

In the first pass, we calculate the prefix product for every index.

For example: nums = [1,2,3,4]
The result array becomes: [1,1,2,6], where each position stores the product of all elements appearing before that index.

In the second pass, we traverse the array from right to left while maintaining a running suffix product.

At every index: result[i] = prefixProduct Ɨ suffixProduct

This allows us to compute the final answer without using separate left and right arrays.
class Solution:

    def productExceptSelf(self, nums):

        n = len(nums)

        result = [0] * n

        result[0] = 1

        for i in range(1, n):

            result[i] = result[i - 1] * nums[i - 1]

        right_product = 1

        for i in range(n - 1, -1, -1):

            result[i] = result[i] * right_product

            right_product *= nums[i]

        return result
public class C_OneExtraArray {

    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 rightProduct = 1;

        for (int i = n - 1; i >= 0; i--) {

            result[i] = result[i] * rightProduct;

            rightProduct = rightProduct * nums[i];
        }

        return result;
    }
}
Time Complexity
O(n)
Space Complexity
O(n)

Conclusion

The Product of Array Except Self problem is an important interview problem that teaches efficient array processing using prefix products and suffix products.

The problem demonstrates how intermediate computations can be reused to avoid unnecessary repeated multiplication operations.

Mastering this problem helps build a strong understanding of array traversal, prefix-suffix techniques, and space optimization, which are commonly used in coding interviews and real-world systems.

šŸ’¬ Comments