Skip to main content
CodePeetCodePeet
CodePeet 250

Product of Array Except Self

MEDIUMProblemSolveExternal Links

Description

Given an integer array nums, return an array answer where 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 operation.

The restriction against division is critical — it means you cannot simply compute the total product and divide by each element. You need a different strategy entirely.

Examples

Example 1

Input: nums = [1, 2, 3, 4]

Output: [24, 12, 8, 6]

Explanation:

  • answer[0] = 2 × 3 × 4 = 24 (product of all elements except nums[0]=1)
  • answer[1] = 1 × 3 × 4 = 12 (product of all elements except nums[1]=2)
  • answer[2] = 1 × 2 × 4 = 8 (product of all elements except nums[2]=3)
  • answer[3] = 1 × 2 × 3 = 6 (product of all elements except nums[3]=4)

Example 2

Input: nums = [-1, 1, 0, -3, 3]

Output: [0, 0, 9, 0, 0]

Explanation:

  • answer[0] = 1 × 0 × (-3) × 3 = 0 (the zero in the array makes this product 0)
  • answer[1] = (-1) × 0 × (-3) × 3 = 0
  • answer[2] = (-1) × 1 × (-3) × 3 = 9 (excluding the zero gives a non-zero product)
  • answer[3] = (-1) × 1 × 0 × 3 = 0
  • answer[4] = (-1) × 1 × 0 × (-3) = 0

Notice that only answer[2] is non-zero because index 2 is where the zero element lives — excluding it removes the only zero from the product.

Example 3

Input: nums = [2, 3]

Output: [3, 2]

Explanation:

  • answer[0] = 3 (only element besides nums[0])
  • answer[1] = 2 (only element besides nums[1])

With just two elements, each answer is simply the other element.

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
  • You must not use the division operation

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is exactly how you would do it by hand: for each position in the array, multiply together every other element.

Imagine you have a row of cards with numbers on them. To find the answer for card 0, you flip it face down and multiply all the remaining visible cards together. Then you flip card 0 back up, flip card 1 face down, and multiply all the visible cards again. You repeat this for every card.

For each of the n positions, you iterate through all other n-1 elements and compute their product. This gives you the correct result but involves a lot of repeated work — you're recomputing products from scratch for each position.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4]:

Step 1: Compute answer[0]. Multiply all elements except nums[0].

  • product = 1 (start with identity)
  • j=1: product = 1 × 2 = 2
  • j=2: product = 2 × 3 = 6
  • j=3: product = 6 × 4 = 24
  • answer[0] = 24

Step 2: Compute answer[1]. Multiply all elements except nums[1].

  • product = 1
  • j=0: product = 1 × 1 = 1
  • j=2: product = 1 × 3 = 3
  • j=3: product = 3 × 4 = 12
  • answer[1] = 12

Step 3: Compute answer[2]. Multiply all elements except nums[2].

  • product = 1
  • j=0: product = 1 × 1 = 1
  • j=1: product = 1 × 2 = 2
  • j=3: product = 2 × 4 = 8
  • answer[2] = 8

Step 4: Compute answer[3]. Multiply all elements except nums[3].

  • product = 1
  • j=0: product = 1 × 1 = 1
  • j=1: product = 1 × 2 = 2
  • j=2: product = 2 × 3 = 6
  • answer[3] = 6

Result: answer = [24, 12, 8, 6]

Brute Force — Computing Product for Each Position — Watch how for each index i, we scan through the entire array multiplying every element except nums[i], repeating work across iterations.

Algorithm

  1. Create a result array answer of the same size as nums.
  2. For each index i from 0 to n-1:
    a. Initialize product = 1.
    b. For each index j from 0 to n-1:
    • If j ≠ i, multiply product by nums[j].
      c. Set answer[i] = product.
  3. Return answer.

Code

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

        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    product *= nums[j];
                }
            }
            answer[i] = product;
        }
        return answer;
    }
};
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [1] * n

        for i in range(n):
            product = 1
            for j in range(n):
                if j != i:
                    product *= nums[j]
            answer[i] = product

        return answer
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    product *= nums[j];
                }
            }
            answer[i] = product;
        }
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, we iterate through all n-1 other elements to compute the product. This gives n × (n-1) = O(n²) multiplications. With n up to 10^5, this means up to 10^10 operations — far too slow.

Space Complexity: O(1)

