Product of Array Except Self in Java DSA: Two Clean Passes, No Division

Solve Product of Array Except Self in Java DSA without division. Brute force, prefix/suffix arrays, and the O(1)-space two-pass sweep, each with a full dry run.

1. Introduction

Product of Array Except Self in Java is one of those problems that looks harmless and then trips you up. You are given an array. For every slot, you must return the product of all the other numbers, leaving that slot out.

The first idea most people reach for is division. Multiply everything, then divide by each number. It works on paper, but the problem bans division and throws zeros at you, so that shortcut falls apart fast.

So we build the answer step by step. Brute force multiplies the neighbours for each slot with two loops. A cleaner version keeps two helper arrays, one for the left side and one for the right. The final one folds both sides into the output array itself and uses no extra space.

Every approach comes with a full dry run on the same seven numbers. Nothing gets skipped, so you can watch each number land in its slot and see exactly why it lands there.

2. Understanding the Problem

Let us fix the rules before we write any code.

• You get an array of integers, for example [2, 1, 3, 2, 1, 4, 1].
• For each index i, return the product of every number except nums[i].
• You are not allowed to use the division operator.
• The whole thing should run in O(n) time.

For our array the answer is [24, 48, 16, 24, 48, 12, 48]. Take index 0, which holds 2. Multiply the other six numbers (1, 3, 2, 1, 4, 1) and you get 24. Do the same for every slot and you have the output.

Interview Insight Interviewers often open with “why not just divide?” Give two reasons: division is banned by the prompt, and a single zero makes total/zero blow up. Naming both shows you spotted the trap.

3. Concepts You Need Here

3.1 Prefix Product

A prefix product for index i is the product of everything to the left of i. So for [2, 1, 3, 2, 1, 4, 1], the prefix at index 3 multiplies 2, 1, and 3, which gives 6. The very first slot has nothing on its left, so its prefix is 1.

3.2 Suffix Product

A suffix product for index i is the product of everything to the right of i. The suffix at index 3 multiplies 1, 4, and 1, which gives 4. The last slot has nothing on its right, so its suffix is 1.

3.3 The Key Idea

Here is the whole trick in one line. The answer at any slot is its prefix times its suffix. Left product times right product covers everything except the number sitting in that slot. No division needed, ever.

4. Approach 1: Brute Force

For each slot, loop over the whole array and multiply every other number. Two loops, plain and simple. It is slow, but it makes the goal crystal clear.

4.1 Pseudocode

result = new array of size n

for i from 0 to n-1:        // the slot we are filling
    product = 1
    for j from 0 to n-1:    // walk the whole array
        if j != i:
            product = product * nums[j]
    result[i] = product

return result

4.2 Pseudocode Explained

Two nested loops, but each line earns its place. Read it as “for every slot, walk the whole array and multiply the rest.”

• The outer loop picks one slot i to fill at a time, so by the end every index in result gets its own value.
• product starts at 1 for each new slot. One is the safe starting point for multiplication, because multiplying by 1 changes nothing, so the very first real multiply gives a clean result.
• The inner loop then walks every index j from 0 to n-1. It does not stop early or skip ahead; it visits the entire array for each slot.
• The check j != i is the heart of the trick. When j is a different index, we fold nums[j] into product. When j lands on the slot we are filling, we skip it, so that number never enters its own answer.
• Once the inner loop ends, product holds every number except nums[i] multiplied together. We store that in result[i] and move the outer loop to the next slot.

Notice what this costs. For every slot we restart product at 1 and re-multiply almost the whole array. That repeated work is exactly what the faster approaches will remove.

4.3 Java Code

import java.util.*;

public class ProductExceptSelfBrute {

    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 (j != i) {
                    product *= nums[j];
                }
            }
            result[i] = product;
        }
        return result;
    }

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

4.4 Java Code Explained

• Line 6 reads the array length into n, so we do not call nums.length repeatedly.
• On line 7 we allocate result as a fresh int array of size n. In Java a new int array fills with zeros, but we overwrite every slot, so those zeros never survive.
• Line 9 opens the outer loop that fixes the slot i we are filling this round.
• Then line 10 resets product to 1 at the top of each outer pass. This reset matters: if we forgot it, leftover values from the previous slot would corrupt the next one.
• Lines 11 to 15 run the inner loop. The guard if (j != i) lets every index through except the current slot, and product *= nums[j] folds each allowed number in.
• At line 16 we store the finished product into result[i], once the inner loop has seen every other number.
• Finally line 18 returns result after all slots are filled.

4.5 Dry Run of the Brute Force

Array: [2, 1, 3, 2, 1, 4, 1]. The outer loop fills one slot per pass. For each pass we show the inner loop building the product step by step, skipping the slot where j equals i. Nothing is hidden.

