Queue

933. Number of Recent Calls

class RecentCounter:
    # Intuition:
    # There is no need to keep all past requests since we only care about the ones that are within the [t-3000, t] frame.
    def __init__(self):
        self.requests = deque()

    def ping(self, t: int) -> int:
        self.requests.append(t)
        # Remove all requests older than 3000 ms
        while self.requests[0] < t - 3000:
            self.requests.popleft()
        return len(self.requests)

# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

649. Dota2 Senate

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        # Intuition:
        # 1. The sequence (index in the string) matters. For "RDDRR", the Dire still wins over the Radiant.
        # 2. Whenever we move to the next round, the remaining senators must vote in the same order as they do in the beginning.
        queue_R = deque()
        queue_D = deque()
        n = len(senate)
        # Populate queues with indices:
        for i, party in enumerate(senate):
            if party == 'R':
                queue_R.append(i)
            else:
                queue_D.append(i)
        # Let senators ban others until one party is empty:
        while queue_R and queue_D:
            # We let one senator from each party to compete. The one of smaller index will ban the other one and then move to the next round.
            r = queue_R.popleft()
            d = queue_D.popleft()
            if r < d:
                queue_R.append(r + n)
            else:
                queue_D.append(d + n)
        return "Radiant" if queue_R else "Dire"

Heap / Priority Queue

215. Kth Largest Element in an Array

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Intuition:
        # We keep building a min-heap consisting of the top k largest elements seen so far while discarding small elements.
        # Then in the end, the root node will be the k-th largest element.
        min_heap = nums[:k]  # Create a min-heap with the first k elements
        heapq.heapify(min_heap)  # Convert the list `min_heap` into a heap queue
        for num in nums[k:]:
            if num > min_heap[0]:  # `min_heap[0]` is the top heap
                heapq.heappushpop(min_heap, num)  # This function allows us to push an element onto the heap and pop the smallest element in one combined operation.
        return min_heap[0]  # The root of the heap is the k-th largest element

2336. Smallest Number in Infinite Set

import heapq

class SmallestInfiniteSet:
    # Keys:
    # - curr_int: Visualize the natural sequence as [1, 2, 3,..., inf], where we only need to use `curr_int` to mark the smallest integer that is not untouched in the sequence (i.e. not yet popped).
    # - heap: This heapq is a priority queue that collects ints that are added back.
    # - recovered_ints: addBack() may bring duplicates to `heap`. `recovered_ints` simply makes these lookups faster, in O(1).
    def __init__(self):
        self.curr_int = 1  # smallest integer that is untouched
        self.heap = []  # min-heap for added-back integers
        self.recovered_ints = set()  # for faster look up (to avoid duplicates in the heap)

    def popSmallest(self) -> int:
        if self.heap:
            smallest = heapq.heappop(self.heap)
            self.recovered_ints.remove(smallest)
            return smallest
        smallest = self.curr_int
        self.curr_int += 1
        return smallest

    def addBack(self, num: int) -> None:
        if num in self.recovered_ints or num >= self.curr_int:
            return
        heapq.heappush(self.heap, num)
        self.recovered_ints.add(num)
# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

2542. Maximum Subsequence Score

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        # Keys:
        # The score is basically: `sum * min` over k selected indices, where we try to maximize both `sum` and `min`.
        # - Sorting nums2 in descending order is the most critical part of solving this problem. By doing so, we make sure the current nums2 we are looking at is always the smallest nums2 we've seen so far.
        pairs