A. Minimum Hours of Training to Win a Competition (opens new window)

DETAILS

def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: List[int], experience: List[int]) -> int:
        en, ex, an, ax = 0, 0, 0, 0
        for ener, exp in zip(energy, experience):
            if ener >= en:
                an += (ener - en + 1)
                en += (ener - en + 1)
            if exp >= ex:
                ax += (exp - ex + 1)
                ex += (exp - ex + 1)
            en -= ener
            ex += exp
            
        return max(0, (an - initialEnergy)) + max(0, (ax - initialExperience))

B. Largest Palindromic Number (opens new window)

Count the frequency of each digit, if a digit d has k occurrence, then it has k / 2 repeats on each side and k % 2 in the middle.

Find out all repeats for both sides and sort decreasingly, then add the largest middle digit.

DETAILS

def largestPalindromic(self, S: str) -> str:
        C = collections.Counter(S)
        res = []
        mid = -1
        for key in C.keys():
            res.extend([key] * (C[key] // 2))
            if C[key] % 2:
                mid = max(int(key), mid)
        res.sort(reverse=True)
        if not res or res[0] == "0":
            return str(mid) if mid != -1 else "0"
        else:
            return "".join(res) + str(mid) + "".join(res[::-1]) if mid != -1 else "".join(res) + "".join(res[::-1])

C. Amount of Time for Binary Tree to Be Infected (opens new window)

DFS to collect all edges, then BFS to find the time the last node be infected.

DETAILS

def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        G = collections.defaultdict(list)
        def dfs(root):
            if root.left:
                G[root.val].append(root.left.val)
                G[root.left.val].append(root.val)
                dfs(root.left)
            if root.right:
                G[root.val].append(root.right.val)
                G[root.right.val].append(root.val)
                dfs(root.right)
        seen = set([start])  
        dfs(root)
        dq = collections.deque()
        d = 0
        dq.append([start, 0])
        
        while dq:
            cn, cd = dq.popleft()
            d = max(d, cd)
            for nxt in G[cn]:
                if nxt not in seen:
                    seen.add(nxt)
                    dq.append([nxt, cd + 1])
                    
        return d

D. Find the K-Sum of an Array (opens new window)

Notice that we only need to find the largest 2000 sum in the worst-case scenario. Use sliding-window-like method, maintain windows in a priority queue.

DETAILS

def kSum(self, A: List[int], k: int) -> int:
        pos = sum(a for a in A if a > 0)
        A = sorted([abs(a) for a in A])
        pq, n, cv = [[A[0], 0]], len(A), 0
        

        for _ in range(k - 1):
            cv, ci = heapq.heappop(pq)
            if ci < n - 1:
                heapq.heappush(pq, [cv + A[ci + 1], ci + 1])
                heapq.heappush(pq, [cv - A[ci] + A[ci + 1], ci + 1])
            
        return pos - cv