Jobs

Interviews

Discussions

Product of Array Except Self

Medium

Disney

0 views

Topics:

ArraysTwo Pointers

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.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Product of Array Except Self

Medium

Disney

0 views

Topics:

ArraysTwo Pointers

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.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected size range of the input array `nums`?
Can the input array `nums` contain zero or negative numbers?
Is the input array `nums` guaranteed to fit within the memory constraints?
If there are multiple zeros in the input array, what should the output array contain?
Is the input array mutable, or should I treat it as immutable?

Brute Force Solution

Approach

The brute-force way to solve this problem is pretty straightforward. For each position in the final answer, we'll calculate the product of all the other numbers in the original set. We will do this for every position.

Here's how the algorithm would work step-by-step:

For the first position, multiply all the numbers together, *except* for the number that's originally in the first position.
Put that product in the first position of a new result.
Now, do the same thing for the second position. Multiply all the numbers together, skipping the one that was originally in the second position.
Put that product in the second position of the result.
Keep repeating this process. For each position, calculate the product of all other numbers and put that product in the corresponding position of the result.
Once you've done this for every single position, you'll have your final result.

Code Implementation

def product_of_array_except_self_brute_force(numbers):
    number_of_elements = len(numbers)
    result_array = [1] * number_of_elements

    for index in range(number_of_elements):
        product = 1

        # Iterate through the array to calc. product of all other numbers.
        for second_index in range(number_of_elements):
            if index != second_index:
                product *= numbers[second_index]

        # Store the product at the current index.
        result_array[index] = product

    return result_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through the input array of size n. For each element, it calculates the product of all other elements, requiring another iteration of approximately n operations. Thus, the overall complexity is derived from performing an n operation for each of the n elements in the input array. This results in approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm calculates each element of the result array individually, without retaining temporary collections of items. The steps describe overwriting a single position in a result with a calculated product, without referring to intermediate data structures. The algorithm has no reliance on extra data structures that scale with the size of the input array. Since the space usage does not grow with input size (N), the space complexity is constant.

Optimal Solution

Approach

The efficient way to solve this problem avoids recalculating products repeatedly. Instead, it smartly builds up the answer by calculating prefix and suffix products. This approach reduces a lot of unnecessary work and gives you the final answer much faster.

Here's how the algorithm would work step-by-step:

First, calculate the product of all the numbers *before* each position. Store these in a new list.
Next, calculate the product of all the numbers *after* each position. Store these in another new list.
Finally, to get the result for each position, simply multiply the product of numbers before it with the product of numbers after it. This gives you the product of all numbers except the number at that position.

Code Implementation

def product_except_self(numbers):
    number_count = len(numbers)
    prefix_products = [1] * number_count
    suffix_products = [1] * number_count
    result = [1] * number_count

    # Calculate prefix products.
    # Each element is the product of all elements before it.
    for i in range(1, number_count):
        prefix_products[i] = prefix_products[i - 1] * numbers[i - 1]

    # Calculate suffix products.
    # Each element is the product of all elements after it.
    for i in range(number_count - 2, -1, -1):
        suffix_products[i] = suffix_products[i + 1] * numbers[i + 1]

    # Calculate the final result by multiplying prefix and suffix products.
    for i in range(number_count):
        result[i] = prefix_products[i] * suffix_products[i]

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n three times. The first iteration calculates prefix products, the second calculates suffix products, and the third calculates the final result by multiplying corresponding prefix and suffix products. Each of these iterations performs a constant amount of work for each element in nums. Since the number of operations grows linearly with the input size n, the time complexity is O(n).

Space Complexity

O(N) – The algorithm creates two new lists to store prefix products and suffix products respectively. Both the prefix products list and the suffix products list each have a size equal to the number of elements in the input array (N). Therefore, the auxiliary space required is proportional to the size of the input, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException as the problem has no valid output for this input.
Array with a single element	Return an array containing only the value 1, as the product of elements excluding the single element is 1.
Array with two elements	Calculate the products and return accordingly in a new array.
Array contains a single zero	All other elements in the result array will be zero, except the element at the index of the zero, which will be the product of all other non-zero elements.
Array contains multiple zeros	The entire result array should be filled with zeros since the product of the array excluding any element will always be zero.
Array with large numbers potentially leading to integer overflow	Use long data type to store intermediate products, or if forbidden by the problem statement, implement overflow detection and handle it appropriately.
Array contains negative numbers	The algorithm should correctly handle negative numbers by multiplying them into the prefix and suffix products.
Large array size affecting time complexity	The solution should aim for O(n) time complexity to handle large arrays efficiently; solutions with nested loops would be unacceptable.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected size range of the input array `nums`?
Can the input array `nums` contain zero or negative numbers?
Is the input array `nums` guaranteed to fit within the memory constraints?
If there are multiple zeros in the input array, what should the output array contain?
Is the input array mutable, or should I treat it as immutable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For the first position, multiply all the numbers together, *except* for the number that's originally in the first position.
Put that product in the first position of a new result.
Now, do the same thing for the second position. Multiply all the numbers together, skipping the one that was originally in the second position.
Put that product in the second position of the result.
Keep repeating this process. For each position, calculate the product of all other numbers and put that product in the corresponding position of the result.
Once you've done this for every single position, you'll have your final result.

Code Implementation

def product_of_array_except_self_brute_force(numbers):
    number_of_elements = len(numbers)
    result_array = [1] * number_of_elements

    for index in range(number_of_elements):
        product = 1

        # Iterate through the array to calc. product of all other numbers.
        for second_index in range(number_of_elements):
            if index != second_index:
                product *= numbers[second_index]

        # Store the product at the current index.
        result_array[index] = product

    return result_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the product of all the numbers *before* each position. Store these in a new list.
Next, calculate the product of all the numbers *after* each position. Store these in another new list.
Finally, to get the result for each position, simply multiply the product of numbers before it with the product of numbers after it. This gives you the product of all numbers except the number at that position.

Code Implementation

def product_except_self(numbers):
    number_count = len(numbers)
    prefix_products = [1] * number_count
    suffix_products = [1] * number_count
    result = [1] * number_count

    # Calculate prefix products.
    # Each element is the product of all elements before it.
    for i in range(1, number_count):
        prefix_products[i] = prefix_products[i - 1] * numbers[i - 1]

    # Calculate suffix products.
    # Each element is the product of all elements after it.
    for i in range(number_count - 2, -1, -1):
        suffix_products[i] = suffix_products[i + 1] * numbers[i + 1]

    # Calculate the final result by multiplying prefix and suffix products.
    for i in range(number_count):
        result[i] = prefix_products[i] * suffix_products[i]

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array or throw an IllegalArgumentException as the problem has no valid output for this input.
Array with a single element	Return an array containing only the value 1, as the product of elements excluding the single element is 1.
Array with two elements	Calculate the products and return accordingly in a new array.
Array contains a single zero	All other elements in the result array will be zero, except the element at the index of the zero, which will be the product of all other non-zero elements.
Array contains multiple zeros	The entire result array should be filled with zeros since the product of the array excluding any element will always be zero.
Array with large numbers potentially leading to integer overflow	Use long data type to store intermediate products, or if forbidden by the problem statement, implement overflow detection and handle it appropriately.
Array contains negative numbers	The algorithm should correctly handle negative numbers by multiplying them into the prefix and suffix products.
Large array size affecting time complexity	The solution should aim for O(n) time complexity to handle large arrays efficiently; solutions with nested loops would be unacceptable.