Product of Array Except Self

medium
Arrays & HashingArray

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

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operator.

Examples

Example 1

  • Input: nums = [1,2,3,4]
  • Output: [24,12,8,6]
  • Explanation: For index 0 the product of all other elements is 234 = 24, for index 1 it is 134 = 12, and so on.

Example 2

  • Input: nums = [-1,1,0,-3,3]
  • Output: [0,0,9,0,0]

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

For each element in the array, compute the product of every other element by iterating through the entire array and skipping the current index. This is the most direct approach: for every position i, multiply all elements except the one at i. While simple, this requires a nested loop and results in quadratic time complexity.

Algorithm

  1. Create a result array of the same length as the input.
  2. For each index i, iterate through the array and multiply all elements where the index is not equal to i.
  3. Store the computed product in result[i].
  4. Return the result array.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    result[i] *= nums[j];
                }
            }
        }
        return result;
    }
};
Java 21
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    result[i] *= nums[j];
                }
            }
        }
        return result;
    }
}
Python 3.12
def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
    for i in range(n):
        for j in range(n):
            if i != j:
                result[i] *= nums[j]
    return result
Go 1.26
func productExceptSelf(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := 0; i < n; i++ {
        result[i] = 1
        for j := 0; j < n; j++ {
            if i != j {
                result[i] *= nums[j]
            }
        }
    }
    return result
}
Approach 2

Prefix and Suffix Products

Intuition

The key insight is that the product of all elements except the one at index i equals the product of all elements to its left multiplied by the product of all elements to its right. We can precompute prefix products (left-to-right running products) and suffix products (right-to-left running products) in two separate passes. Then the answer for each index is simply prefix[i] * suffix[i]. This avoids division entirely and runs in linear time.

Algorithm

  1. Create a result array and initialize all values to 1.
  2. Traverse left to right, maintaining a running product of all elements seen so far. Store this prefix product in the result array.
  3. Traverse right to left, maintaining a running product of all elements seen so far. Multiply the existing result value by this suffix product.
  4. Return the result array.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, 1);

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

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

        return result;
    }
};
Java 21
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

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

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

        return result;
    }
}
Python 3.12
def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n

    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

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

    prefix := 1
    for i := 0; i < n; i++ {
        result[i] = prefix
        prefix *= nums[i]
    }

    suffix := 1
    for i := n - 1; i >= 0; i-- {
        result[i] *= suffix
        suffix *= nums[i]
    }

    return result
}

Frequently asked questions

What is the optimal time complexity of Product of Array Except Self?

The most efficient approach in this guide ("Prefix and Suffix Products") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Product of Array Except Self use?

Product of Array Except Self is a medium-level Arrays & Hashing problem involving Array. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Product of Array Except Self be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[1,2,3,4]
Expected Output
[24,12,8,6]