Beyond the output array answer (which doesn't count as extra space per the problem statement), we only use the product variable. No auxiliary data structures.

Why This Approach Is Not Efficient

The brute force runs in O(n²) time. With n up to 10^5, that's approximately 10^10 operations, which would take tens of seconds — well beyond typical time limits.

The fundamental problem is redundant computation. When computing answer[0] = 2×3×4 and then answer[1] = 1×3×4, we multiply 3×4 in both computations. Almost all of the work overlaps between iterations.

Key insight: the product of all elements except nums[i] can be decomposed as:

answer[i] = (product of everything to the LEFT of i) × (product of everything to the RIGHT of i)

If we precompute all left products (prefix products) and all right products (suffix products), we can combine them in O(1) per position. Building each prefix/suffix array takes O(n), so the total work becomes O(n).

Better Approach - Prefix and Suffix Products

Intuition

Instead of recomputing the product from scratch for each position, we can split the problem into two halves.

For any index i, the product of all elements except nums[i] equals:

  • The product of all elements before index i (the prefix product)
  • Multiplied by the product of all elements after index i (the suffix product)

Think of it like a fence with posts. To know the total length of fence on both sides of post i, you measure the fence to its left and the fence to its right, then add them. You don't need to remeasure the entire fence each time — you just need two running measurements.

We build two arrays:

  • prefix[i] = product of nums[0] × nums[1] × ... × nums[i-1] (everything before i)
  • suffix[i] = product of nums[i+1] × nums[i+2] × ... × nums[n-1] (everything after i)

Then answer[i] = prefix[i] × suffix[i].

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4]:

Phase 1: Build prefix array (left to right)

Step 1: prefix[0] = 1 (nothing to the left of index 0)
Step 2: prefix[1] = prefix[0] × nums[0] = 1 × 1 = 1
Step 3: prefix[2] = prefix[1] × nums[1] = 1 × 2 = 2
Step 4: prefix[3] = prefix[2] × nums[2] = 2 × 3 = 6

prefix = [1, 1, 2, 6]

Phase 2: Build suffix array (right to left)

Step 5: suffix[3] = 1 (nothing to the right of index 3)
Step 6: suffix[2] = suffix[3] × nums[3] = 1 × 4 = 4
Step 7: suffix[1] = suffix[2] × nums[2] = 4 × 3 = 12
Step 8: suffix[0] = suffix[1] × nums[1] = 12 × 2 = 24

suffix = [24, 12, 4, 1]

Phase 3: Combine

Step 9: answer[0] = prefix[0] × suffix[0] = 1 × 24 = 24
Step 10: answer[1] = prefix[1] × suffix[1] = 1 × 12 = 12
Step 11: answer[2] = prefix[2] × suffix[2] = 2 × 4 = 8
Step 12: answer[3] = prefix[3] × suffix[3] = 6 × 1 = 6

answer = [24, 12, 8, 6]

Prefix & Suffix Products — Building Two Arrays Then Combining — Watch how we build a prefix product array (left to right) and a suffix product array (right to left), then multiply them element-wise to get each answer in O(1).

Algorithm

  1. Create a prefix array of size n. Set prefix[0] = 1.
  2. Fill prefix left-to-right: prefix[i] = prefix[i-1] × nums[i-1].
  3. Create a suffix array of size n. Set suffix[n-1] = 1.
  4. Fill suffix right-to-left: suffix[i] = suffix[i+1] × nums[i+1].
  5. Create the answer: answer[i] = prefix[i] × suffix[i].
  6. Return answer.

Code

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n), suffix(n), answer(n);

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

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

        for (int i = 0; i < n; i++) {
            answer[i] = prefix[i] * suffix[i];
        }
        return answer;
    }
};
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        prefix = [1] * n
        suffix = [1] * n

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

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

        answer = [prefix[i] * suffix[i] for i in range(n)]
        return answer
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        int[] answer = new int[n];

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

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

        for (int i = 0; i < n; i++) {
            answer[i] = prefix[i] * suffix[i];
        }
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make three passes through the array: one to build the prefix array, one to build the suffix array, and one to combine them. Each pass is O(n), so total time is O(3n) = O(n).

Space Complexity: O(n)

We use two additional arrays (prefix and suffix), each of size n. Combined with the output array, the extra space is O(n). Note: the problem states that the output array does not count as extra space, but the prefix and suffix arrays do.