Pass i = 0 (skip nums[0] = 2). product starts at 1:

So result[0] = 24.

Pass i = 3 (skip nums[3] = 2). product starts at 1:

So result[3] = 24.

The remaining passes work the exact same way. Here is what each outer pass produces, so you can see the full array fill up:

Final result: [24, 48, 16, 24, 48, 12, 48].

4.6 Reading the Dry Run

Let us walk the two detailed passes and see what the loops are really doing.

Pass i=0, filling the first slot.

The outer loop parks on slot 0, which holds 2. That 2 is the one number we must leave out. Now the inner loop sweeps across all seven indices and multiplies the rest.

• j=0: this is the slot itself, so we skip it. product stays 1.
• j=1 to j=2: we fold in 1 then 3, so product climbs from 1 to 3.
• Next at j=3 to j=4: we fold in 2 then 1, so product moves to 6 and stays 6.
• Then at j=5: we fold in 4, and product jumps to 24.
• Finally at j=6: we fold in the last 1, and product stays 24.

Every number except that first 2 got multiplied in, so result[0] is 24. That is exactly what the problem wanted.

Pass i=3, filling the middle slot.

Now the outer loop sits on slot 3, which holds 2. This time the skip happens in the middle of the sweep, not at the start.

• j=0 to j=2: we fold in 2, 1, 3, so product becomes 6.
• At j=3: this is the slot itself, so we skip. product stays 6.
• Then j=4 to j=6: we fold in 1, 4, 1, so product ends at 24.

The skip landing in the middle changes nothing about the logic. We still touch every other number exactly once, so result[3] is 24.

The rest of the passes repeat this pattern, each one leaving out a different slot. Notice how much repeated work happens. For every single slot we re-multiply almost the whole array from scratch, which is why this version is slow.

4.7 Time and Space Cost

• Time is O(n²), because the outer loop runs n times and the inner loop runs n times inside it.
• Space is O(1) extra, since we only keep one product variable, ignoring the output array.

Seven numbers means 49 multiply checks, which is fine. For a large array this quadratic work drags, so we speed it up next.

5. Approach 2: Prefix and Suffix Arrays

Instead of rebuilding a product for every slot, compute the left products once and the right products once. Store them in two arrays. Then the answer for each slot is just left times right.

5.1 Pseudocode

prefix = new array of size n, all 1
suffix = new array of size n, all 1

for i from 1 to n-1:              // build left products
    prefix[i] = prefix[i-1] * nums[i-1]

for i from n-2 down to 0:         // build right products
    suffix[i] = suffix[i+1] * nums[i+1]

result = new array of size n
for i from 0 to n-1:
    result[i] = prefix[i] * suffix[i]

return result

5.2 Pseudocode Explained

Three short loops, each doing one clean job, and no number ever multiplied twice.

• prefix[0] and suffix[n-1] both stay 1. The first slot has nothing to its left and the last has nothing to its right, so their missing side is an empty product, which equals 1.
• The first loop walks left to right and builds prefix. Each prefix[i] is the previous prefix times nums[i-1], the number sitting just before i. So every cell reuses the work already done, instead of recounting from the start.
• That offset is worth pausing on. prefix[i] uses nums[i-1], not nums[i], so a slot’s own number is never part of its left product. This off-by-one is intentional, not a bug.
• A second loop walks right to left and builds suffix the mirror way. Each suffix[i] is the next suffix times nums[i+1], the number just after i, so again the slot’s own value stays out.
• Then a third loop multiplies prefix[i] by suffix[i] for every slot. Left product times right product is the product of everything except nums[i], which is the answer we want.

5.3 Java Code

import java.util.*;

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;
    }

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

5.4 Java Code Explained

• Lines 7 to 9 allocate three int arrays of size n: prefix, suffix, and result.
• Line 11 seeds prefix[0] to 1, the empty left product for the first slot.
• Lines 12 to 13 fill the rest of prefix. The loop starts at i=1, and prefix[i-1] * nums[i-1] carries the running left product forward one number at a time.
• Line 16 seeds suffix[n-1] to 1, the empty right product for the last slot.
• Lines 17 to 19 fill suffix. This loop counts down from n-2, and suffix[i+1] * nums[i+1] carries the running right product backward one number at a time.
• Lines 21 to 23 combine the two arrays. For each slot, prefix[i] * suffix[i] gives the final answer, which line 24 returns.
• Watch the index math: prefix reaches back with i-1 and suffix reaches forward with i+1. Those offsets are what keep nums[i] out of its own slot.

5.5 Dry Run of the Prefix and Suffix Arrays

Array: [2, 1, 3, 2, 1, 4, 1]. We build the prefix array first, then the suffix array, then combine them. Every single cell is traced.

