Product of Array Except Self

Product of Array Except Self has a sneaky rule. You are not allowed to use division. That one rule makes a simple question interesting. The interviewer wants to see if you can build the answer from two passes instead of one easy divide. It is a clever pattern worth knowing.

🎯 The Problem

You get an array of numbers and you must build a new array of products. Here are the rules.

• For each position, return the product of every other number in the array.
• The number at that position is left out. You multiply all the rest together.
• You must solve it without using the division operator.

Let us say the array is [1, 2, 3, 4]. For position 0, you multiply 2 * 3 * 4, which gives 24. For position 1, you multiply 1 * 3 * 4, which gives 12. And so on. The product of all numbers to the left of a position is called the prefix product. It is everything before that spot multiplied together.

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Explanation:
  index 0: 2*3*4 = 24
  index 1: 1*3*4 = 12
  index 2: 1*2*4 = 8
  index 3: 1*2*3 = 6

The catch is the rule. No division. So you cannot just multiply everything and divide out each number.

Here is the idea in a picture. Each answer is the product of everything on its left times everything on its right.

🐢 Approach 1: Rescan For Every Index (Brute Force)

The idea in one line: for each position, loop over the whole array again and multiply all the others.

The idea:

• One loop fixes the output position.
• A second loop walks every number.
• Skip the current index and multiply the rest.
• Store that product as the answer for that position.

Why it is weak:

• For every position you scan the whole array again.
• Two nested loops over n items means about n times n steps.
• So it is O(n²) time. Fine for a few numbers, slow on a big array.

Here is the brute-force code for that idea:

def product_except_self(nums):
    answer = []

    for skip in range(len(nums)):
        product = 1
        for i, num in enumerate(nums):
            if i != skip:
                product *= num
        answer.append(product)

    return answer


print(product_except_self([1, 2, 3, 4]))

➗ Approach 2: Total Product Then Divide (Banned Alternative)

The idea in one line: multiply everything once, then divide out each number.

The idea:

• Multiply every number together to get one big total.
• For each position, divide the total by the number there.
• The result is the product of all the others.

Why it is banned:

• The problem forbids division on purpose.
• It also breaks when any number is 0. Dividing by zero fails.
• So even outside this rule, the divide trick is risky.

Here is the division-based code for that idea:

def product_except_self(nums):
    zero_count = nums.count(0)

    if zero_count > 1:
        return [0] * len(nums)

    product = 1
    for num in nums:
        if num != 0:
            product *= num

    if zero_count == 1:
        return [product if num == 0 else 0 for num in nums]

    return [product // num for num in nums]


print(product_except_self([1, 2, 3, 4]))

⚡ Approach 3: Prefix and Suffix Products (Best)

The idea in one line: each answer is everything on its left multiplied by everything on its right.

The two parts:

• The left part is the prefix product.
• The right part is the suffix product, everything after that spot multiplied together.

How it works:

• Walk left to right. Keep a running product of everything seen before each spot. Store it in the output. Now each slot holds its prefix product.
• Walk right to left. Keep a running product of everything seen after each spot. Multiply it into the stored value.
• Now each slot holds prefix times suffix, which is the answer.

Why it is fast:

• Two simple passes, no division.
• Each number is touched a fixed number of times. So it is O(n).
• The output array holds the result, so the extra memory is O(1) beyond the output.

Here is a dry-run on [1, 2, 3, 4]. We build prefixes first, then fold in the suffixes.

Steps to Solve

1. Create an output array the same size as the input.
2. Walk left to right. Keep a running prefix product that starts at 1. Store it in the output slot, then multiply the current number into the running product.
3. Now each output slot holds the product of everything to its left.
4. Walk right to left. Keep a running suffix product that starts at 1. Multiply it into the output slot, then multiply the current number into the running product.
5. Now each output slot holds prefix times suffix, which is the final answer.
6. Return the output array.

#include <stdio.h>

void productExceptSelf(int nums[], int n, int output[]) {
    int prefix = 1;
    for (int i = 0; i < n; i++) {
        output[i] = prefix;     // product of everything to the left
        prefix *= nums[i];      // grow the running prefix
    }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        output[i] *= suffix;    // fold in product to the right
        suffix *= nums[i];      // grow the running suffix
    }
}

