Product of Array Except Self

Question

Given an integer array, return an array where each element is the product of all other elements. Solve without using division and in O(n) time. A Meta coding interview staple.

Codemia · Accepted Answer

The problem requires us to calculate the product of all elements in an array except the current element for each position, without using division and in O(n) time. The best approach to solve this problem is to utilize a two-pass algorithm. The first pass will calculate the products of all elements to the left of each index, and the second pass will calculate the products of all elements to the right of each index. This two-pass approach efficiently combines both left and right products to achieve the desired result.

1. Initialize an output array of the same length as the input array, filled with ones. This will store the final product values.
2. Create a variable `left_product` initialized to 1. 
3. In the first loop (0 to n-1), update the output array such that each position `i` contains the product of all elements to its left. After updating output[i], update `left_product` by multiplying it with the current input element.

Example with input [1, 2, 3, 4]:
   - For i = 0: output[0] = 1 (no left elements)
   - For i = 1: output[1] = 1 * 1 = 1
   - For i = 2: output[2] = 1 * 2 = 2
   - For i = 3: output[3] = 2 * 3 = 6

4. Initialize a variable `right_product` to 1. 
5. In the second loop (n-1 to 0), update the output array such that each position `i` multiplies its current value by the product of all elements to its right.

Continuing the example:
   - For i = 3: output[3] = 6 * 1 = 6
   - For i = 2: output[2] = 2 * 4 = 8
   - For i = 1: output[1] = 1 * 12 = 12
   - For i = 0: output[0] = 1 * 24 = 24

The final output will be [24, 12, 8, 6].

Here is the Python code implementing the above approach:
```python
def product_except_self(nums):
    n = len(nums)
    output = [1] * n

left_product = 1
    for i in range(n):
        output[i] = left_product
        left_product *= nums[i]

right_product = 1
    for i in range(n - 1, -1, -1):
        output[i] *= right_product
        right_product *= nums[i]

return output
```
This solution maintains the product of elements without using division and achieves the desired output in O(n) time.

The time complexity of this solution is O(n) because we traverse the input array twice: once for the left products and once for the right products. The space complexity is O(1) if we do not count the output array, otherwise O(n) due to the output array that stores the result. This is efficient given the constraints, as we are not allowed to use division and must handle the product accumulation in linear time.

1. **Single Element Array**: For input [5], the output should be [1] since there are no other elements to multiply with.
2. **Array with Zeros**: If the input is [0, 4, 0], the output should be [0, 0, 0] because the product of the remaining elements for each position is zero.
3. **Array with Negative Numbers**: For input [-1, -2, -3, -4], the output should be [-24, -12, -8, -6], demonstrating that the sign and magnitude of the numbers are correctly accounted for in the product calculation.

Product of Array Except Self

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string