I’ve recently begun tackling the Blind 75, a curated list of LeetCode problems put together by Yangshun Tay, aimed at aiding those prepping for software engineering interviews. Writing these posts not only reinforces my understanding but also, I hope, aids others working through the list.
I would like to shoutout NeetCode. If I ever ran into a problem that I just couldn’t wrap my head around, I could always count on his channel as he consistently offers videos that break down the problem that guides you to your solution.
Today, we are looking at LeetCode 238: Product of Array Except Self
LeetCode 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 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
Input: nums = [1,2,3,4]
Output: [24,12,8,6]For 1: Product of others = 2 × 3 × 4 → 24
For 2: Product of others = 1 × 3 × 4 → 12
For 3: Product of others = 1 × 2 × 4 → 8
For 4: Product of others = 1 × 2 × 3 → 6
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]For every position except 0: The product will be 0 due to multiplication by 0.
For 0: Product of everything else = -1 × 1 × -3 × 3 = 9
Initial Intuition
At first glance, the idea of computing the product of the entire array and then dividing the total product by the element at each index might arise. However, the problem explicitly states that using the division operation is not allowed.
Another brute force approach might involve iterating through each index i and calculating the product of all numbers except the number at index i. This approach would result in a time complexity of O(n^2), which is not optimal.
Optimized Approach
The key insight here is that for each number nums[i], the product of all numbers except itself can be seen as the product of:
- All numbers before it (nums[0] to nums[i-1]).
- All numbers after it (nums[i+1] to nums[n-1]).
By iteratively computing products for both sections, we avoid the need for the division operation and keep our solution within the O(n) time constraint. To illustrate, consider the array [1,2,3,4]. For the second element, 2, the product would be 1 * 3 * 4.
- Starting from the leftmost index, traverse the array and compute the left-side product for each number. Store these products in the output array.
- Beginning with the rightmost index, traverse the array backward and compute the right-side product for each number. Multiply this with the existing value (the left-side product) in the output array.
Solution
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
# Create an output array initialized with ones.
output = [1] * n
# Calculate the left-side product for each number.
left_product = 1
for i in range(1, n):
left_product *= nums[i - 1]
output[i] *= left_product
# Calculate the right-side product for each number and multiply it with the corresponding left-side product.
right_product = 1
for i in range(n - 2, -1, -1):
right_product *= nums[i + 1]
output[i] *= right_product
return outputTime and Space Complexity
The time complexity of this solution is O(n) as each of the two loops runs for ‘n’ iterations, leading to a total of 2n iterations, which is linear with respect to the input size.
The space complexity is O(1) if we don’t count the output array, as the problem statement suggests. This is because we use a constant amount of space beyond the output array, regardless of the input size.