int main(void) {
    int nums[] = {1, 2, 3, 4};
    int n = 4;
    int output[4];
    productExceptSelf(nums, n, output);
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", output[i]);
        if (i < n - 1) printf(", ");
    }
    printf("]\n");
    return 0;
}

[24, 12, 8, 6]

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> output(n);
    int prefix = 1;
    for (int i = 0; i < n; i++) {
        output[i] = prefix;     // product of everything to the left
        prefix *= nums[i];      // grow the running prefix
    }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        output[i] *= suffix;    // fold in product to the right
        suffix *= nums[i];      // grow the running suffix
    }
    return output;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> result = productExceptSelf(nums);
    cout << "[";
    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i < (int)result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[24, 12, 8, 6]

import java.util.Arrays;

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] output = new int[n];
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            output[i] = prefix;     // product of everything to the left
            prefix *= nums[i];      // grow the running prefix
        }
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            output[i] *= suffix;    // fold in product to the right
            suffix *= nums[i];      // grow the running suffix
        }
        return output;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 4 };
        System.out.println(Arrays.toString(productExceptSelf(nums)));
    }
}

[24, 12, 8, 6]

def product_except_self(nums):
    n = len(nums)
    output = [1] * n            # start every slot at 1
    prefix = 1
    for i in range(n):
        output[i] = prefix      # product of everything to the left
        prefix *= nums[i]       # grow the running prefix
    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix     # fold in product to the right
        suffix *= nums[i]       # grow the running suffix
    return output


nums = [1, 2, 3, 4]
print(product_except_self(nums))

[24, 12, 8, 6]

function productExceptSelf(nums) {
  const n = nums.length;
  const output = new Array(n).fill(1); // start every slot at 1
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    output[i] = prefix;   // product of everything to the left
    prefix *= nums[i];    // grow the running prefix
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    output[i] *= suffix;  // fold in product to the right
    suffix *= nums[i];    // grow the running suffix
  }
  return output;
}

const nums = [1, 2, 3, 4];
console.log(productExceptSelf(nums));

[ 24, 12, 8, 6 ]

Let us read the Python version line by line and explain why each line is there.

def product_except_self(nums):
    n = len(nums)
    output = [1] * n
    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]
    return output

The line output = [1] * n makes an output list the same size as the input, filled with 1. We use 1 because 1 is safe to multiply by. It does not change a product.

The line prefix = 1 starts the running prefix at 1. The first position has nothing to its left. So its prefix product is 1.

In the first loop, output[i] = prefix stores the product of everything to the left of i. We store it before multiplying the current number, so the current number is correctly left out.

The line prefix *= nums[i] then grows the running product to include the current number. So the next position picks up the right left-side product.

The line suffix = 1 starts the running suffix at 1. The last position has nothing to its right. So its suffix product is 1.

In the second loop, output[i] *= suffix multiplies the right-side product into the prefix already stored. Now the slot holds left product times right product. That is the answer.

The line suffix *= nums[i] grows the suffix to include the current number, ready for the next position to the left.

The final return output gives back the finished array. No division was used anywhere.

⏱️ Time and Space Complexity

The brute force scans the array for every position, so it is slow. The division trick is fast but is banned and breaks on zeros. The prefix-and-suffix method runs two simple passes and uses no division. So it is the clean winner. That gives O(n) time, and O(1) extra space if you do not count the output array.

🧩 Key Takeaways

• ✅ Each answer is the product of everything to the left times everything to the right.
• ✅ Build prefix products in a forward pass, then fold in suffix products in a backward pass.
• ✅ Filling the output with 1 first is safe because 1 never changes a product.
• ✅ Store the prefix before multiplying the current number, so each number leaves itself out.
• ✅ No division means it stays correct even when the array has a zero.

🚀 What’s Next?

• Maximum Product Subarray
• Two Sum