[LeetCode] 179. Largest Number

Problem : https://leetcode.com/problems/largest-number/

Time Complexity : O ( N Log N )

from functools import cmp_to_key
from functools import reduce

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # a + b > b + a means (a+b) is larger than (b+a) in dictionary order
        dictionaryOrder = cmp_to_key(lambda a, b : 1 if int(a + b) > int(b + a) else -1)
        
        # sort nums in dictionary ascending order
        # concat all numbers from the largest to the smallest. 
        # return 0 if the first digit of final result is '0'
        result = reduce(lambda accumulate, n : accumulate + n, \
                        reversed(sorted(map(str, nums), key = dictionaryOrder)), \
                        '')
           
        return result if result[0] != '0' else '0'

[LeetCode] 174. Dungeon Game

Problem : https://leetcode.com/problems/dungeon-game/

Memorization Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        @lru_cache(maxsize = None)
        def helper(y, x):
            if y >= row or x >= col:
                return 2 ** 31 - 1
            
            if y == row -1 and x == col - 1:
                return max(1, 1 - dungeon[y][x])
            
            # only need to have 1 health point to survive 
            return max(1, min(helper(y,x+1), helper(y+1, x)) - dungeon[y][x])

        return helper(0, 0)

DP Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        max_int = 2 ** 31 - 1
        
        dp = [[max_int] * (col+1) for _ in range(row + 1)]
        
        dp[row][col-1] = 1
        dp[row-1][col] = 1
        
        for y in reversed(range(row)):
            for x in reversed(range(col)):
                dp[y][x] = max(1, min(dp[y+1][x], dp[y][x+1]) - dungeon[y][x])
        
        return dp[0][0]

[LeetCode] 173. Binary Search Tree Iterator

Problem : https://leetcode.com/problems/binary-search-tree-iterator/

Because in-order traverse BST can generate a ascending sequence.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        
        def inorder(node):
            if node:
                yield from inorder(node.right)
                yield node.val
                yield from inorder(node.left)
        
        self.nodes = list(inorder(root))

    def next(self) -> int:
        return self.nodes.pop()

    def hasNext(self) -> bool:
        return self.nodes


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

A stack based iterative solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = [root] if root else []
        

    def next(self) -> int:
        node = self.stack[-1]
        
        while node.left:
            self.stack.append(node.left)
            tmp = node.left
            node.left = None
            node = tmp
        
        # pop the parent node
        self.stack.pop()
        
        if node.right:
            self.stack.append(node.right)
            node.right = None
        
        return node.val
        

    def hasNext(self) -> bool:
        return self.stack
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Edited on 04/22/2021. Refactor the recursive and iterative solution.

[LeetCode] 172. Factorial Trailing Zeroes

Problem : https://leetcode.com/problems/factorial-trailing-zeroes/

number of trailing zero = number of 10 

Because 2 * 5 = 10 and number of 5 is less than the number of 2.

This problem equals how many 5 in the given number.

class Solution:
    def trailingZeroes(self, n: int) -> int:
        return n // 5 + self.trailingZeroes(n // 5) if n > 0 else 0

[LeetCode] 171. Excel Sheet Column Number

Problem : https://leetcode.com/problems/excel-sheet-column-number/

This problem equals to convert 27 based number to 10 based number.

from functools import reduce

class Solution:
    def titleToNumber(self, s: str) -> int:
        return reduce(lambda x, y: x * 26 + ord(y) - ord('A') + 1, s, 0)

[LeetCode] 169. Majority Element

Problem : https://leetcode.com/problems/majority-element/

Since majority element appears more than n/2 times, number[n/2] in the sorted array must be the majority element.

Time Complexity = O ( N * Log N )

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        return sorted(nums)[n // 2]

Use counter to filter out minority element.

Time Complexity = O ( N )

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        result = nums[0]
        count = 1
        
        for i in range(1, len(nums)):
            if nums[i] == result:
                count += 1
            else:
                count -= 1
            
            if count == 0:
                result = nums[i]
                count = 1
        
        return result

[LeetCode] 168. Excel Sheet Column Title

Problem : https://leetcode.com/problems/excel-sheet-column-title/

Time Complexity = O ( Log N )

class Solution:
    def convertToTitle(self, n: int) -> str:
        letters = [chr(i) for i in range(ord('A'),ord('Z')+1)]
        
        result = ""
        
        while n > 0:
            # use n - 1 because letters is zero-based array
            i = (n-1) % 26
            
            result += letters[i]
            n = (n-1) // 26
        
        return result[::-1]

[LeetCode] 167. Two Sum II - Input array is sorted

Problem : https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Time Complexity = O ( Log N )

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        
        while left < right:
            tmp = numbers[left] + numbers[right]
            
            if tmp < target:
                left += 1
            elif tmp > target:
                right -= 1
            else:
                return [left+1, right+1]

[LeetCode] 166. Fraction to Recurring Decimal

Problem : https://leetcode.com/problems/fraction-to-recurring-decimal/

Simulator long division process to calculate fraction result.

Because the same numerator always leads to the same fraction result. 

Use hash table to save numerator encountered to avoid repeating fractional part.

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        negative = (numerator < 0) ^ (denominator < 0)
        
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        result = str(numerator // denominator)
        
        if numerator % denominator == 0:
            return "-" + result if negative and numerator != 0  else result
        
        numerator = numerator % denominator
        numerator *= 10
        
        visited = {}
        
        result += "."
        
        while numerator > 0:
            
            if numerator not in visited:
                visited[numerator] = len(result)
            else:
                prefix = result[:visited[numerator]] + '('
                appendix = result[visited[numerator]:] + ')'
                result = prefix + appendix
                break
            
            if numerator > denominator:
                result += str(numerator // denominator)
                numerator = numerator % denominator
            else:
                result += '0'
            
            numerator *= 10
        
        return "-" + result if negative else result

Edited on 03/04/2021. A simpler implementation.

[LeetCode] 165. Compare Version Numbers

Problem : https://leetcode.com/problems/compare-version-numbers/

Step 1, split version string by '.' to get integer on each level

Step 2, recursively compare integer on each level.  By default, integer on each level = 0

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = list(map(int, version1.split('.')))
        v2 = list(map(int, version2.split('.')))
        
        def compare(level):
            left = v1[level] if level < len(v1) else 0
            right = v2[level] if level < len(v2) else 0
            
            if left < right:
                return -1
            
            if left > right:
                return 1
            
            return 0 if level >= len(v1) and level >= len(v2) else compare(level+1)
                
        return compare(0)