A. Evaluate Boolean Binary Tree (opens new window)

DFS

DETAILS

def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if root.val == 0:
                return False
            elif root.val == 1:
                return True
            elif root.val == 2:
                return dfs(root.left) or dfs(root.right)
            else:
                return dfs(root.left) and dfs(root.right)
        
        return dfs(root)

B. The Latest Time to Catch a Bus (opens new window)

DETAILS

def latestTimeCatchTheBus(self, B: List[int], P: List[int], C: int) -> int:
        B.sort()
        P.sort()
        m, n, j, curr = len(B), len(P), 0, 0
        for b in B:
            curr = 0
            while j < n and P[j] <= b and curr < C:
                j += 1
                curr += 1
                
        ans = b if curr != C else P[j - 1]
        P = set(P)
        while ans in P:
            ans -= 1
        return ans

C. Minimum Sum of Squared Difference (opens new window)

DETAILS

def minSumSquareDiff(self, A: List[int], B: List[int], k1: int, k2: int) -> int:
        n, tot = len(A), k1 + k2
        pq = [-abs(A[i] - B[i]) for i in range(n)]
        if k1 + k2 > abs(sum(pq)): return 0
        heapq.heapify(pq)
        while tot > 0:
            n = len(pq)
            curr = -heapq.heappop(pq)
            gap = max(tot // n, 1)
            curr -= gap
            tot -= gap
            heapq.heappush(pq, -curr)
        
        return sum(x ** 2 for x in pq)

D. Subarray With Elements Greater Than Varying Threshold (opens new window)

DETAILS

def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        nums, stack = [0] + nums + [0], [0]
        for i in range(1,len(nums)):
            while nums[i] < nums[stack[-1]]:
                tmp = nums[stack.pop()]
                if tmp > threshold // (i - stack[-1] - 1):
                    return i - stack[-1] - 1
            stack.append(i)
        return -1