238. Product of Array Except Self

[sophryu99]

Approach

https://leetcode.com/problems/product-of-array-except-self/

The key is to write an algorithm in O(n) time without using the division operation. If division operation was allowed, the simplest approach would have been getting the product of every elements in the array, and dividing by ith element.

1. Initialize a base var as 1. This var will contain the incremental product throughout the array scan
2. Traverse through the list, append the element i to new arr, update the base var as base * arr[i].
3. Traverse through the list from backwards, update arr[i] = arr[i] base, then update the base var as `base nums[i]`
4. Return ans array

def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = []
        n = len(nums)
        base = 1

        # Scan from the left
        for i in range(n):
            ans.append(base)
            base = base * nums[i]

        # Scan from the right
        base = 1
        for i in range(n-1,-1,-1):
            ans[i] = ans[i] * base
            base = base * nums[i]
        return ans

n: length of the array

• Time Complexity: O(n) Twice of linear scan through the array
• Space Complexity: O(n) answer array