Building prefix (left products). prefix[0] = 1 by rule:

prefix ends as [1, 2, 2, 6, 12, 12, 48].

Building suffix (right products). suffix[6] = 1 by rule, and we walk backwards:

suffix ends as [24, 24, 8, 4, 4, 1, 1].

Combining: result[i] = prefix[i] × suffix[i]:

Final result: [24, 48, 16, 24, 48, 12, 48].

5.6 Reading the Dry Run

Let us go array by array and see how each cell earns its value.

Building the prefix array.

prefix[0] is 1 because slot 0 has nothing on its left. From there each cell reuses the one before it, which is why this is fast.

• prefix[1]: take prefix[0] (1) and multiply by nums[0] (2). That gives 2, the product of everything left of slot 1.
• prefix[2]: take prefix[1] (2) and multiply by nums[1] (1). Still 2, since multiplying by 1 changes nothing.
• Then prefix[3]: take prefix[2] (2) and multiply by nums[2] (3). That gives 6.
• Each later cell keeps stacking one more left number, ending at prefix[6] = 48.

Notice we never recompute from scratch. Every cell just extends the previous product by one number, so the whole array fills in a single sweep.

Building the suffix array.

suffix[6] is 1 because the last slot has nothing on its right. This time we walk backwards, stacking right-side numbers.

• suffix[5]: take suffix[6] (1) and multiply by nums[6] (1). That gives 1.
• suffix[4]: take suffix[5] (1) and multiply by nums[5] (4). That gives 4.
• Then suffix[3]: take suffix[4] (4) and multiply by nums[4] (1). Still 4.
• The sweep keeps going down to suffix[0] = 24, each cell adding one more right number.

Combining the two arrays.

Now the payoff. For each slot, prefix holds everything on the left and suffix holds everything on the right. Multiply them and the slot’s own number is nowhere in the product.

• Slot 0: prefix 1 times suffix 24 gives 24. The left side was empty, so the answer is purely the right side.
• At slot 3: prefix 6 times suffix 4 gives 24. Left of it multiplied to 6, right of it multiplied to 4.
• Then slot 6: prefix 48 times suffix 1 gives 48. The right side was empty, so the answer is purely the left side.

Left times right, every time. That single rule is the heart of the whole problem.

Interview Insight If asked why the edges start at 1, say this: the first slot has no left neighbours and the last has no right neighbours, so their missing side must multiply as 1, the identity for multiplication.

5.7 Time and Space Cost

• Time is O(n), because three separate single loops replace the nested pair.
• Space is O(n), for the two helper arrays we keep around.

A big jump over brute force on speed. But interviewers usually push further and ask you to drop those two extra arrays, which is the final version.

6. Approach 3: Two Passes with O(1) Extra Space

We do not really need two helper arrays. Write the left products straight into the output array on one pass. Then sweep back over the output and multiply in the right products using a single running variable. This is the answer interviewers hope to see.

6.1 Pseudocode

result = new array of size n

prefix = 1                       // running left product
for i from 0 to n-1:
    result[i] = prefix           // store left product first
    prefix = prefix * nums[i]    // then extend it

suffix = 1                       // running right product
for i from n-1 down to 0:
    result[i] = result[i] * suffix
    suffix = suffix * nums[i]

return result

6.2 Pseudocode Explained

Two passes, one running number each, and the output array does double duty as scratch space.

• prefix starts at 1 and acts as a running left product. As the first pass moves right, prefix always holds the product of everything seen so far.
• Inside the first pass the order is store first, extend second. We write prefix into result[i], then multiply nums[i] into prefix. Because the write happens before the multiply, result[i] captures the left product without nums[i] in it.
• After that first pass, result is not the final answer yet. Each slot holds only its left product, waiting for the right side.
• suffix starts at 1 and acts as a running right product. The second pass walks backward, so suffix always holds the product of everything to the right so far.
• The second pass uses the same store-then-extend order. We multiply result[i] by suffix, folding the right side onto the left side already sitting there, then extend suffix with nums[i].

That store-before-extend timing, used in both passes, is the whole game. It is what guarantees nums[i] never lands in its own slot, so we get the same answer as two arrays but with a single variable.

6.3 Java Code

import java.util.*;

public class ProductExceptSelfOptimal {

    public static 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;
    }

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

6.4 Java Code Explained

• Line 7 allocates result, the only array we create. There is no separate prefix or suffix array this time.
• Line 9 starts prefix at 1 for the left-to-right pass.
• Lines 10 to 13 run that pass. result[i] = prefix stores the left product first, then prefix *= nums[i] extends it. Doing the store before the multiply is what keeps nums[i] out of its own slot.
• Line 15 starts suffix at 1 for the right-to-left pass.
• Lines 16 to 19 run that pass counting down from n-1. result[i] *= suffix folds the right product onto the left product already in the slot, then suffix *= nums[i] extends it for the next step left.
• Line 20 returns result, which now holds prefix times suffix in every slot. No extra array was ever needed.

