The O(n) Club: Product of Array Except Self (Or, How to Survive Without Division & Dignity)

The O(n) Club: Product of Array Except Self (Or, How to Survive Without Division & Dignity)

⚡ TL;DR

You need a new array where each position gets the product of all the other values except itself. No, you can’t use division—that’s cheating and interviewers know it. Brute force is slow and ugly, like most rushed Monday mornings. Here’s what you wish you didn’t have to write:

// Brute force (legendary for eating CPUs):
int[] output = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
    int prod = 1;
    for (int j = 0; j < nums.length; j++) {
        if (i != j) prod *= nums[j];
    }
    output[i] = prod;
}

This works… if you have infinite time, no zeros, and a desire to annoy your runtime profiler. Now let’s see how adults do it.

🧠 How Devs Usually Mess This Up

Ah, the old “just multiply everything together and divide by the current number” routine—classic! Instant face-palm when a single zero shows up and turns everything into zero. And if there are two zeroes? Congratulations, your output is now sponsored by the number zero. Plus, the problem says no division. Yes, because leetcoders love pain.

Many people also drag in extra arrays for prefix and suffix products—doubling their space use and raising interview eyebrows everywhere. Go lean or go home.

🔍 What’s Actually Going On

Imagine you’re building a team report, but for each developer you leave them out and multiply everyone else’s daily coffee intake. Do you really want to total up the whole room every time? No. Instead:

• First, walk left-to-right and store the product of everything before each dev (prefix products).
• Then, stroll right-to-left and multiply by the product of everything after (suffix products).

This way, each output slot is the product of every other dev’s caffeine habits—no division, no drama, and way less work for your nervous CPU.

🛠️ PseudoCode

• Set up:
  int[] res = new int[nums.length];
  Start with 1s since multiplying by zero would be… well, catastrophic.
• Prefix pass: Left to right, fill res[i] with product of everything before i.
  int left = 1;<br>for (int i = 0; i < nums.length; i++) {<br>  res[i] = left;<br>  left *= nums[i];<br>}
• Suffix pass: Right to left, multiply res[i] by product of everything after i.
  int right = 1;<br>for (int i = nums.length - 1; i >= 0; i--) {<br>  res[i] *= right;<br>  right *= nums[i];<br>}
• Return and flex: Output res, because you’ve earned it.

💻 The Code

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    int prefix = 1;
    for (int i = 0; i < n; i++) {
        res[i] = prefix;
        prefix *= nums[i];
    }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= suffix;
        suffix *= nums[i];
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero is the villain: If you have two or more zeros, every output is zero. One zero? Only that spot is non-zero—rest are zeroed out. Handle with care, or at least denial.
• Division-based code crashes fast when zeros pop up. Trust the process.
• Time? O(n). Extra space? Just your output array and two hand-picked variables (so, basically O(1) if you ignore the result).

🧠 Interviewer Brain-Tattoo

“Division is for mortals. Prefix and suffix are for the O(n) gods.”
Don’t multiply harder—multiply smarter, and always look both ways for zeros.