LeetCode 238. Product of Array Except Self

This post was migrated from Tistory. You can find the original here.

Problem

https://leetcode.com/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

Approach

I couldn’t come up with an idea for solving this in O(n) without using division. I peeked at the discussion, saw the words “left” and “right,” and it clicked.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_dp, right_dp = [0], [0]
        left_product, right_product = 1, 1
        for i in nums:
            left_product *= i
            left_dp.append(left_product)

        for i in range(len(nums)-1, -1, -1):
            right_product *= nums[i]
            right_dp.append(right_product)
        
        result = []
        leng = len(nums)
        for i in range(leng):
            if i-1 < 0:
                left = 1
            else:
                left = left_dp[i]
            
            if i+1 >= leng:
                right = 1
            else:
                right = right_dp[leng-i-1]
            result.append(left * right)
        return result

I first built left_dp and right_dp, then multiplied the left and right dp values around each index.

Solving it this way, the runtime percentile was a bit disappointing.

Looking at another solution, it built the result without that final for loop. Thinking about it, for a nums of length 4,

if left covers 1 slot, right covers 2,

if left covers 2 slots, right covers 1,

…

it’s already determined, so you don’t actually need a separate for loop at the end to build the result.

Revised code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        dp = [1]
        left_product, right_product = 1, 1
        leng = len(nums)
        for i in range(leng-1):
            left_product *= nums[i]
            dp.append(left_product)

        # print(dp)
        for i in range(len(nums)-1, 0, -1):
            right_product *= nums[i]
            dp[i-1] *= right_product
        
        return dp