How do you solve Product of Array Except Self on LeetCode?

Product of Array Except Self (LeetCode #238) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using prefix and suffix products allows us to avoid division.

What is the brute force solution for Product of Array Except Self?

The brute force approach for Product of Array Except Self is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach calculates the product for each index by multiplying all other elements in the array. This is straightforward but inefficient as it involves repeated calculations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Product of Array Except Self?

Product of Array Except Self uses the following concepts: Array, Prefix Sum. The recommended patterns to study are: Prefix Sum, Suffix Array.

What are the interview tips for Product of Array Except Self?

Explain your thought process clearly before coding. Consider edge cases and discuss them with the interviewer. Practice writing clean and efficient code.

What are common mistakes when solving Product of Array Except Self?

Forgetting to initialize the result array or using incorrect indices. Not considering edge cases like zeros in the input array.

#238

Product of Array Except Self

Medium

ArrayPrefix SumPrefix SumSuffix Array

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses two passes to compute the prefix and suffix products, allowing us to calculate the result in linear time without using division. This approach is efficient and avoids redundant calculations.

⚙️

Algorithm

4 steps

1Step 1: Initialize a result array of the same length as nums with all elements set to 1.
2Step 2: Compute the prefix products: for each index i, set result[i] to the product of all previous elements (from the start to i-1).
3Step 3: Compute the suffix products: iterate from the end of the array, multiplying the current result[i] by the product of all elements after i (from i+1 to end).
4Step 4: Return the result array.

solution.py12 lines

1def productExceptSelf(nums):
2    n = len(nums)
3    result = [1] * n
4    prefix = 1
5    for i in range(n):
6        result[i] = prefix
7        prefix *= nums[i]
8    suffix = 1
9    for i in range(n-1, -1, -1):
10        result[i] *= suffix
11        suffix *= nums[i]
12    return result

ℹ

Complexity note: The time complexity is O(n) because we make two passes through the array (one for prefix and one for suffix). The space complexity is O(n) due to the result array.

1Using prefix and suffix products allows us to avoid division.
2Two passes through the array are sufficient to compute the result.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.