Why This Approach Is Not Efficient

The prefix-suffix approach achieves O(n) time, which is optimal since we must look at every element at least once. However, it uses O(n) extra space for the prefix and suffix arrays.

The problem's follow-up challenge asks: can we do this in O(1) extra space? (The output array doesn't count.)

The key observation is that we don't actually need to store the full prefix and suffix arrays simultaneously. We can:

  1. First pass: build the prefix products directly into the answer array.
  2. Second pass: sweep right-to-left with a running suffix product, multiplying it into each answer cell as we go.

This eliminates the need for separate prefix and suffix arrays — the answer array serves double duty, and the suffix product is reduced to a single variable.

Optimal Approach - Single Output Array with Running Product

Intuition

We use the same decomposition — answer[i] = left product × right product — but we're clever about where we store things.

In the first pass (left to right), we fill the answer array with prefix products. At this point, answer[i] contains the product of all elements to the LEFT of index i.

In the second pass (right to left), we maintain a single running variable suffix_product that accumulates the product of elements to the RIGHT of the current index. We multiply this into answer[i] on the fly.

Imagine you're painting a fence from left to right, keeping a running count of paint used. Then you walk back right to left with a second can, multiplying in the other side's contribution as you go. At the end, each section of fence has the complete picture — and you only needed one extra paintbrush (variable) for the return trip.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4]:

Phase 1: Left-to-right pass (build prefix products into answer)

Step 1: answer[0] = 1 (nothing to the left of index 0)
Step 2: answer[1] = answer[0] × nums[0] = 1 × 1 = 1
Step 3: answer[2] = answer[1] × nums[1] = 1 × 2 = 2
Step 4: answer[3] = answer[2] × nums[2] = 2 × 3 = 6

After pass 1: answer = [1, 1, 2, 6] (these are prefix products)

Phase 2: Right-to-left pass (multiply in suffix products)

Step 5: Initialize suffix_product = 1.
Step 6: i=3: answer[3] = answer[3] × suffix_product = 6 × 1 = 6. Then suffix_product = suffix_product × nums[3] = 1 × 4 = 4.
Step 7: i=2: answer[2] = answer[2] × suffix_product = 2 × 4 = 8. Then suffix_product = 4 × 3 = 12.
Step 8: i=1: answer[1] = answer[1] × suffix_product = 1 × 12 = 12. Then suffix_product = 12 × 2 = 24.
Step 9: i=0: answer[0] = answer[0] × suffix_product = 1 × 24 = 24. Then suffix_product = 24 × 1 = 24.

Result: answer = [24, 12, 8, 6]

Optimal — Build Prefix In-Place, Then Sweep Suffix — Watch how we first fill the answer array with prefix products (left to right), then sweep back right to left multiplying in the suffix product using a single variable — achieving O(1) extra space.

Algorithm

  1. Create answer array of size n.
  2. Left-to-right pass: Fill answer with prefix products.
    • Set answer[0] = 1.
    • For i = 1 to n-1: answer[i] = answer[i-1] × nums[i-1].
  3. Right-to-left pass: Multiply in suffix products using a running variable.
    • Initialize suffix_product = 1.
    • For i = n-1 down to 0:
      • answer[i] = answer[i] × suffix_product
      • suffix_product = suffix_product × nums[i]
  4. Return answer.

Code

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n);

        // Left-to-right: fill with prefix products
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Right-to-left: multiply in suffix products
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffixProduct;
            suffixProduct *= nums[i];
        }

        return answer;
    }
};
class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [1] * n

        # Left-to-right: fill with prefix products
        for i in range(1, n):
            answer[i] = answer[i - 1] * nums[i - 1]

        # Right-to-left: multiply in suffix products
        suffix_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix_product
            suffix_product *= nums[i]

        return answer
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // Left-to-right: fill with prefix products
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Right-to-left: multiply in suffix products
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffixProduct;
            suffixProduct *= nums[i];
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make exactly two passes through the array. The left-to-right pass computes n prefix products in O(n). The right-to-left pass multiplies in n suffix products in O(n). Total: O(2n) = O(n). This is optimal because we must read every input element at least once.

Space Complexity: O(1) extra space

The output array answer is required by the problem and does not count as extra space. The only additional variable we use is suffix_product, which is a single integer — constant space. We eliminated the separate prefix and suffix arrays entirely by reusing the answer array for dual purpose.