6.5 Dry Run of the Two-Pass Sweep

Array: [2, 1, 3, 2, 1, 4, 1]. We trace the left pass first, then the right pass, watching result change on every step. Both passes store into result before extending the running product.

Left pass. prefix starts at 1, result starts empty (shown as _):

After the left pass, result = [1, 2, 2, 6, 12, 12, 48]. Each slot now holds its left product.

Right pass. suffix starts at 1, and we walk from index 6 back to 0:

Final result: [24, 48, 16, 24, 48, 12, 48].

6.6 Reading the Dry Run

Let us walk both passes slowly, because the store-before-extend timing is the one thing that makes this work.

Left pass, storing left products.

prefix begins at 1, meaning “nothing multiplied yet.” On each step we first drop prefix into result[i], then fold nums[i] in for the next slot.

• i=0: prefix is 1, so result[0] becomes 1. Slot 0 has no left neighbour, so 1 is correct. Then prefix becomes 1 × 2 = 2.
• i=1: prefix is 2, so result[1] becomes 2. That 2 is nums[0], the only number left of slot 1. Then prefix becomes 2 × 1 = 2.
• Next i=2: prefix is 2, so result[2] becomes 2. Then prefix becomes 2 × 3 = 6.
• The sweep continues, and result[6] lands on 48, the product of all six numbers to the left of the last slot.

Because we store before we extend, nums[i] itself never sneaks into result[i]. It only joins prefix for the slots that come after it.

Right pass, folding in right products.

Now suffix begins at 1 and we move backwards. Each slot already holds its left product, so we just multiply the right product on top.

• i=6: result[6] is 48, suffix is 1, so result[6] stays 48. The last slot has no right neighbour. Then suffix becomes 1 × 1 = 1.
• i=5: result[5] is 12, suffix is 1, so result[5] stays 12. Then suffix becomes 1 × 4 = 4.
• At i=4: result[4] is 12, suffix is 4, so result[4] becomes 48. Then suffix becomes 4 × 1 = 4.
• At i=3: result[3] is 6, suffix is 4, so result[3] becomes 24. Then suffix becomes 4 × 2 = 8.
• By i=0: result[0] is 1, suffix is 24, so result[0] becomes 24, purely the right product since the left was empty.

Each slot ends as left product times right product, exactly like the two-array version. The difference is we carried the right side in a single variable instead of a whole array.

Interview Insight A sharp follow-up is “does the output array count as extra space?” The clean answer: no, the result you must return never counts. That is why this version is called O(1) extra space even though it writes an array.

6.7 Comparing the Three Traces

7. Comparing the Three Approaches

All three give the same answer. They just pay different prices.

The two faster versions share the same time class. What separates them is memory. The two-pass version reuses the output array and carries the right side in one variable, so it barely uses any extra space.

In an interview, start with brute force, point out the wasted re-multiplying, mention the prefix and suffix arrays, then collapse them into the two-pass sweep. That climb is the story interviewers want to hear.

Interview Insight If pushed on why division is off the table, note the zero problem clearly: with one zero, only that slot is nonzero; with two or more zeros, every slot is zero. The prefix and suffix method handles all of these without a single divide.

8. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep them in mind.

• Reaching for division forgets the ban and breaks on any zero in the array.
• Extending the running product before storing it folds nums[i] into its own slot, which is wrong.
• Forgetting to seed prefix and suffix at 1 leaves the edge slots empty or zeroed.
• An array with one zero, like [1, 2, 0, 4], should give [0, 0, 8, 0], since only the zero’s slot escapes it.
• An array with two zeros makes every slot zero, and the prefix-suffix method returns that correctly.

Run those zero cases through your code before you call it done. They catch more bugs than any ordinary input will.

9. Interview Questions

10. Conclusion

Product of Array Except Self in Java looks scary because of the no-division rule. But once you split the work into a left side and a right side, the fear melts away.

Our seven-number trace showed the payoff clearly. Brute force re-multiplied the neighbours for every slot. The two-pass sweep filled left products in the output, then folded right products back in, all with one spare variable.

So take the pattern, not just the answer. When a slot depends on everything around it, split that into what is before and what is after. Compute each side once, then combine. That habit turns a slow quadratic grind into a clean linear pass, and it will help on many array problems further down the list.

11. Further Reading

• LeetCode Product of Array Except Self problem
• Oracle Java Arrays documentation
• Previous in this series: Container With Most Water in Java
• Next in this series: Valid Anagram in Java