238. Product of Array Except Self - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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 solution must be implemented without using division and should run in O(n) time.

Example Inputs and Outputs:

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: The product of all elements except nums[i] is:
- answer[0] = 2 * 3 * 4 = 24
- answer[1] = 1 * 3 * 4 = 12
- answer[2] = 1 * 2 * 4 = 8
- answer[3] = 1 * 2 * 3 = 6
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Zeros are handled carefully. Here any index except the one with value 0 will have a product that includes 0, resulting in 0. The index corresponding to the single 0 in the input has output 9 (product of -1 * 1 * -3 * 3). If there were more than one zero in the input, all outputs would be 0.
Input: nums = [4, 5, 1, 8, 2]
Output: [80, 64, 320, 40, 160]
(Each output is the product of all input numbers except the one at that position.)

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.

Hints for Solving the Problem:

Can you compute the product of all elements efficiently without iterating for each index separately? Think about reusing computations.
Instead of using division, consider maintaining a left product and a right product for each position. Using these prefix and suffix products can help compute the result in one pass.

Approach 1: Brute Force (O(n²))

This straightforward approach is to iterate over each element and compute the product of all other elements by a nested loop. While easy to implement, this method is inefficient for large inputs because of its quadratic time complexity.

Code (Brute Force)

Brute Force Approach (Python)

Python3

. . . .

Brute Force Approach (Java)

Java

. . . .

This brute-force solution correctly computes the result but performs O(n) work for each of the n indices, leading to O(n²) time complexity. It will be too slow when n is large (e.g., 10^5).

Approach 2: Optimal Solution Using Prefix & Suffix Products (O(n))

The optimal solution runs in linear time by computing products in two passes without using division.

The idea is to calculate the prefix product (product of all elements to the left of the current index) and the suffix product (product of all elements to the right of the current index) for each position, then multiply them to get the result for that index.

How it works: We first traverse the array from the left, accumulating a running product. For each index i, store the product of all elements before it in a result array. Then traverse from the right end, and for each index multiply the existing value (which is the left product) by the running product of all elements to the right. This gives the final product for each index without ever multiplying the index’s own value.

Code (Optimal Prefix/Suffix)

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

In this optimal approach, each element of the output is calculated by combining the product of all elements to the left and all elements to the right of that index. We use the result array itself to store the left products in the first loop, and then update it with the right products in the second loop. This approach is efficient and runs in O(n) time using constant extra space (aside from the output array).

Complexity Analysis

Brute Force: Time complexity is O(n²) and space complexity is O(1) (not counting the output array). This is inefficient for large n.
Optimal Prefix/Suffix: Time complexity is O(n) and space complexity is O(1) auxiliary (we only use a few extra variables, aside from the output array which is required). This meets the problem requirements.

Edge Cases to Consider:

Array containing zero: If the array contains one or more zeros, the output needs special handling. For example, if there is exactly one zero in nums, then all positions except the zero's position will be 0 in the output (because the product will include that zero). If there are two or more zeros, then every output element will be 0.
Negative numbers: The presence of negative values doesn't affect the algorithm correctness, but the sign of the product should be correct for each position (even number of negatives yields positive product, odd yields negative). The logic of prefix/suffix multiplication inherently handles this as long as multiplication is done correctly.
All elements are the same: e.g. nums = [3, 3, 3] should produce [9, 9, 9]. Ensure that the algorithm doesn't erroneously reuse data from the same index or anything that could break this symmetrical case.

Common Mistakes:

Using division to get the result: A naive approach might compute the total product of all numbers and then divide by nums[i] for each index. This fails when nums contains zero (division by zero is undefined) and was explicitly disallowed by the problem.
Incorrect initialization of the right product accumulator: Forgetting to reset or properly initialize the running product for the suffix pass can lead to wrong answers. Make sure right_product (in Python) or rightProduct (in Java) starts at 1 before the right-to-left traversal.
Overwriting values too early: If using a single array to store results, be careful not to overwrite a value that you still need. The prefix-first, then suffix approach as shown ensures that at each step you have the necessary values available.

Alternative Variations:

Allowing Division: If the problem allowed using division, one could simply compute the product of all elements and then for each index return total_product / nums[i]. This would be O(n) time but is not robust against zeros and not allowed in this problem.
Using Prefix/Suffix arrays explicitly: Instead of using the output array to store prefix products, you could use two separate arrays L and R of length n where L[i] is product of elements up to (but not including) i, and R[i] is product of elements from the end to (but not including) i. Then set answer[i] = L[i] * R[i]. This is a bit more space-heavy (O(n) extra space) but conceptually simpler for some to understand. The approach shown above optimizes by not needing separate arrays for prefix and suffix.

Related Problems for Further Practice:

Prefix Sum and Prefix Product problems: These are a category of problems where precomputing cumulative sums or products can drastically reduce computation for range queries or exclusion operations. Practicing these will strengthen understanding of the technique.
LeetCode 238 - Product of Array Except Self (the same problem, often cited as a classic array problem). If you found this problem challenging, revisit it after practicing other problems to solidify the concept.
LeetCode 53 - Maximum Subarray: Although a different problem (sum vs. product), it uses the idea of accumulating results (Kadane's algorithm) and can help understand handling of running computations.
LeetCode 152 - Maximum Product Subarray: Involves keeping track of running products (including handling negatives and zeros) and is another twist on using prefix/suffix concepts (here you track max and min products). This is a good next step to practice after solving Product of Array Except Self.