A. Find Subsequence of Length K With the Largest Sum (opens new window)

Sort and get the k-th largest sum.

DETAILS

def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        A = sorted(nums, reverse = True)
        tmp = A[:k]
        c = collections.Counter(tmp)
        ans = []
        for a in nums:
            if c[a] > 0:
                ans.append(a)
                c[a] -= 1
        return ans

B. Find Good Days to Rob the Bank (opens new window)

Left and right DP.

DETAILS

def goodDaysToRobBank(self, A: List[int], t: int) -> List[int]:
        if t == 0: return list(range(len(A)))
        lft, rgt, n = [1], [1], len(A)
        
        # Build non-increasing on the left side (inclusive).
        curr = 1
        for i in range(1, n):
            if A[i] <= A[i - 1]: curr += 1
            else: curr = 1
            lft.append(curr)
        
        # Build non-decreasing on the right side (inclusive).
        curr = 1
        for i in range(n - 2, -1, -1):
            if A[i] <= A[i + 1]: curr += 1
            else: curr = 1
            rgt.append(curr)
        rgt.reverse()
        
        return [i for i in range(n) if lft[i] >= t + 1 and rgt[i] >= t + 1]

C. Detonate the Maximum Bombs (opens new window)

Build relation between bombs with overlapped explosion range. BFS from every bomb.

DETAILS

def maximumDetonation(self, A: List[List[int]]) -> int:
        n = len(A)
        nxt = collections.defaultdict(list)
        for i in range(n - 1):
            for j in range(i + 1, n):
                d = (A[i][0] - A[j][0]) ** 2 + (A[i][1] - A[j][1]) ** 2
                if A[i][2] ** 2 >= d:
                    nxt[i].append(j)
                if A[j][2] ** 2 >= d:
                    nxt[j].append(i)
        ans = 1
        for i in range(n):
            seen = set([i])
            dq = collections.deque()
            dq.append(i)
            num = 0
            while dq:
                curr = dq.popleft()
                num += 1
                for cand in nxt[curr]:
                    if cand not in seen:
                        seen.add(cand)
                        dq.append(cand)
            ans = max(ans, num) 
        return ans

D. Sequentially Ordinal Rank Tracker (opens new window)

Priority Queue. Notice python doesn't support passing comparator to priority queue thus we create a data structure and overwrite its comparator.

DETAILS

class Node(object):
    def __init__(self, val, name):
        self.val = val
        self.name = name
        
    def __lt__(self, other):
        if self.val == other.val:
            return self.name > other.name
        return self.val < other.val

class SORTracker:
    def __init__(self):
        self.top = []
        self.bot = []
        self.q = 0

    def add(self, name: str, score: int) -> None:
        heapq.heappush(self.top, Node(score, name))
        
        # Maintain heap TOP of length self.q.
        while len(self.top) > self.q:
            curnode = heapq.heappop(self.top)
            curv = curnode.val
            curn = curnode.name
            heapq.heappush(self.bot, (-curv, curn))

    def get(self) -> str:
        # Maintain heap TOP of length self.q.
        # Since we have one more query, we need to add one item to TOP.
        curv, curn = heapq.heappop(self.bot)
        self.q += 1
        heapq.heappush(self.top, Node(-curv, curn))
        return curn