Product of Array Except Self Without Using Division: O(n) Java Solution

You can calculate the product of array elements except self without using division by employing a two-pass algorithm that accumulates left products in a first pass and right products in a second pass, achieving O(n) time and O(1) auxiliary space.

The "product of array except self" problem is a classic algorithmic challenge that tests your ability to optimize for both time and space complexity. This article examines the optimal solution implemented in the kdn251/interviews repository, which demonstrates how to solve this problem without division while maintaining linear time complexity.

Understanding the Problem Constraints

The problem requires constructing an output array where each element at index i equals the product of all input array elements except nums[i]. The constraints are strict:

• No division allowed – You cannot compute the total product and divide by each element
• O(n) time complexity – The solution must run in linear time relative to input size
• O(1) auxiliary space – Aside from the output array, the algorithm must use constant extra storage

The Two-Pass Left/Right Accumulation Algorithm

The solution implemented in leetcode/array/ProductofArrayExceptSelf.java uses a clever two-pass approach that leverages the output array as temporary storage to avoid additional data structures.

First Pass – Left Products

The algorithm first traverses from left to right, maintaining a running product of all elements to the left of the current index:

int left = 1;
for (int i = 0; i < n; i++) {
    result[i] = left;          // product of elements left of i
    left *= nums[i];
}

After this pass, result[i] contains the product of all elements before index i.

Second Pass – Right Products

The second pass traverses from right to left, maintaining a running product of all elements to the right:

int right = 1;
for (int i = n - 1; i >= 0; i--) {
    result[i] *= right;        // multiply by product of elements right of i
    right *= nums[i];
}

This multiplies the stored left product by the right product, yielding the final result without ever using division.

Java Implementation from kdn251/interviews

The complete implementation appears in both the LeetCode and LinkedIn solution sets within the kdn251/interviews repository:

• LeetCode version: leetcode/array/ProductofArrayExceptSelf.java
• LinkedIn version: company/linkedin/ProductOfArrayExceptSelf.java

Both files contain the identical productExceptSelf method:

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 1;
    
    // Left products
    for (int i = 0; i < n; i++) {
        result[i] = left;
        left *= nums[i];
    }
    
    int right = 1;
    // Right products combined with left products
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= right;
        right *= nums[i];
    }
    
    return result;
}

Complexity Analysis

The algorithm achieves optimal complexity across both dimensions:

• Time Complexity: O(n) – Each element is visited exactly twice (once in each pass), resulting in linear time relative to the input array length.
• Space Complexity: O(1) auxiliary – Only two scalar variables (left and right) are used besides the output array, which does not count toward auxiliary space under standard interview constraints.

Handling Edge Cases

The implementation robustly handles several edge cases without modification:

• Arrays containing zeros: When zeros appear in the input, the left and right products propagate correctly. Positions containing zero receive the product of all non-zero elements, while other positions become zero.
• Minimum length arrays: For an array of length 2, the algorithm correctly returns [nums[1], nums[0]] without special handling.
• Single element arrays: While the problem typically assumes length ≥ 2, the code returns [1] for single-element inputs, which is mathematically consistent.

Summary

• The product of array except self without using division requires a two-pass accumulation strategy to achieve O(n) time and O(1) space.
• The kdn251/interviews repository implements this in leetcode/array/ProductofArrayExceptSelf.java and company/linkedin/ProductOfArrayExceptSelf.java using the productExceptSelf method.
• The algorithm first stores left products, then multiplies by right products in a reverse pass, avoiding division entirely while handling edge cases like zeros automatically.

Frequently Asked Questions

Why can't I use division to solve the product of array except self problem?

Using division would simplify the problem to computing the total product once and dividing by each element. However, this approach fails when the array contains zeros (division by zero) and violates the explicit constraint prohibiting division operations. The two-pass accumulation method handles zeros correctly without division risks.

What is the time and space complexity of the optimal solution?

The optimal solution runs in O(n) time because it performs exactly two linear passes through the array. It uses O(1) auxiliary space (excluding the output array) by storing intermediate left products in the result array and computing right products on-the-fly with a single scalar variable.

How does the algorithm handle arrays containing multiple zeros?

If the input contains exactly one zero, the position of that zero receives the product of all non-zero elements, while all other positions become zero. If the input contains two or more zeros, every position in the output becomes zero because every element is "except" at least one zero. The left/right accumulation logic naturally produces these results without special-case code.

Where can I find the complete implementation in the kdn251/interviews repository?

The complete Java implementation resides in two locations within the repository: leetcode/array/ProductofArrayExceptSelf.java for the LeetCode variation and company/linkedin/ProductOfArrayExceptSelf.java for the LinkedIn interview preparation set. Both files contain the identical productExceptSelf method demonstrating the two-pass algorithm.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}