A. Best Poker Hand (opens new window)

Count the frequency of each rank and suit.

DETAILS

def bestHand(self, R: List[int], S: List[str]) -> str:
        rr, ss = [0] * 13, [0] * 4
        maxR, maxS = 0, 0

        for r in R: 
            rr[r - 1] += 1
            maxR = max(maxR, rr[r - 1])
        for s in S:
            ss[ord(s) - ord('a')] += 1
            maxS = max(maxS, ss[ord(s) - ord('a')])

        if maxS == 5: return "Flush"
        elif maxR > 2: return "Three of a Kind"
        elif maxR == 2: return "Pair"
        return "High Card"

B. Number of Zero-Filled Subarrays (opens new window)

Find all segments with 0s.

DETAILS

def zeroFilledSubarray(self, A: List[int]) -> int:
        ans, curr = 0, 0
        for a in A:
            if a == 0: curr += 1
            else: 
                ans += curr * (curr + 1) // 2
                curr = 0
        return ans + curr * (curr + 1) // 2

C. Design a Number Container System (opens new window)

Sorted container

DETAILS

from sortedcontainers import SortedList
class NumberContainers:

    def __init__(self):
        self.D, self.pq = {}, defaultdict(SortedList)

    def change(self, index: int, number: int) -> None:
        if index in self.D:
            pn = self.D[index]
            self.pq[pn].remove(index)
        self.D[index] = number
        self.pq[number].add(index)

    def find(self, number: int) -> int:
        return self.pq[number][0] if len(self.pq[number]) else -1

D. Shortest Impossible Sequence of Rolls (opens new window)

Don't overestimate the difficulty!

We are looking for the shortest length that isn't appear in the sequence. Let's say that the actually shortest invalid length is k, meaning we can find all the sequence with length k-1, k-2, ..., 1.

Suppose all the sequence wiht length k-1 can be found before index j, if we can find another set of number of 1~k after index j, meaning we can also find all the sequence with length k-1. While that is contradict to the fact that we lack some of the k-length sequence, meaning we can't find a full set of numbers.

Therefore, the algorithm is quite straght-forward, we just need to iterate over the seqence, whenever we find a full set of number 1~k, meaning all sequence with the current length can be found, we should look for longer sequence, that is, increment the length by 1.

DETAILS

def shortestSequence(self, R: List[int], k: int) -> int:
        ans, seen = 1, set()
        for r in R:
            seen.add(r)
            if len(seen) == k:
                seen.clear()
                ans += 1
        return ans