A. Minimum Amount of Time to Fill Cups (opens new window)

Focus on the water highest amount.

DETAILS

def fillCups(self, A: List[int]) -> int:
        A.sort()
        if A[2] <= A[0] + A[1]:
            return math.ceil(sum(A) / 2) 
        else:
            return A[2]

B. Smallest Number in Infinite Set (opens new window)

Use set live_set to store all the valid numbers, priority queue live to sort them together with some previously removed numbers.

DETAILS

class SmallestInfiniteSet:

    def __init__(self):
        self.live = list(range(1, 1001))
        heapq.heapify(self.live)
        self.live_set = set(list(range(1, 1001)))

    def popSmallest(self) -> int:
        while self.live and self.live[0] not in self.live_set:
            heapq.heappop(self.live)
        curr = heapq.heappop(self.live)
        self.live_set.remove(curr)
        return curr
        
    def addBack(self, num: int) -> None:
        if num not in self.live_set:    
            self.live_set.add(num)
            heapq.heappush(self.live, num)

C. Move Pieces to Obtain a String (opens new window)

In order to transform from start to target, all the Ls can only move leftward while all the Rs can only move rightward, they don't share the same range. Thus we just need to verify if there exist any index that belongs to the trajactory of both an L or an R.

DETAILS

def canChange(self, S: str, T: str) -> bool:
        lft, rgt, n = 0, 0, len(S)
        for i in range(n):
            if ('R' in [S[i], T[i]] and lft != 0) or ('L' in [S[i], T[i]] and rgt != 0):
                return False
            if (S[i] == 'R' and T[i] == 'L') or (S[i] == 'L' and T[i] == 'R'):
                return False
            if S[i] == 'R':
                rgt += 1
            if S[i] == 'L':
                lft += 1
            if T[i] == 'R':
                rgt -= 1
            if T[i] == 'L':
                lft -= 1
            if (lft != 0 and rgt != 0) or lft > 0 or rgt < 0:
                return False
        return lft == 0 and rgt == 0

D. Count the Number of Ideal Arrays (opens new window)

dp

DETAILS

def idealArrays(self, n: int, mval: int) -> int:
        ans, mod = mval, 10 ** 9 + 7
        prev = {x : 1 for x in range(1, mval + 1)}
        
        for idx in range(1, n):
            curr = {}
            for pre in prev:
                for m in range(2, mval // pre + 1):
                    curr[pre * m] = curr.get(pre * m, 0) + prev[pre]
                    ans += prev[pre] * comb(n - 1, idx)
                    ans %= mod
            prev = curr

        return ans