We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Product of Array Except Self

Number: 238

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, Microsoft, Bloomberg, Goldman Sachs, PayPal, Fractal Analytics, Asana, Uber, Apple, Oracle, Flipkart, Yahoo, Intuit, Yandex, TikTok, Accenture, IBM, Turing, Warnermedia, Tekion, Autodesk, Sigmoid, Infosys, Adobe, eBay, Visa, Cisco, Docusign, LinkedIn

Problem 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 challenge must be solved in O(n) time and without using the division operation. Additionally, aim to solve the problem with O(1) extra space complexity (excluding the output array).

Key Insights

  • The product for each index can be computed by multiplying the product of all numbers to the left and the product of all numbers to the right of that index.
  • Division is not allowed, so we must compute the cumulative products explicitly.
  • Create two passes: one forward pass for prefix products and one backward pass for suffix products.
  • Use the output array to store the cumulative product values, achieving O(1) extra space by not using additional arrays.

Space and Time Complexity

Time Complexity: O(n) because we iterate through the array twice. Space Complexity: O(1) extra space (excluding the output array).

Solution

The approach uses two passes over the input array:

  1. Initialize the answer array and fill it with prefix products. For each index i, answer[i] contains the product of all elements before i.
  2. Traverse the array from the end using a running suffix product. Update the answer array by multiplying the current suffix product with the prefix product already stored. This method leverages an output array to store intermediate results and uses a temporary variable for the suffix product, ensuring constant extra space.

Code Solutions

# Function to compute product of array except self
def productExceptSelf(nums):
    n = len(nums)
    # Initialize the output array with 1s for prefix multiplication
    answer = [1] * n

    # Compute prefix products: for each element answer[i] holds the product of all numbers left of i
    prefix_product = 1
    for i in range(n):
        answer[i] = prefix_product  # store prefix product so far
        prefix_product *= nums[i]   # update the prefix product

    # Compute suffix products and multiply with prefix products in answer array
    suffix_product = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix_product  # multiply current answer with suffix product
        suffix_product *= nums[i]     # update the suffix product

    return answer

# Example usage
nums = [1, 2, 3, 4]
print(productExceptSelf(nums))  # Output: [24, 12, 8, 6]
← Back to All Questions