238. Product of Array Except Self

Description

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

Note that the solution needs to run in O(N) time and division can not be used.

Solution

Given an input array of nums =[2,3,4,5] the output array is calculated as follows:

index 0 = nums[1] * nums[2] * nums[3] (3 * 4 * 5 = 60)

index 1 = nums[0] * nums[2] * nums[3] (2 * 4 * 5 = 40)

index 2 = nums[0] * nums[1] * nums[3] (2 * 3 * 5 = 30)

index 3 = nums[0] * nums[1] * nums[2] (2 * 3 * 4 = 24)

Result is [60, 40, 30, 24]

Since the solution needs to run in O(N) time we cannot use nested loops. However, we can use multiple loops sequentially as that is a O(N) runtime. For example, two sequential loops would be O(N) + O(N) which reduces to O(N).

Looking at how each index is calculated, the pattern is to multiply the numbers on the left side of the current index with the numbers on the right side of the index. In the diagram below the greyed out cell is the current element.

nums[0] = (no left side) (3 * 4 * 5)

nums[1] = (2) * (4 * 5)

nums[2] = (2 * 3) * (5)

nums[3] = (2 * 3 * 4) (no right side)

And a longer example where nums = [10, 20, 30, 40, 50, 60, 70, 80, 90]

nums[4] = (10 * 20 * 30 * 40) * (60 * 70 * 80 * 90)

This logic can be broken into two loops. The first loop will multiply the numbers to the left of the current index. These values are stored in a "left" array.

Note that the value of left[i] is the cumulative product. For example:

the value of a left element is the cumulative product

Using nums = [10, 20, 30, 40, 50, 60, 70, 80, 90] as an example:

left[0] = 1

left[1] = 10 * 1

left[2] = 20 * (10 * 1)

left[3] = 30 * ( 20 * (10 * 1))

left[4] = 40 * (30 * ( 20 * (10 * 1)))

and so on...

Note that the first element does not have a left side to multiply. The first element only has right side multiplication. So, in the left array, the first element will default to 1. A similar situation happens for the last element, except it has no right side to multiply. So the last element in the right array will default to 1.

left = [1] * len(nums)

# [2, 3, 4, 5]
for i in range(1, len(nums)):
    left[i] = nums[i-1] * left[i-1]
# left = [1,2, 6, 24]

The second loop will multiply numbers to the right of the current index. The for loop starts at the 2nd to last element, because the last element will be 1 for the reasons stated above.

right = [1] * len(nums)

for i in range(len(nums) - 2, -1, -1):
    right[i] = nums[i+1] * right[i+1]
# right = [60, 20, 5, 1]

Then we multiply the two arrays together to get the result.

Example: nums = [2, 3, 4, 5]

left = [1, 2, 6, 24]

right = [60, 20, 5, 1]

answer = [60, 40, 30, 24]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left = [1] * len(nums)
        right = [1] * len(nums)
        answer = [1] * len(nums)

        # nums = [2, 3, 4, 5]
        for i in range(1, len(nums)):
            left[i] = nums[i-1] * left[i-1]
        # left = [1,2, 6, 24]
        
        for i in range(len(nums) - 2, -1, -1):
            right[i] = nums[i+1] * right[i+1]
        # right = [60, 20, 5, 1]
        
        for i in range(len(nums)):
            answer[i] = left[i] * right[i]
        # answer = [60, 40, 30, 24]
        return answer

The above solution uses three loops. This can be reduced to two loops by combining the last two loops.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left = [1] * len(nums)
        right = [1] * len(nums)
        answer = [1] * len(nums)

        for i in range(1, len(nums)):
            left[i] = nums[i-1] * left[i-1]
        
        for i in range(len(nums) - 2, -1, -1):
            right[i] = nums[i+1] * right[i+1]
            answer[i] = left[i] * right[i]
        
        # The for loop above calculated the answer for all elements but the last 
        # one. This is because in calculating the right side array we don't 
        # calculate the last element because it defaults to 1. So the last element
        # in the answer array is the last element of the left array (which is the
        # product of all the left side elements.
        answer[-1] = left[-1]
        return answer
                

The question then asks for an optimal solution of "Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)"

We can build on the above solution. The optimized solution is similar to the above solution with the following changes:

• The left and right arrays are removed

• The first loop remains the same, except the left array is replaced with the answer array

• For the second loop, we still want to iterate backward over the nums array. But now we are condensing the creation of the right array and multiplying it with the answer array in this second loop. The tally variable is used keep the running product of the nums array (this is the right side calculation).

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = [1] * len(nums)
        for i in range(1, len(nums)):
            answer[i] = answer[i - 1] * nums[i - 1]

        tally = 1
        for i in range(len(nums) - 2, -1, -1):
            tally *= nums[i + 1]
            answer[i] = answer[i] * tally
        return answer