Home Dsa Product of ...

Product of Array Except Self problem and solutions in Java and Python

The “Product of Array Except Self” problem is another classic interview favorite (commonly asked at FAANG), and it’s all about careful prefix/suffix computation without using division.

Let’s go step-by-step 👇

🧩 Problem Statement

Given an integer array nums, return an array output such that output[i] = product of all the elements of nums except nums[i].

You must write an algorithm that:

Runs in O(n) time
Does not use division
Uses O(1) extra space (excluding output array)

Example

Input:  nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation:
- output[0] = 2*3*4 = 24
- output[1] = 1*3*4 = 12
- output[2] = 1*2*4 = 8
- output[3] = 1*2*3 = 6

⚙️ 1. Brute Force Approach (O(n²))

For each element, multiply all others except itself.

❌ Inefficient (too slow for large arrays)

✅ Java:

public int[] productExceptSelfBrute(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

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

✅ Python:

def product_except_self_brute(nums):
    n = len(nums)
    res = []
    for i in range(n):
        prod = 1
        for j in range(n):
            if i != j:
                prod *= nums[j]
        res.append(prod)
    return res

🕒 Time: O(n²) 💾 Space: O(1)

⚡ 2. Optimized Approach — Prefix & Suffix Products (O(n) time, O(1) space)

💡 Key Idea

Each output[i] = → product of all elements before i (prefix) × product of all elements after i (suffix)

We can compute this in two passes:

Compute prefix products
Compute suffix products on the fly (without extra array)

✅ Java Solution (O(n), O(1))

public class ProductOfArrayExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

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

        // Step 2: suffix products (accumulate from right)
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] res = productExceptSelf(nums);
        for (int r : res) System.out.print(r + " ");
    }
}

Output:

24 12 8 6

✅ Python Solution (O(n), O(1))

def product_except_self(nums):
    n = len(nums)
    res = [1] * n

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

    # Step 2: suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]

    return res

# Example
nums = [1, 2, 3, 4]
print(product_except_self(nums))  # Output: [24, 12, 8, 6]

🧠 Dry Run Example

nums = [1, 2, 3, 4]
Prefix phase:
res = [1, 1, 2, 6]

Suffix phase:
suffix = 1 → res[3]=6*1=6
suffix=4
res[2]=2*4=8
suffix=12
res[1]=1*12=12
suffix=24
res[0]=1*24=24
Final res = [24,12,8,6]

🧭 Complexity

Step	Time	Space
Prefix pass	O(n)	O(1)
Suffix pass	O(n)	O(1)
✅ Total	O(n)	O(1)

⚙️ 3. Variant — Using Division (if allowed)

If the problem allows division and there are no zeros, you can simply take:

totalProduct = product of all elements
output[i] = totalProduct / nums[i]

But this fails if:

Any element = 0 (division by zero)
Problem explicitly bans division (as in LeetCode #238)

💬 Real-World Analogy

You have a production line with multiple machines. Each produces a certain number of units. You want to know how the line performs if each machine is excluded once. This algorithm efficiently calculates each scenario without re-running all multiplications.

🚀 Bonus Variation: Handle zeros

If array contains zeros:

If more than 1 zero → all outputs = 0
If exactly 1 zero → only index of zero = product of non-zero elements; rest = 0

✅ Python (handling zeros)

def product_except_self_with_zeros(nums):
    zero_count = nums.count(0)
    if zero_count > 1:
        return [0] * len(nums)
    total = 1
    for num in nums:
        if num != 0:
            total *= num
    res = []
    for num in nums:
        if num == 0:
            res.append(total)
        elif zero_count == 1:
            res.append(0)
        else:
            res.append(total // num)
    return res

✅ Summary

Approach	Time	Space	Handles Zeros	Uses Division
Brute Force	O(n²)	O(1)	✅	✅
Prefix + Suffix	O(n)	O(1)	✅	❌
Division	O(n)	O(1)	❌	✅

Here’s a visual step-by-step diagram to clearly show how the prefix + suffix (two-pass) method for the Product of Array Except Self works.

We’ll take the example:

nums = [1, 2, 3, 4]

🧩 Step 1 — Initialize Result Array

We start with:

res = [1, 1, 1, 1]   // all ones initially

🔹 Step 2 — Compute Prefix Products

We’ll build the prefix (product of all elements before index i).

Index	nums[i]	res[i] (prefix product so far)	Explanation
0	1	1	No elements before index 0
1	2	res[1] = res[0] * nums[0] = 1×1 = 1
2	3	res[2] = res[1] * nums[1] = 1×2 = 2
3	4	res[3] = res[2] * nums[2] = 2×3 = 6

✅ After prefix pass:

res = [1, 1, 2, 6]

🔸 Each element now holds product of all elements to its left.

🔹 Step 3 — Compute Suffix Products

We move from right to left, tracking a running suffix product (i.e., product of all elements after index i).

Initialize:

suffix = 1

Now iterate backward:

i	nums[i]	res[i] before	res[i] after (× suffix)	new suffix value
3	4	6	6×1 = 6	suffix = 1×4 = 4
2	3	2	2×4 = 8	suffix = 4×3 = 12
1	2	1	1×12 = 12	suffix = 12×2 = 24
0	1	1	1×24 = 24	suffix = 24×1 = 24

✅ Final res:

res = [24, 12, 8, 6]

🎯 Intuitive Visualization

nums: [ 1    2    3    4 ]

Prefix: [ 1   (1)  (1×2)  (1×2×3) ] = [1, 1, 2, 6]
Suffix: [ (2×3×4)  (3×4)  (4)  1 ]  = [24, 12, 4, 1]

Output = Prefix × Suffix
        = [1×24, 1×12, 2×4, 6×1]
        = [24, 12, 8, 6]