Product of Array Except Self

Master this topic with zero to advance depth.

Product of Array Except Self

The product of all elements except nums[i] is (product of all elements to the left of i) * (product of all elements to the right of i). We can precalculate these products in one or two passes.

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operator.

Visual Representation

nums = [1, 2, 3, 4]

Prefixes: [1,  1,  1*2, 1*2*3] = [1,  1,  2,  6]
Suffixes: [2*3*4, 3*4, 4,  1] = [24, 12, 4,  1]

Result:   [1*24, 1*12, 2*4, 6*1] = [24, 12, 8, 6]

Medium

Examples

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
answer[0] = 234 = 24, answer[1] = 134 = 12, answer[2] = 124 = 8, answer[3] = 123 = 6

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Any product that includes 0 will be 0

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

For each index i, we iterate through the entire array again using index j. If i != j, we multiply nums[j] to a running product. This is suboptimal due to the nested traversal.

⏱ O(N²) because for every element, we scan the rest of the array.💾 O(1) (excluding output array)

Detailed Dry Run

Index	Elements Multiplied	Result
0	2 * 3 * 4	24
1	1 * 3 * 4	12
2	1 * 2 * 4	8
3	1 * 2 * 3	6

java

import java.util.*;

public class Main {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int prod = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) prod *= nums[j];
            }
            res[i] = prod;
        }
        return res;
    }

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

Approach 2

Level II: Better Solution (Prefix & Suffix Arrays)

Intuition

Any element at i has a product equal to (everything to its left) * (everything to its right). We can precompute two arrays: prefix (cumulative product from start) and suffix (cumulative product from end).

⏱ O(N) traversal.💾 O(N) storage.

Detailed Dry Run

Index	Prefix (Left)	Suffix (Right)	Left * Right
0	1	234 = 24	24
1	1	3*4 = 12	12
2	1*2 = 2	4	8
3	123 = 6	1	6

java

import java.util.*;

public class Main {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        left[0] = 1; right[n-1] = 1;
        for (int i = 1; i < n; i++) left[i] = left[i-1] * nums[i-1];
        for (int i = n-2; i >= 0; i--) right[i] = right[i+1] * nums[i+1];
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = left[i] * right[i];
        return res;
    }

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

Approach 3

Level III: Optimal Solution (Space Optimized)

Intuition

We can optimize space by using the result array itself to store prefix products first. Then, we iterate backwards and maintain a running suffix product to multiply with the stored prefix values. This avoids extra arrays.

⏱ O(N) with only two passes.💾 O(1) extra space.

Detailed Dry Run

Optimization Visual

nums = [1, 2, 3, 4]

Forward Pass (Prefix): res = [1, 1, 2, 6] (Storing products of everything to the left)

Backward Pass (Suffix):

i	res[i] (Prefix)	Suffix Var	res[i] * Suffix (Final)
3	6	1	6
2	2	1*4=4	8
1	1	4*3=12	12
0	1	12*2=24	24

Visual Representation:

Index:   0    1    2    3
Nums:    1    2    3    4
Prefix: [1,   1,   2,   6]
Suffix: [24,  12,  4,   1]
Result: [24,  12,  8,   6]

java

import java.util.*;

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

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

← Previous QuestionLongest Consecutive Sequence

Next Question →Top K Frequent Elements

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.