Product of Array Except Self

Java coding interview problem for Array Logic: Product of Array Except Self.

The Product of Array Except Self is one of the most frequently asked array problems in technical interviews.

This problem tests important concepts:

Prefix computation
Suffix computation
Space optimization
Handling zero values
Array manipulation
Mathematical reasoning

It is commonly asked in interviews at:

Google
Amazon
Microsoft
Meta
Netflix

What is Product of Array Except Self?

Given an integer array, return an array where each element contains the product of all elements except itself.

The result should be calculated:

Without using division.
In O(n) time.
Preferably with constant extra space.

Example 1

Input:

nums = [1,2,3,4]

For each position:

Index 0:

2 * 3 * 4 = 24

Index 1:

1 * 3 * 4 = 12

Index 2:

1 * 2 * 4 = 8

Index 3:

1 * 2 * 3 = 6

Output:

[24,12,8,6]

Example 2

Input:

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

Output:

[0,0,9,0,0]

Understanding the Problem

Given:

[1,2,3,4]

We need:

Index 0:

Product of:

2 × 3 × 4

Index 1:

Product of:

1 × 3 × 4

Index 2:

Product of:

1 × 2 × 4

Index 3:

Product of:

1 × 2 × 3

Final:

[24,12,8,6]

Why Is This Question Asked in Interviews?

This problem tests whether candidates understand:

1. Avoiding Brute Force

A direct solution requires:

O(n²)

time.

Interviewers expect:

O(n)

2. Prefix and Suffix Patterns

Many advanced problems use this pattern:

Range product
Range sum
Maximum product
Dynamic programming

3. Handling Edge Cases

Especially:

Zero values
Negative numbers
Large numbers

Real-World Applications

Database Analytics

Calculate total metrics excluding the current record.

Example:

Sales:

[10,20,30,40]

For each store:

Total sales of other stores

Machine Learning

Feature normalization:

Each feature can be compared against combined values of remaining features.

Distributed Systems

Aggregate information from all nodes except the current node.

Statistics

Calculate:

Combined values
Comparative metrics
Excluding current observation

Problem Statement

Given an integer array:

nums

return an array:

answer

where:

answer[i]

is equal to:

product of all elements except nums[i]

Constraints

Example:

2 <= nums.length <= 100000

Values:

-30 <= nums[i] <= 30

Rules

The solution should:

Not use division.
Run in O(n).
Handle zeros correctly.

Understanding Product Calculation

Example:

Input:

[1,2,3,4]

Total product:

1×2×3×4

Using division:

24 / 1 = 24

24 / 2 = 12

24 / 3 = 8

24 / 4 = 6

But division creates problems with zero values.

Therefore, interviewers usually prohibit division.

Handling Zero Values

Zeros make this problem interesting.

Example:

[1,2,0,4]

Without zero:

Product:

1×2×4 = 8

Only zero position gets:

Result:

[0,0,8,0]

Multiple zeros:

Example:

[0,2,0,4]

There is no valid product except zero.

Output:

[0,0,0,0]

Array Visualization

Input:

[1,2,3,4]

Prefix Products:

Before current element:

Suffix Products:

After current element:

Index:

0  1  2  3

24 12 4 1

Answer:

Prefix × Suffix

Formula

For every index:

answer[i]
=
left product
*
right product

Example:

Index 2:

Left:

1×2 = 2


Right:

4

Result:

2×4 = 8

Dry Run

Input:

[1,2,3,4]

Step 1

Create answer array:

[1,1,1,1]

Step 2

Calculate prefix products.

Index 0:

left product = 1

answer:

[1,1,1,1]

Index 1:

left product = 1

Index 2:

left product = 1×2

answer:

[1,1,2,1]

Index 3:

left product = 1×2×3

answer:

[1,1,2,6]

Step 3

Multiply suffix products.

From right:

Index 3:

suffix = 1

answer:

[1,1,2,6]

Index 2:

suffix = 4

answer:

[1,1,8,6]

Index 1:

suffix = 3×4

answer:

[1,12,8,6]

Index 0:

suffix = 2×3×4

answer:

[24,12,8,6]

Approach 1 — Brute Force Multiplication

The simplest approach:

For every index:

Multiply all other elements.
Store result.

Algorithm

For each element:

product = 1

Traverse array:

Skip current index.

Multiply remaining values.

Java Program

import java.util.Arrays;

public class ProductExceptSelfBruteForce {


    public static 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) {

                    product *= nums[j];

                }

            }


            result[i] = product;

        }


        return result;

    }


    public static void main(String[] args) {


        int[] nums =
                {1,2,3,4};


        System.out.println(
                Arrays.toString(
                    productExceptSelf(nums)));

    }

}

Output

[24,12,8,6]

Step-by-Step Explanation

Input:

[1,2,3,4]

Index 0:

Multiply:

2×3×4

Result:

Index 1:

Multiply:

1×3×4

Result:

Index 2:

Multiply:

1×2×4

Result:

Index 3:

Multiply:

1×2×3

Result:

Complexity Analysis

Time:

O(n²)

Space:

O(n)

Advantages

Very easy to understand.
Good beginner solution.
Handles zeros naturally.

Drawbacks

Too slow for large arrays.
Repeats calculations.
Not interview optimal.

Approach 2 — Prefix and Suffix Arrays

The optimized idea:

Instead of repeatedly calculating products,

store:

Product of all elements before index.
Product of all elements after index.

Prefix Example

Array:

[1,2,3,4]

Prefix:

[1,1,2,6]

Meaning:

prefix[2] = 1×2

Suffix Example

Suffix:

[24,12,4,1]

Meaning:

suffix[2] = 4

Formula

answer[i] =
prefix[i] * suffix[i]

Java Program

import java.util.Arrays;

public class ProductExceptSelfPrefixSuffix {


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


        int n = nums.length;


        int[] prefix =
                new int[n];


        int[] suffix =
                new int[n];


        int[] result =
                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++) {


            result[i] =
                prefix[i] *
                suffix[i];

        }


        return result;

    }

}

Complexity Analysis

Time:

O(n)

Space:

O(n)

Advantages

Linear time.
Easy to understand.
Handles zeros.
Interview acceptable.

Drawbacks

Uses extra arrays.
More memory usage.

Approach 3 — Optimized Prefix and Suffix Approach (Optimal)

The prefix and suffix approach uses:

prefix array

+

suffix array

It gives:

Time Complexity: O(n)

But requires:

O(n) extra space

The optimized approach removes the suffix array.

We reuse the result array to store prefix products.

Final complexity:

Time: O(n)

Space: O(1)

(Excluding the output array)

Core Idea

For every index:

answer[i]
=
product of elements before i
*
product of elements after i

We calculate:

Prefix product from left to right.
Suffix product from right to left.

Example

Input:

[1,2,3,4]

First Pass — Prefix Product

Store left products:

Index:

0   1   2   3

1   1   2   6

Meaning:

answer[3] = 1×2×3

Second Pass — Suffix Product

Traverse from right:

Initial:

suffix = 1

Multiply suffix with answer.

Index 3:

answer[3] = 6 × 1

Result:

Update suffix:

suffix = 4

Index 2:

answer[2] = 2 × 4

Result:

Update:

suffix = 12

Index 1:

answer[1] = 1 × 12

Result:

Index 0:

answer[0] = 1 × 24

Result:

Final:

[24,12,8,6]

Java Program

import java.util.Arrays;

public class ProductExceptSelfOptimized {


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


        int n = nums.length;


        int[] result =
                new int[n];


        // Store prefix products

