Product of Array Except Self

MEDIUM✓ CHIP-TIMEDLC #238 — FULL STATEMENT ↗

The drill: Compute, for every index, the product of all other values in the array — without ever dividing and without recomputing the whole product from scratch each time.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives, and for every index the task is to report the product of all the other values in the array — everyone except that one position.

Division is off the table as a shortcut, since a zero anywhere in the array would break a divide-based approach; the product has to be assembled without ever dividing.

The output is its own array, the same length as the input, where each slot holds the product of everything except the value that started in that same slot.

EX 01

nums = [1, 2, 3, 4]

→ [24, 12, 8, 6]

EX 02

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

→ [0, 0, 6, 0]

A SINGLE ZERO ZEROES OUT EVERY INDEX BUT ITS OWN

EX 03

nums = [0, 0]

→ [0, 0]

TWO ZEROS ZERO OUT EVERYTHING

arrays hold at least two elements
values may be negative, zero, or positive, including more than one zero
the running products always fit in a standard signed integer range
division is disallowed as a solving technique

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Dividing the total product by nums[i] would give the answer in one pass, but a zero anywhere in the array breaks division. What structure avoids division entirely?

HINT 2 THE STRUCTURE

The product excluding index i splits cleanly into two halves: everything to its left times everything to its right. Both halves can be built as running totals.

HINT 3 ONE STEP FROM THE ANSWER

Fill the output with running prefix products left to right, then sweep right to left multiplying in a running suffix product — no division, and the second pass reuses the output array as its own storage.

COACH'S BOARD — THE PATTERN, STEP BY STEP

PREFIX MEETS SUFFIXPATTERN · PREFIX × SUFFIX PASSESnums = [1, 2, 3, 4]

STEP 1

nums = [1, 2, 3, 4]. A left-to-right pass fills each slot with the running product of everything to its left.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/product-of-array-except-self.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        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

TIME O(N)SPACE O(1) EXTRAPYTHON · RACE PACE · 13 LN

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = []
        for i in range(n):
            product = 1
            for j in range(n):
                if j != i:
                    product *= nums[j]
            result.append(product)
        return result

TIME O(N²)SPACE O(1) EXTRAPYTHON · TRAINING PACE · 11 LN

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

TIME O(N)SPACE O(1) EXTRAJAVA · RACE PACE · 17 LN

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

TIME O(N²)SPACE O(1) EXTRAJAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED