Product of Array Except Self

MediumArrayPrefix Sum
Category: Array & Hashing
Companies that ask this question:
AmazonFacebookMicrosoftAppleGoogle

Approach

Product of Array Except Self

Problem Statement

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 operation.

Examples

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation:
- answer[0] = 2*3*4 = 24
- answer[1] = 1*3*4 = 12
- answer[2] = 1*2*4 = 8
- answer[3] = 1*2*3 = 6

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
  • Cannot use division
  • Must be O(n) time

Approach

Key Insight

For each index i, the result is:

answer[i] = (product of all elements to the left) × (product of all elements to the right)

We can compute these using prefix and suffix products!

Solution: Prefix and Suffix Products

Algorithm:

  1. Left pass: Calculate prefix products (all elements to the left)
    • answer[i] = product of all elements before index i
  2. Right pass: Multiply by suffix products (all elements to the right)
    • answer[i] *= product of all elements after index i

Example Walkthrough:

nums = [1, 2, 3, 4]

Left pass (prefix products):
answer[0] = 1        (no elements to left)
answer[1] = 1        (1)
answer[2] = 1*2      (1*2 = 2)
answer[3] = 1*2*3    (1*2*3 = 6)
Result: [1, 1, 2, 6]

Right pass (multiply by suffix products):
answer[3] *= 1       (no elements to right) = 6*1 = 6
answer[2] *= 4       (4) = 2*4 = 8
answer[1] *= 3*4     (3*4 = 12) = 1*12 = 12
answer[0] *= 2*3*4   (2*3*4 = 24) = 1*24 = 24
Result: [24, 12, 8, 6]

Space Optimization

We can use a single variable to track the running product instead of extra arrays!

Complexity Analysis

  • Time Complexity: O(n)
    • Two passes through the array
  • Space Complexity: O(1)
    • Output array doesn't count as extra space
    • Only using constant extra space

Pattern Recognition

This problem demonstrates:

  • Prefix/Suffix patterns - computing cumulative values
  • Two-pass technique - left-to-right, then right-to-left
  • Space optimization - reusing output array
  • Avoiding division with clever math

Solution

java
1class Solution {
2    // Optimal Solution: Two Pass with O(1) space
3    public int[] productExceptSelf(int[] nums) {
4        int n = nums.length;
5        int[] answer = new int[n];
6
7        // Left pass: Calculate prefix products
8        // answer[i] = product of all elements to the left of i
9        answer[0] = 1; // No elements to the left of index 0
10        for (int i = 1; i < n; i++) {
11            answer[i] = answer[i - 1] * nums[i - 1];
12        }
13
14        // Right pass: Multiply by suffix products
15        // answer[i] *= product of all elements to the right of i
16        int rightProduct = 1; // Running product from the right
17        for (int i = n - 1; i >= 0; i--) {
18            answer[i] *= rightProduct;
19            rightProduct *= nums[i];
20        }
21
22        return answer;
23    }
24
25    // Alternative: Using explicit prefix and suffix arrays (for clarity)
26    public int[] productExceptSelfExplicit(int[] nums) {
27        int n = nums.length;
28        int[] prefix = new int[n];  // Product of all elements before i
29        int[] suffix = new int[n];  // Product of all elements after i
30        int[] answer = new int[n];
31
32        // Calculate prefix products
33        prefix[0] = 1;
34        for (int i = 1; i < n; i++) {
35            prefix[i] = prefix[i - 1] * nums[i - 1];
36        }
37
38        // Calculate suffix products
39        suffix[n - 1] = 1;
40        for (int i = n - 2; i >= 0; i--) {
41            suffix[i] = suffix[i + 1] * nums[i + 1];
42        }
43
44        // Multiply prefix and suffix
45        for (int i = 0; i < n; i++) {
46            answer[i] = prefix[i] * suffix[i];
47        }
48
49        return answer;
50    }
51}
52
Loading visualizer...