Product of Array Except Self - LeetCode Problem

Problem Description

The "Product of Array Except Self" problem statement is as follows: Given an array of integers, return an array where each element is the product of all the elements in the original array except for the one at its index.

Solution

The solution to this problem can be broken down into a few simple steps:

1. We first create an empty result array with the same length as the input array.

2. We then initialize two variables, left_product and right_product, both set to 1.

3. We loop through the input array from left to right, and for each element in the array, we set the corresponding element in the result array to the current left_product value, and then multiply left_product by the current element.

4. We then loop through the input array from right to left, and for each element in the array, we multiply the corresponding element in the result array by the current right_product value and then multiply right_product by the current element.

5. Finally, we return the result array.

Here is the code for the solution:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        left_product, right_product = 1, 1

        # loop through the array from left to right
        for i in range(n):
            result[i] *= left_product
            left_product *= nums[i]

        # loop through the array from right to left
        for i in range(n-1, -1, -1):
            result[i] *= right_product
            right_product *= nums[i]

        return result

Complexity Analysis

The time complexity of this solution is O(n) since we loop through the input array twice, but each loop is only O(n) in time complexity.

The space complexity is also O(n) since we create an additional result array of size n.

Conclusion

In conclusion, the Product of Array Except Self problem can be solved using a simple algorithm that loops through the input array twice, and stores the left and right products of each element in the result array. This is a great problem for beginners to practice their array manipulation skills and can be solved in a relatively short amount of time. Happy coding! 😎