238 : Product of Array Except Self

By •
238. Product of Array Except Self

Problem Restated (Very Simply)

You are given an array:

nums = [1, 2, 3, 4]

For each index, you need to calculate:

Product of all elements except the one at that index

So:

  • 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 output:

[24, 12, 8, 6]

Why Not Just Multiply Everything?

Many beginners think:

“Why not calculate total product and divide by nums[i]?”

Two problems:

  1. Division is not allowed
  2. Zero breaks everything

So we need another way.

Core Idea (Absolute Beginner Explanation)

For any index i, the result is:

(product of numbers to the LEFT of i)
×
(product of numbers to the RIGHT of i)

That’s it.
No tricks. No division.

Step 1: Prefix Product (Left Side)

Prefix means everything before the current index.

For:

nums = [1, 2, 3, 4]

Prefix product array conceptually becomes:

Index:   0   1   2   3
Prefix:  1   1   2   6

Why?

  • Index 0 → nothing on the left → 1
  • Index 1 → 1
  • Index 2 → 1 * 2 = 2
  • Index 3 → 1 * 2 * 3 = 6

Step 2: Suffix Product (Right Side)

Suffix means everything after the current index.

Index:   0   1   2   3
Suffix: 24  12   4   1

Why?

  • Index 3 → nothing on the right → 1
  • Index 2 → 4
  • Index 1 → 3 * 4 = 12
  • Index 0 → 2 * 3 * 4 = 24

Step 3: Multiply Prefix × Suffix

Index:    0    1    2    3
Prefix:   1    1    2    6
Suffix:  24   12    4    1
Result:  24   12    8    6

This gives the answer 🎯

Two-Array Approach (Easy to Understand)

How It Works

  1. Build prefix[]
  2. Build suffix[]
  3. Multiply both

Code Idea (Conceptual)

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

Complexity

  • Time: O(n)
  • Space: O(n) ❌ (extra arrays)

This approach is great for beginners, but not optimal.

Optimized Approach (Interview Expected)

Instead of two arrays:

  • Use one result array
  • Use two variables: prefix and suffix

Why This Works

  • First pass stores prefix directly in result
  • Second pass multiplies suffix into result
  • No extra arrays needed

Dry Run of Optimized Code (Very Important)

Input

nums = [1, 2, 3, 4]

Initial State

result = [1, 1, 1, 1]
prefix = 1

First Loop (Prefix Pass)

iresult[i]prefix
011×1=1
111×2=2
222×3=6
366×4=24

After loop:

result = [1, 1, 2, 6]

Second Loop (Suffix Pass)

suffix = 1
iresult[i]suffix
36×1=61×4=4
22×4=84×3=12
11×12=1212×2=24
01×24=2424×1=24

Final result:

[24, 12, 8, 6]

Optimized C++ Code (Clean & Interview-Ready)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);

        int prefix = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = prefix;
            prefix *= nums[i];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }

        return ans;
    }
};

Python

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        result = [1] * n

        prefix = 1
        for i in range(n):
            result[i] = prefix
            prefix *= nums[i]

        suffix = 1
        for i in range(n - 1, -1, -1):
            result[i] *= suffix
            suffix *= nums[i]

        return result

Java

class Solution {
    public 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;
    }
}

JavaScript

var productExceptSelf = function(nums) {
    const n = nums.length;
    const result = new Array(n).fill(1);

    let prefix = 1;
    for (let i = 0; i < n; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }

    let suffix = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] *= suffix;
        suffix *= nums[i];
    }

    return result;
};

Comparison Summary

ApproachTimeSpaceInterview
Brute ForceO(n²)O(1)❌
Two ArraysO(n)O(n)⚠️
Optimized Prefix-SuffixO(n)O(1)✅

Common Beginner Mistakes

  • Forgetting that output array doesn’t count as extra space
  • Initializing prefix/suffix with 0 instead of 1
  • Trying to use division
  • Panicking when zeros appear (this solution handles them)

How to Explain This in an Interview

“For each index, the result is the product of elements before and after it.
I compute prefix products in one pass, suffix products in another, and combine them in the output array to keep space O(1).”

That answer alone impresses interviewers.

Final Takeaway

  • This problem is about thinking, not memorization
  • Prefix-suffix is a core array technique
  • Once you get this, many other problems become easier

If you understand this solution deeply, you’re already thinking like an interview-ready engineer 👏

Related Posts

Scroll to Top