algoadvance

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 problem should be solved without using division and in O(n) time complexity.

Clarifying Questions

1. Q: Can the input array nums contain negative numbers?
   • A: Yes, the input array can contain negative numbers.
2. Q: Is the input array guaranteed to have at least one element?
   • A: Yes, the input array will have at least one element.
3. Q: Can the input array contain zeros?
   • A: Yes, the input array can contain zeros.

Strategy

To solve this problem, we can leverage two auxiliary arrays: left_products and right_products.

1. Left Products:
   • left_products[i] will store the product of all elements to the left of index i.
   • Initialize left_products[0] to 1 because there are no elements to the left of the first element.
2. Right Products:
   • right_products[i] will store the product of all elements to the right of index i.
   • Initialize right_products[length-1] to 1 because there are no elements to the right of the last element.
3. Combine:
   • Finally, compute the result for each index i by multiplying left_products[i] and right_products[i].

This approach ensures that each element at index i is a product of all elements except nums[i] and also ensures the solution is done in O(n) time.

Code

Here’s the implementation of the described strategy in Python:

def product_except_self(nums):
    n = len(nums)

    # Initialize the arrays with default values of 1
    left_products = [1] * n
    right_products = [1] * n
    answer = [0] * n

    # Calculate the left products
    for i in range(1, n):
        left_products[i] = left_products[i - 1] * nums[i - 1]

    # Calculate the right products
    for i in range(n - 2, -1, -1):
        right_products[i] = right_products[i + 1] * nums[i + 1]

    # Calculate the answer array by multiplying left and right products
    for i in range(n):
        answer[i] = left_products[i] * right_products[i]

    return answer

Time Complexity

• Time Complexity: O(n)
  • This results from two traversals to fill left_products and right_products, and one more traversal to fill the answer array.
• Space Complexity: O(n)
  • Additional space is used for the left_products, right_products, and answer arrays. If we consider the result array as part of the output (which is usually considered as not extra space), the space complexity can be O(n) too due to the use of the auxiliary arrays.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?