        result[0] = 1;


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


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

        }


        // Calculate suffix product

        int suffix = 1;


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


            result[i] =
                    result[i] * suffix;


            suffix =
                    suffix * nums[i];

        }


        return result;

    }


    public static void main(String[] args) {


        int[] nums =
                {1,2,3,4};


        System.out.println(
                Arrays.toString(
                    productExceptSelf(nums)));

    }

}

Output

[24,12,8,6]

Step-by-Step Explanation

Input:

[1,2,3,4]

Step 1: Prefix Calculation

Initial:

result = [1,1,1,1]

After processing:

result =
[1,1,2,6]

Meaning:

result[i]
=
product before i

Step 2: Suffix Calculation

Start:

suffix = 1

Index 3:

result[3] = 6 * 1

= 6

Update:

suffix = 4

Index 2:

result[2] = 2 * 4

= 8

Update:

suffix = 12

Index 1:

result[1] = 1 * 12

= 12

Index 0:

result[0] = 1 * 24

= 24

Final Answer:

[24,12,8,6]

Complexity Analysis

Time:

O(n)

Because:

One left traversal.
One right traversal.

Space:

O(1)

Extra variables:

suffix

Only output array is used.

Advantages

Optimal solution.
No division.
Handles zeros.
Constant extra space.
Preferred interview solution.

Drawbacks

Requires understanding prefix and suffix pattern.

Mathematical Explanation

For an index i:

The complete product is:

nums[0] × nums[1] × ... × nums[n-1]

excluding:

nums[i]

becomes:

(nums[0]...nums[i-1])
*
(nums[i+1]...nums[n-1])

Therefore:

answer[i]
=
left product
*
right product

Division Approach (Why It Is Usually Avoided)

A simple idea:

Calculate:

total product

Then:

answer[i] =
total product / nums[i]

Example:

Input:

[1,2,3,4]

Total:

Results:

It looks simple.

But problems occur with zero.

Zero Case

Input:

[1,2,0,4]

Total product:

Division:

0 / 0

Invalid.

Multiple Zero Case

Input:

[0,2,0,4]

Total:

Need:

[0,0,0,0]

Division cannot handle this easily.

Java Streams Approach

A stream-based approach is possible but not recommended.

The reason:

Product except self requires maintaining state.

Example:

Arrays.stream(nums)

can easily calculate:

total product

but handling:

exclude current index

requires additional logic.

Stream Implementation

import java.util.Arrays;

public class ProductExceptSelfStreams {


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


        return Arrays.stream(nums)
                .map(index -> {

                    int product = 1;


                    for (int i = 0;
                         i < nums.length;
                         i++) {


                        if (i != index) {

                            product *= nums[i];

                        }

                    }


                    return product;

                })
                .toArray();

    }

}

Complexity Analysis

Time:

O(n²)

Space:

O(n)

Why Streams Are Not Ideal Here?

Streams improve readability, but:

They do not naturally express prefix/suffix state.
They create extra processing.
They are slower for algorithmic problems.

For interviews:

Prefer:

Loops + Prefix/Suffix

Comparison of All Approaches

Approach	Time Complexity	Space Complexity	Recommended
Brute Force	O(n²)	O(n)	Learning
Prefix + Suffix Arrays	O(n)	O(n)	Good
Optimized Prefix/Suffix	O(n)	O(1)	Best Interview Solution
Division	O(n)	O(1)	Avoid
Streams	O(n²)	O(n)	Not Recommended

Prefix Product Pattern Explanation

The prefix pattern appears frequently.

General idea:

Instead of recalculating:

everything before current index

store previous calculations.

Examples:

Prefix Sum
Prefix Maximum
Prefix Minimum
Prefix Product

Primitive vs Object Arrays

Primitive Array

Example:

int[]

Advantages:

Faster.
Less memory.
No boxing.

Recommended for:

Competitive programming.
Large datasets.

Object Array

Example:

Integer[]

Advantages:

Works with Collections.
Supports generic APIs.

Common Interview Mistakes

Mistake 1

