Product of Array Except Self LeetCode #238 [Solved in Python]

Product of Array Except Self LeetCode problem’s task is to return an answer array where answer[i] is the product of all elements except itself.

The task is to return an array called answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The catch is that we must solve this problem in O(n) time complexity without using the division operation.

Question:

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.

Let’s break this down with an example:

Example:

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

For the first element in the output (answer[0]), we need to calculate the product of all elements in nums except nums[0], which is 2 * 3 * 4 = 24. Similarly, we calculate the other elements of the output array.

The key challenge here is to find an efficient solution that satisfies the given constraints.

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 <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Understanding the Constraints

Before diving into the solution, let’s understand the constraints provided in the problem statement:

1. The length of the input array nums is between 2 and 105. This means we may have a relatively large input size, so our solution should be efficient.
2. The values in nums can range from -30 to 30. We need to handle both positive and negative integers within this range.
3. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. This ensures that the product won’t result in overflow.

Now that we have a clear understanding of the problem and its constraints, let’s explore an efficient approach to solving it.

Product of Array Except Self – Efficient Solution

To solve this problem efficiently, we can follow these steps:

Step 1: Calculate Prefix Products

We’ll start by calculating the product of all elements to the left of each element in the nums array.

We’ll store these prefix products in a new array called prefix_products.

This can be done in a single pass through the nums array.

Step 2: Calculate Postfix Products and Populate answer Array

Next, we’ll calculate the product of all elements to the right of each element in the nums array while populating the answer array.

To do this, we’ll traverse the nums array from right to left, maintaining a variable postfix_product that keeps track of the product of elements to the right.

We’ll also use an index i to access elements in nums and prefix_products.

For each element at index i, we’ll multiply the corresponding prefix product from prefix_products (which represents the product of elements to the left of nums[i]) by the current postfix_product (which represents the product of elements to the right of nums[i]).

The result will be stored in the answer array at index i. Additionally, we’ll update the postfix_product by multiplying it with the current element in nums.

Step 3: Return the answer Array

Finally, we’ll have the answer array populated with the desired values, and we can return it as the result.

Let’s implement this efficient approach in Python code:

def productExceptSelf(self, nums: List[int]) -> List[int]:
    # Calculate the prefix products
    n = len(nums)
    prefix_products = [1] * n
    prefix_product = 1
    for i in range(n):
        prefix_products[i] = prefix_product
        prefix_product *= nums[i]

    # Calculate postfix products and populate the answer array
    postfix_product = 1
    answer = [0] * n  # Initialize the answer array
    for i in range(n - 1, -1, -1):
        answer[i] = prefix_products[i] * postfix_product
        postfix_product *= nums[i]

    return answer

This code efficiently solves the problem by avoiding unnecessary division operations and ensures O(n) time complexity and O(1) space complexity (excluding the space required for the answer array).

Time and Space Complexity

• Time Complexity: O(n) – We perform two passes through the nums array, each taking O(n) time.
• Space Complexity: O(1) – Excluding the space required for the answer array, our algorithm uses a constant amount of extra space.

Reasoning Behind Our Approach

The reasoning behind this approach is based on the observation that we can compute the product of all elements except nums[i] by multiplying the product of elements to the left of nums[i] (prefix product) with the product of elements to the right of nums[i] (postfix product).

By precomputing the prefix products and then calculating the postfix products on the fly while populating the answer array, we achieve the desired result with optimal time and space complexity.

Related Interview Questions

• Top K Frequent Elements LeetCode Problem
• Two Sum II LeetCode Problem
• Group Anagrams LeetCode Problem
• Valid Palindrome LeetCode Problem
• Valid Sudoku LeetCode Problem

Conclusion

In this blog post, we tackled the Product of Array Except Self LeetCode problem (Problem 238) efficiently.

We provided a detailed problem overview, discussed the constraints, and presented an optimized solution that meets the requirements of O(n) time complexity without using the division operation.

By calculating prefix and postfix products and populating the answer array in two passes, we successfully solved this problem.

Feel free to comment, ask questions, make suggestions, and share this content with others.

Happy coding!