23.03.11 Today’s Leetcode

109. Convert Sorted List to Binary Search Tree (medium)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next


        def dfs(start, end):
            if start >= end:
                return None
            nonlocal arr
            mid = (start + end) // 2
            node = TreeNode(arr[mid])
            node.left = dfs(start, mid)
            node.right = dfs(mid + 1, end)
            return node
        
        return dfs(0, len(arr))

2196. Create Binary Tree From Descriptions (medium)

class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        d = {}
        children = set()
        for par, child, isLeft in descriptions:
            if par not in d:
                d[par] = TreeNode(par)
            if child not in d:
                d[child] = TreeNode(child)
            
            children.add(child)
            if isLeft == 1:
                d[par].left = d[child]
            else:
                d[par].right = d[child]
            
        for par, _, _ in descriptions:
            if par not in children:
                return d[par]
        return None

215. Kth Largest Element in an Array (medium)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        temp = []
        for num in nums:
            heappush(temp, -num)
        
        res = 0
        for i in range(k):
            res = -heappop(temp)
        return res

219. Contains Duplicate II (easy)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d = defaultdict(list)
        for index, num in enumerate(nums):
            if len(d[num]) >= 1 and index - d[num][-1] <= k:
                return True
            d[num].append(index)
        
        return False

        

221. Maximal Square (medium)

DP Approach

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix is None or len(matrix) < 1:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        dp = [[0]*(cols + 1) for _ in range(rows + 1)]
        max_side = 0
        
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == '1':
                    dp[r + 1][c + 1] = min(dp[r][c], dp[r + 1][c], dp[r][c + 1]) + 1 
                    # Be careful of the indexing since dp grid has additional row and column
                    max_side = max(max_side, dp[r + 1][c + 1])
                
        return max_side * max_side