Using division without discussing zero cases.

Mistake 2

Using nested loops.

Complexity:

O(n²)

Mistake 3

Creating both prefix and suffix arrays unnecessarily.

Mistake 4

Forgetting integer overflow.

Large products may exceed:

int

Use:

long

when required.

Edge Cases

Input	Output
`[1,2,3,4]`	`[24,12,8,6]`
`[0,1,2,3]`	`[6,0,0,0]`
`[0,0,2]`	`[0,0,0]`
`[-1,1,0,-3,3]`	`[0,0,9,0,0]`
Single element	Depends on constraints

Interview Follow-up Questions

Q1. Solve without division.

Q2. Solve in O(1) extra space.

Q3. Handle multiple zeros.

Q4. Find product except range.

Q5. Find maximum product subarray.

Q6. Use prefix product technique.

Q7. Explain why division fails.

Key Takeaways

The Product of Array Except Self problem teaches one of the most important interview patterns:

Prefix + Suffix

Evolution:

Brute Force
     ↓
Prefix + Suffix Arrays
     ↓
Optimized Prefix/Suffix

The optimal solution:

Time Complexity: O(n)

Space Complexity: O(1)

Core idea:

Store information from the left, then combine it with information from the right.

Frequently Asked Interview Questions

Q1. What is the optimal solution?

Prefix and suffix product approach.

Q2. Why not use division?

Because zero values create invalid division cases.

Q3. What pattern does this problem use?

Prefix and suffix computation.

Q4. Can this be solved in constant space?

Yes.

Use:

output array

+

one suffix variable

Q5. Where is this pattern useful?

Applications:

Range calculations
Analytics
Data processing
Optimization problems

Interview Tip

When asked:

"Product of Array Except Self."

Explain the progression:

Brute Force → O(n²)
Prefix/Suffix Arrays → O(n)
Optimized Prefix/Suffix → O(1) extra space

The final interview solution:

Prefix Product + Suffix Product

Time: O(n)

Space: O(1)

Understanding this pattern will help solve many advanced array and dynamic programming problems.

Product of Array Except Self

What is Product of Array Except Self?

Example 1

Example 2

Understanding the Problem

Why Is This Question Asked in Interviews?

1. Avoiding Brute Force

2. Prefix and Suffix Patterns

3. Handling Edge Cases

Real-World Applications

Database Analytics

Machine Learning

Distributed Systems

Statistics

Problem Statement

Constraints

Rules

Understanding Product Calculation

Handling Zero Values

Array Visualization

Formula

Dry Run

Step 1

Step 2

Step 3

Approach 1 — Brute Force Multiplication

Algorithm

Java Program

Output

Step-by-Step Explanation

Complexity Analysis

Advantages

Drawbacks

Approach 2 — Prefix and Suffix Arrays

Prefix Example

Suffix Example

Formula

Java Program

Complexity Analysis

Advantages

Drawbacks

Approach 3 — Optimized Prefix and Suffix Approach (Optimal)

Core Idea

Example

First Pass — Prefix Product

Second Pass — Suffix Product

Java Program

Output

Step-by-Step Explanation

Step 1: Prefix Calculation

Step 2: Suffix Calculation

Complexity Analysis

Advantages

Drawbacks

Mathematical Explanation

Division Approach (Why It Is Usually Avoided)

Zero Case

Multiple Zero Case

Java Streams Approach

Stream Implementation

Complexity Analysis

Why Streams Are Not Ideal Here?

Comparison of All Approaches

Prefix Product Pattern Explanation

Similar Problems

Range Sum Query

Product Queries

Primitive vs Object Arrays

Primitive Array

Object Array

Common Interview Mistakes

Mistake 1

Mistake 2

Mistake 3

Mistake 4

Edge Cases

Interview Follow-up Questions

Q1. Solve without division.

Q2. Solve in O(1) extra space.

Q3. Handle multiple zeros.