Product of Array Except Self

Problem Overview

Given an array of integers, return a new array where each element is the product of all the other elements, without using division and in O(n) time.

Why solve this?

Forbidding division rules out the obvious shortcut (divide the total product by each element) and forces the same prefix/suffix decomposition idea that powers prefix sums — just with multiplication, and with a genuinely useful O(1)-extra-space refinement.

Pattern Recognition

Whenever a result at index i needs 'everything except position i' and division is unavailable (or unsafe, as it would be with a zero in the array), split the computation into a left-side running product and a right-side running product.

Prerequisites

• Find Pivot Index — the same left/right split idea, applied to products instead of sums.

Hints

1. The obvious idea — divide the total product by nums[i] — breaks the moment any element is 0, and the problem forbids division anyway.
2. For each index, the answer is (product of everything to its left) times (product of everything to its right).
3. Compute the left-side running products into the output array first, then multiply in the right-side running product in a second pass, without ever allocating a separate array for it.

Approach

Start with the brute-force framing: for each index i, the answer is the product of every element except nums[i], which naively means an O(n) inner loop per index, O(n^2) total. The first improvement splits that into two O(n) passes: a prefix array where prefix[i] holds the product of everything before i, and a suffix array where suffix[i] holds the product of everything after i — the answer at i is then prefix[i] * suffix[i], in O(n) time but O(n) extra space for the two arrays. The final optimization removes the second array: first fill the output array with the left-side running products directly (output[i] = product of nums[0..i-1]), then make a second pass from the right with a single running suffix variable, multiplying it into output[i] as it goes — reconstructing the same result with only O(1) auxiliary space beyond the output array itself.

Code

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

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy