LeetCode 238: Product of Array Except Self

An Interactive Visual Explainer

Idea By: Chetan Pachpande | Executed By: Claude

← Back to Home

Problem Description

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 algorithm must run in O(n) time and without using the division operation.

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]

Complexity Analysis

Time Complexity: O(N)
Two passes through the array, each taking O(n) time.

Space Complexity: O(1)
Only using the output array and a few variables. No extra space proportional to input size.

Java Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, 1);
        
        // Prefix pass: result[i] = product of all elements before i
        int preFix = 1; 
        for (int i = 0; i < nums.length; i++) {
            result[i] = preFix;
            preFix = preFix * nums[i];
        }
        
        // Postfix pass: multiply by product of all elements after i
        int postFix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] = postFix * result[i];
            postFix = postFix * nums[i];
        }
        
        return result;
    }
}

Intuition

The key insight is to use a two-pass approach with prefix and postfix products to avoid division and achieve O(n) time complexity.

  1. Prefix Pass: For each position i, store the product of all elements to the left of i.
  2. Postfix Pass: For each position i, multiply the prefix product by the product of all elements to the right of i.
  3. Result: result[i] = (product of elements before i) × (product of elements after i)
  4. No Division: We cleverly avoid division by constructing the answer through multiplication only.
  5. Space Efficient: Use the result array itself to store intermediate values.

Step-by-Step Code

Live Visualization

Input Array:

Result Array: Prefix Pass

Current Calculation:

Ready to start...

Algorithm States

Status: Ready Current Phase: Initialization Current Index (i): N/A Prefix Value: 1 Postfix Value: 1

Execution Commands