Course4all

Product of Array Except Self

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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

IndexElements MultipliedResult
02 * 3 * 424
11 * 3 * 412
21 * 2 * 48
31 * 2 * 36
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

IndexPrefix (Left)Suffix (Right)Left * Right
01234 = 2424
113*4 = 1212
21*2 = 248
3123 = 616
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):
ires[i] (Prefix)Suffix Varres[i] * Suffix (Final)
3616
221*4=48
114*3=1212
0112*2=2424
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)));
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLongest Consecutive Sequence
Next Question →Top K Frequent Elements