NVIDIA, LeetCode | Dong WANG

238. Product of Array Except Self

When there are no elements to multiple at a certain position, the product should be initialized as 1, since 1 is the identity element for multiplication and does not affect the overall result. That is the reason why left_prod and right_prod are both initialized as 1.

from typing import List
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_prod = 1
        right_prod = 1
        result = []
        for i in range(len(nums)):
            # append the left_prod first, update the left_prod with current element second to except self
            result.append(left_prod)
            left_prod *= nums[i]
        
        for i in range(len(nums)-1, -1, -1):
            result[i] *= right_prod
            right_prod *= nums[i]
        return result

49. Group Anagrams

When you’re comparing elements in a list pairwise, hashmap could reduce the time complexity from O(n^2) to O(n) using a key with distinguishing or grouping capability.

Anagram: same after sorting

from typing import List
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = {}
        for word in strs:
            key = ''.join(sorted(word)) # sorted(word) will return a list
            if key in hashmap:
                hashmap[key].append(word)
            else:
                hashmap[key] = [word]
        return list(hashmap.values()) 
        # list(hashmap.keys())
        # list(hashmap.values()) 
        # list(hashmap.items()) List[tuple]

Enjoy Reading This Article?