Array Form
    Index:  0   1   2   3   4   5   6
    Value: [3,  5,  8,  9, 10, 12, 15]

    Tree Form

            (0)3
            /     \
        (1)5       (2)8
        /   \      /   \
    (3)9  (4)10 (5)12 (6)15

    def kthLargest(nums, k):
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)  # Keep only top K elements
        return heap[0]

    # Example: kthLargest([3, 2, 1, 5, 6, 4], 2) -> 5

class MedianFinder:
    def __init__(self):
        self.low = []   # Max-heap (invert values)
        self.high = []  # Min-heap
    
    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.low) < len(self.high):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    
    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2        

    def mergeKSorted(lists):
        heap = []
        for i, lst in enumerate(lists):
            if lst:
                heapq.heappush(heap, (lst[0], i, 0))
        
        result = []
        while heap:
            val, list_idx, elem_idx = heapq.heappop(heap)
            result.append(val)
            if elem_idx + 1 < len(lists[list_idx]):
                heapq.heappush(heap, (lists[list_idx][elem_idx+1], list_idx, elem_idx+1))
        return result

    # mergeKSorted([[1,4,5],[1,3,4],[2,6]]) -> [1,1,2,3,4,4,5,6]   

def dijkstra(graph, start):
    
    # Graph: Node -> list of (neighbor, weight) tuples
    # start: Starting node for shortest path search

    # Result: 
    # dist: shortest distance from start to all other nodes

    # Init all distances to infinity, 
    # except start node which has distance 0
    dist = {node: float('inf') for node in graph}
    dist[start] = 0

    # minHeap priority queue stores tuples of (distance, node)
    # iterate from start node and commence exploring neighbors
    heap = [(0, start)]

    # while there are nodes to process in heap
    while heap:
        
        # grab node with smallest known distance from start
        d, node = heapq.heappop(heap)

        # Skip if we already have already explored a shorter
        # path to the current node
        if d > dist[node]:
            continue

        # Check each neighbor and see if we have found 
        # a shorter path through the current node
        for nei, w in graph[node]:
            
            # grab new distance
            nd = d + w

            # if shorter path found, update and push to heap
            if nd < dist[nei]:
                dist[nei] = nd
                heapq.heappush(heap, (nd, nei))

    # overall: time complexity
    # overall: space complexity
    return dist

    def max_sliding_window(nums, k):

        # maxHeap via minHeap with negative values
        # initialize with first k elements
        heap = [(-nums[i], i) for i in range(k)]
        heapq.heapify(heap)

        # root of heap is the largest in the current window
        res = [-heap[0][0]]
        
        # iterate sliding window forward
        for i in range(k, len(nums)):

            # push new element to heap
            heapq.heappush(heap, (-nums[i], i))

            # remove top element if they are outside current window
            while heap[0][1] <= i - k:
                heapq.heappop(heap)

            # after removing out of window elements, heap root is max
            # within the current window
            res.append(-heap[0][0])

        return res

    def minMeetingRooms(intervals):

        # Sort intervals by their start time,
        # ensures we process meetings in chronological order
        intervals.sort(key=lambda x: x[0])

        # minHeap to track end time of ongoing meetings,
        # storing the earliest ending meeting at the top
        heap = []

        # iterate over rooms in earliest starting order
        for start, end in intervals:

            # if heap is not empty, and the earliest ending meeting the earliest meeting ends
            # ends before or exactly when the new meeting starts,
            # then we can remove the earliest ending meeting 
            # (essentially freeing up a room)
            if heap and heap[0] <= start:
                # pop meeting that ended the earliest
                heapq.heappop(heap)

            # 'start' the current meeting by pushing it to the heap
            heapq.heappush(heap, end)

        # last heap size is the number meetings running
        # concurrently after all meetings have started
        return len(heap)

    # Example: 
    # minMeetingRooms([[0,30],[5,10],[15,20]]) -> 2

class KthLargest:

    # MinHeap:
    # We need to track 2 things
    #   - The root min item currently in the stack, which represents kth highest
    #   - Number of items in the stack

    # For our functions, they may need to update the above 2

    # KthLargest():
    #   - Initializes the minHeap
    #   - Starts adding more numbers

    # Add():
    #   - Adds a number to the minHeap
    #   - Returns the kth largest element up to that point

    def __init__(self, k: int, nums: list[int]):
        
        # MinHeap of size k:
        # will contain the k largest elements seen so far,
        # lowest top score at root which represents the kth highest number

        # limiting size of minHeap to be size k    
        self.k = k

        # minHeap
        self.minHeap = []
        
        # mimic 'streaming' input data into minHeap
        for num in nums:
            self.add(num)
    
    # tc:
    # sc: 
    def add(self, val: int) -> int:

        # Attempt to add element to stack
        #   - if minHeap has less elements than k, simply add new element
        #   - if minHeap is out of space, push only if new score is higher than 
        #     current lowest score at the root

        # Heap still has space, add element
        if len(self.minHeap) < self.k:
            heapq.heappush(self.minHeap, val)

        # Heap is out of space, check against min element
        else:
            # Grab min element
            smallestTopScore = self.minHeap[0]

            # Add score if its higher than current lowest element
            if val > smallestTopScore:
                # Replace root element
                heapq.heapreplace(self.minHeap, val)
        
        # return top k score
        return self.minHeap[0]

    # overall: tc
    # overall: sc 

    def findKthLargest(self, nums: list[int], k: int) -> int:
        # Note:
        # 1. MinHeap of size k
        # Result: root of minHeap contains kth largest element
        
        # heap
        minHeap = []
        
        # for each element
        for num in nums:

            # if heap has space, simply push
            if len(minHeap) < k:
                heapq.heappush(minHeap, num)

            # if heap has no space, check if push is necessary
            else:
                # push if new num is larger than smallest in minHeap,
                # this will force a new kth largest element
                if num > minHeap[0]:
                    heapq.heapreplace(minHeap, num)
        
        # kth largest is at the root of the minHeap
        kth = minHeap[0]

        # overall: time complexity
        # overall: space complexity
        return kth

    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        # Note:
        # Optimized Quick Select which will remove 1 subList of duplicates per iteration 
        # 1. RandPivot
        # 2. Partition nums by creating larger, equal, or smaller than pivot subLists
        # 3. Recurse into the correct subList
        # Result: kth largest found while accounting for potential stream of duplicates

        # Empty check
        if not nums: 
            return
        
        # random pivot
        pivot = random.choice(nums)
        
        # Partition nums into three parts:
        # bigger: elements greater than pivot
        bigger = [num for num in nums if num > pivot]
        
        # if kth is within bigger, recurse
        if k <= len(bigger):
            return self.findKthLargest(bigger, k)
        
        # Duplicate Optimization 
        # equal: elements equal to pivot
        equal = [num for num in nums if num == pivot]
        
        # If kth largest is within biggest + equal count,
        # kth will be within partition duplicate list
        if k <= len(bigger) + len(equal):
            return equal[0]
        
        # kth must be within smaller list, recurse
        # update k to ignore length of bigger and equal list
        smaller = [num for num in nums if num < pivot]
        return self.findKthLargest(smaller, k-len(bigger)-len(equal))

    def kthLargestNumber(self, nums: List[str], k: int) -> str:

        # Note:
        # 1. MinHeap of size k, same shape as 215's heap solution
        # 2. The trap: these are STRINGS representing potentially huge
        #    integers (up to 100 digits), so raw string comparison
        #    ("10" < "9") is WRONG -- we must compare by (length, value)
        #    since equal-length numeric strings DO compare correctly
        #    lexicographically, and longer strings are always larger
        #    (no leading zeros guaranteed by constraints)
        # Result: root of minHeap contains kth largest element

        # Comparator key: (length, string) sorts numerically correct --
        # longer digit strings are bigger numbers, and same-length
        # digit strings compare the same lexicographically as numerically
        def numKey(numStr: str):
            return (len(numStr), numStr)

        # heap holds (comparable key, original string) pairs so heapq
        # compares using our numeric key instead of raw string order
        minHeap = []

        # tc: O(n log k), each of n elements does at most one O(log k) op
        for numStr in nums:
            key = numKey(numStr)

            # if heap has space, simply push
            if len(minHeap) < k:
                heapq.heappush(minHeap, (key, numStr))

            # if heap has no space, check if push is necessary
            else:
                # push if new num is larger than smallest in minHeap,
                # this will force a new kth largest element
                if key > minHeap[0][0]:
                    heapq.heapreplace(minHeap, (key, numStr))

        # kth largest is at the root of the minHeap
        kth = minHeap[0][1]

        # overall: tc O(n log k), n = len(nums)
        # overall: sc O(k), for the heap
        return kth

    def kthLargestNumber(self, nums: List[str], k: int) -> str:

        # Note:
        # Same duplicate-aware Quick Select shape as 215's Solution 2,
        # but comparisons use (length, value) instead of raw numeric
        # comparison, since these are strings representing potentially
        # huge integers that Python ints could also handle directly --
        # comparing by (len, str) avoids the overhead of int() conversion
        # on up to 10^4 strings of up to 100 digits each.
        # 1. RandPivot
        # 2. Partition nums by creating larger, equal, or smaller than pivot subLists
        # 3. Recurse into the correct subList
        # Result: kth largest found while accounting for potential stream of duplicates

        def numKey(numStr: str):
            return (len(numStr), numStr)

        def quickSelect(numsList: List[str], k: int) -> str:

            # Empty check
            if not numsList:
                return ""

            # random pivot
            pivot = random.choice(numsList)
            pivotKey = numKey(pivot)

            # Partition numsList into three parts:
            # bigger: elements greater than pivot
            bigger = [num for num in numsList if numKey(num) > pivotKey]

            # if kth is within bigger, recurse
            if k <= len(bigger):
                return quickSelect(bigger, k)

            # Duplicate Optimization
            # equal: elements equal to pivot
            equal = [num for num in numsList if numKey(num) == pivotKey]

            # If kth largest is within biggest + equal count,
            # kth will be within partition duplicate list
            if k <= len(bigger) + len(equal):
                return equal[0]

            # kth must be within smaller list, recurse
            # update k to ignore length of bigger and equal list
            smaller = [num for num in numsList if numKey(num) < pivotKey]
            return quickSelect(smaller, k - len(bigger) - len(equal))

        # overall: tc O(n) average case, O(n^2) worst case (rare with
        #          random pivot); n = len(nums)
        # overall: sc O(n) average, for the recursive partition lists
        return quickSelect(nums, k)

    def topKFrequent(self, nums: List[int], k:int) -> List[int]:

        # MinHeap: 
        # Heap only guarantees that the root is the min or max, and
        # provides no guarantee about the relative order of nodes. 
        # The minHeap root will hold the smallest element,
        # as we iterate we will add elements, 
        # and we only remove the root/smallest element when heap exceeds size k.
        # This ensures the heap will hold the k most frequent
        # elements we have seen so far

        # sc: freq count for list, m unique elements in worst case O(n)
        freq = defaultdict(int)

        # Calculate freq count for each element
        # tc: iterate over list O(n)
        for num in nums: 
            freq[num] += 1

        # sc: minHeap holds smallest k elements O(k)
        minHeap = []

        # tc: iterate over freq count, m unique elements in worst case O(n)
        for (num, freq) in freq.items(): 

            # tc: push operation O(log n)
            heapq.heappush(minHeap, (freq, num)) 
            
            # if heap grows to size k + 1, pop least freq root so we keep the k most freq elements
            if len(minHeap) > k:
t6
                # tc: pop smallest element O(log k)
                heapq.heappop(minHeap) 
        

        # alternative expanded loop:
        # tc: grab top k occurring elements from minHeap, worst case grab n elements O(n)
        result = []
        for (_, num) in minHeap:
            result.append(num) 

        # alternative shorter notation
        # result = [num for freq, num in minHeap]

        # overall: tc O(n log n)
        # overall: sc O(n)
        return result

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    
        # QuickSelect Modified QuickSort:
        # QuickSort sorts based on a partitioned element, whereas when QuickSort
        # complete, everything to the left of the partitioned element is less than it
        # and everything to the right of the partitioned element is greater than it.
        # QuickSelect uses a finalPartitionMarker marks the final expected correct position, 
        # where at which point it stops and elements to the left and right of finalPartitionMarker
        # are guaranteed to be smaller/larger.
        # This avoids sorting the entire array by only sorting as many elements until the 
        # finalPartitionMarker is in the correct place which
        # isolates the minimum elements needed to complete the task

        # Helper: 
        # In place partition of subarray [left,right] relative to random pivot index value
        def partitionSection(left, right, randPivotElemIndex):
            
            # tc: subarray m elements, n in worst case O(n)
            
            # Frequency count of random pivot element
            pivotElemFreq = frequency[unique[randPivotElemIndex]]

            # Move random pivot element to end
            # Tuple unpacking in python allows swapping two variables
            unique[randPivotElemIndex], unique[right] = unique[right], unique[randPivotElemIndex]
            
            # Left index to partition/move larger elements to the left boundary of subarray
            partitionIndex = left

            # tc: iterate over subarray, n in worst case O(n)
            for i in range(left, right):

                # Partition elements with frequencies above the pivotElem Freq (pivotElemFreq < freq),
                # move them to left (move larger elements greater than the pivot to the left of the pivot)
                if pivotElemFreq < frequency[unique[i]]:  
                    
                    # Slicing:
                    # Placing larger freq element on left [high... low] 
                    # allows [:k] to grab the first top k freq elements
                    unique[i], unique[partitionIndex] = unique[partitionIndex], unique[i]
                    partitionIndex += 1

            # set pivot to correct partitioned index,
            # elements left and right of pivot follow [greater... pivot ... lesser]
            unique[partitionIndex], unique[right] = unique[right], unique[partitionIndex]
            return partitionIndex

        # Helper: 
        # Wrapper function that continues to pick random partition element until we have 
        # placed some element at the "finalPartitionMarker" index
        # tc: average recursion depth O(log m)
        # sc: recursion stack for in place partitioning on average O(log m)
        def quickSelectBinarySearchHelper(left, right, finalPartitionMarker):
            
            # Base Case:
            if left == right:
                return

            # Random pivot index:
            # Differs from QuickSort "median-of-three" approach.
            # Random pivot focuses on finding the kth smallest or largest,
            # rather than fully sorting the array, and using random pivot avoids 
            # degrading to worst case O(n^2)
            randPivotElemIndex = random.randint(left, right)

            # Partition subarray
            resultPivotElemIndex = partitionSection(left, right, randPivotElemIndex)
            
            # Base Case: Random partition marker ended up in correct place
            if finalPartitionMarker == resultPivotElemIndex:
                # -> allows us to grab k top freq count by [:k]
                return 
            
            # Binary Search Modification:
            # Selects next subarray and partition pivot
            # resultPivotElemIndex must recurse towards side where finalPartitionMark is on

            # Result was to the right of final expected, 
            # search to the left of the result: [left, resultPivot-1]
            elif finalPartitionMarker < resultPivotElemIndex:
                quickSelectBinarySearchHelper(left, resultPivotElemIndex - 1, finalPartitionMarker)
            
            # Result was to the left of final expected,
            # search to the right of the result: [resultPivot+1, right]
            else:
                quickSelectBinarySearchHelper(resultPivotElemIndex + 1, right, finalPartitionMarker)

        # Calculate freq count for each element
        # tc: iterate over list O(n)
        # sc: allocate for list, n unique elements worst case O(n)
        frequency = defaultdict(int)
        for num in nums:
            frequency[num] += 1

        # Top Kth Elements Indexing: Top 2 elements are indexes [0, 1]
        # [9 7 4 3 1]
        #  0 1 2 3 4
        finalPartition = k - 1

        # Unique count to sort by during partitioning
        unique = list(frequency.keys())
        n = len(unique)
        l, r = 0, n - 1

        # For High to Low (descending) indexing:
        # with list of 6 elements, grab largest 2 elements
        # 2 - 1 = 1 (our 2nd largest)
        # splice [:2] = [0, 1]
        quickSelectBinarySearchHelper(l, r, finalPartition)

        # Pivot is now in the correct partitioned index.
        # Elements left and right of pivot follow [greater... pivot ... lesser]
        # Slice the first k to grab the top k elements

        # overall: tc O(n)
        # overall: sc O(n)
        return unique[:k]

    def topKFrequent(self, nums: List[int], k:int) -> List[int]:
        
        # BucketSort:
        # Grouping values by freq count into buckets.
        # Allows us to iterate over most freq buckets and grab top k elements

        # Calculate freq count for each element
        # tc: iterate over list of n integers O(n)
        # sc: frequency count for unique integers O(m) 
        count = defaultdict(int)
        for key in nums:
            count[key] += 1

        # numBuckets index = items with that frequency count
        # numBuckets must account for max freq count case, where list is full of only 1 element
        # numBuckets must account for empty list, (but still needs a bucket index 0), so we need
        # len(num)+1,
        # empty: 1 bucket: [0] representing empty group
        # else: list of len 5, 6 buckets: [0, 1, 2, 3, 4, 5] each representing length group,
        # with max freq count of 5
        numBuckets = len(nums) + 1

        # list of empty lists, numBucket amount of times 
        # tc: iterate over list length O(n)
        # sc: create len(list)+1 buckets O(n)
        freqBuckets = [[] for i in range(numBuckets)]

        # tc: iterate over frequency list for m unique integer tuples (int, occurrences) O(m) 
        for int, occurrences in count.items():
            freqBuckets[occurrences].append(int)

        # sc: grabbing top k integers, n worst case O(k)
        res = []

        # tc: iterate over len(list)+1 buckets O(n)
        for i in range(len(freqBuckets) - 1, 0, -1):
            
            # tc: iterate over all elements in curr bucket O(m)
            for num in freqBuckets[i]:
                
                # tc: insert operation O(1)
                res.append(num)
                
                # tc: continue while less than k elements grabbed O(k)
                if len(res) == k:
                    return res

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def findClosestElements(self, arr, k, x):
        
        n = len(arr) - 1

        # Sliding Window Boundaries
        # sc: O(1)
        left = 0
        right = n

        currWindowLen = right - left + 1

        # Shrink window from n down to k elements
        # At each step, remove the element farther from x
        while k < currWindowLen:

            # value difference from left and right nums to target x
            leftNum = arr[left]
            leftValue  = abs(leftNum - x)

            rightNum = arr[right]
            rightValue = abs(rightNum - x)

            # Between left and right, remove farther num from target
            # If equal, default to remove right
            # (keep left, problem prefers smaller)
            if leftValue <= rightValue:
                right -= 1
            else:
                left += 1

            # Check new window length
            currWindowLen = right - left + 1

        # left is now at the best location
        res = arr[left:(right + 1)]

        # overall: tc O()
        # overall: sc O()
        return res

    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
                
        # Binary Search + Sliding Window Approach

        # Idea:
        # 1. The closest k elements must form a contiguous subarray of length k.
        # 2. Use binary search to find the left boundary of that window.
        # 3. Compare distances from x for potential windows, and shrink towards the closest.
        
        n = len(arr)
        
        # Binary search boundaries for left index of window
        left = 0
        right = n - k  # window of size k, so left can go at most n-k
        
        # Binary search over possible left boundaries
        # tc: O(log(n-k))
        while left < right:

            # grab mid
            mid = (left + right) // 2

            # Compare distances of window edges to x
            leftEdgeDist  = x - arr[mid]
            rightEdgeDist = arr[mid + k] - x

            # Left edge is farther from x than the right edge
            # Shift left boundary to get left edge closer
            # tc: O(1)
            if rightEdgeDist < leftEdgeDist:
                left = mid + 1

            # Right edge is farther or equal to from x than the left edge
            # Shift left boundary to get right edge closer
            # tc: O(1)
            else:
                right = mid

        # Left now points to optimal left boundary because:
        #   - Every position to the left was eliminated (left edge was too far)
        #   - Every position to the right was eliminated (right edge was too far)
        #   - left == right means only one candidate remains that was never eliminated
        #   - This is the position where the window [left, left+k] is closest to x
        # Splice window of size k
        # tc: O(k)
        res = arr[left:left + k]

        # overall: tc O(log(n-k) + k)
        # overall: sc O(k)
        return res

    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:

        # Min-Heap as k-way Merge:
        # Fix i and vary j: for a fixed nums1[i], the sums
        # nums1[i] + nums2[0], nums1[i] + nums2[1], ... are non-decreasing
        # since nums2 is sorted. So each i defines its own sorted "list"
        # of candidate sums. Finding the k smallest across all these
        # lists is the same k-way merge pattern as Kth Smallest in a
        # Sorted Matrix and Merge K Sorted Lists.

        # Why we only seed min(len(nums1), k) rows:
        # We only ever need at most k pairs total, so there's no reason
        # to seed more than k starting candidates -- any row beyond the
        # kth smallest nums1[i] value can't contribute to the first k
        # results before at least one smaller-sum pair is exhausted first.
        # This keeps the heap size, and therefore each op's cost, bounded
        # by O(min(n, k)) instead of O(n).

        if not nums1 or not nums2 or k == 0:
            return []

        n1, n2 = len(nums1), len(nums2)
        result = []

        # sc: O(min(n1, k)), one "frontier" entry per seeded row
        # Seed: pair each of the first min(n1, k) elements of nums1
        # with nums2[0], the smallest possible partner for that row
        heap = [(nums1[i] + nums2[0], i, 0) for i in range(min(n1, k))]
        heapify(heap)

        # tc: O(k log(min(n1, k))), k pops, each heap op O(log(min(n1,k)))
        while heap and len(result) < k:
            total, i, j = heappop(heap)
            result.append([nums1[i], nums2[j]])

            # Advance:
            # this row's next element becomes the new candidate for
            # row i, maintaining the "one frontier per row" invariant
            if j + 1 < n2:
                heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))

        return result

        # overall: tc O(k log(min(n1, k)))
        # overall: sc O(min(n1, k)), for the heap and seeded rows

    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:

        # Min-Heap as k-way Merge:
        # For a fixed numerator index i, as the denominator index j
        # shrinks from n-1 down toward i+1, arr[j] gets smaller while
        # arr[i] stays fixed -- so arr[i]/arr[j] strictly increases.
        # That means each numerator index i defines its own "row" of
        # increasing fractions, exactly like the sorted-matrix merge
        # pattern from problem 378, just walking denominators backward
        # instead of forward.

        # Why seed at j = n-1:
        # arr[i]/arr[n-1] is the SMALLEST fraction for a given i, since
        # n-1 is the largest possible denominator index. Seeding every
        # row at its smallest element is what lets the heap always
        # offer the true global minimum next.

        n = len(arr)

        # sc: O(n), one entry per row: (fraction, i, j)
        # Seed the heap with the smallest fraction for each numerator
        # index i (paired with the largest denominator, arr[n-1])
        heap = [(arr[i] / arr[n - 1], i, n - 1) for i in range(n - 1)]
        heapify(heap)

        # Pop the smallest k-1 times, discarding each -- the kth pop
        # tc: O(k log n), each pop/push is O(log n) on a heap of size n
        for _ in range(k-1):
            frac, i, j = heappop(heap)

            # Advance:
            # shrink this row's denominator index by one, producing
            # the next-larger fraction for the same numerator index i
            if j - 1 > i:
                heappush(heap, (arr[i] / arr[j - 1], i, j - 1))

        # The kth pop is the answer
        _, i, j = heap[0]
        return [arr[i], arr[j]]

        # overall: tc O((n + k) log n) -- seeding is O(n log n),
        #          k pops/pushes are O(k log n)
        # overall: sc O(n), for the heap

    def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        
        # Note:
        # 1. We want the k points with the smallest Euclidean distances from (0, 0).
        # 2. Instead of computing sqrt(x^2 + y^2), we can use the squared distance x^2 + y^2
        #    because sqrt is monotonic and doesn't change order.
        # 3. Approach:
        #    - Use a max-heap (store negative distances) of size k.
        #    - Iterate over points:
        #         if heap size < k: push (-distance, point)
        #         else if current distance < largest distance in heap: pop and push
        #    - This ensures we always keep k closest points in O(n log k) time.

        # (-distance, [x, y])
        maxHeap = []

        # add all distances to maxHeap
        for x, y in points:

            # square distance
            dist = x * x + y * y 

            # if maxHeap has space, simply push
            if len(maxHeap) < k:
                heapq.heappush(maxHeap, (-dist, [x, y]))

            # if maxHeap is full, check if push is required
            else:

                # if closer than farthest point
                if dist < -maxHeap[0][0]:
                    heapq.heapreplace(maxHeap, (-dist, [x, y]))
        
        # grab list of coords
        res = [xy for (_, xy) in maxHeap]

        # overall: time complexity
        # overall: space complexity
        return res

    def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        
        # Note:
        # Classic Quick Select but with square distance
        # sqrt() is monotonic so we can ignore it
        
        # squared distance to origin
        def dist(i: int) -> int:
            return points[i][0] ** 2 + points[i][1] ** 2
        
        def partition(left, right, randPivotIndex) -> int:

            # prepare partition
            randPivotDist = dist(randPivotIndex)
            points[randPivotIndex], points[right] = points[right], points[randPivotIndex]
            leftPartition = left
            
            # partition all closer points to left
            for i in range(left, right):

                # if point is closer to origin (lower)
                if dist(i) < randPivotDist:
                    points[leftPartition], points[i] = points[i], points[leftPartition]
                    leftPartition += 1
            
            # restore pivot
            points[right], points[leftPartition] = points[leftPartition], points[right]

            # return
            return leftPartition
        
        def quickselect(left, right, finalIndex):
            
            # Base case:
            if left >= right:
                return
            
            # random pivot and result
            randPivotIndex = random.randint(left, right)
            resPivot = partition(left, right, randPivotIndex)
            
            # target check
            if resPivot == finalIndex:
                return
            
            elif resPivot < finalIndex: 
                quickselect(resPivot + 1, right, finalIndex)

            else:
                quickselect(left, resPivot - 1, finalIndex)
            
        
        # boundary
        n = len(points)

        # quickSelect on bounds
        quickselect(0, n - 1, k)

        # grab lowest k points
        res = points[:k]

        # overall: time complexity
        # overall: space complexity
        return res

    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:

        # Min-Heap as k-way Merge:
        # Since every row is individually sorted, the matrix is really
        # n separate sorted lists. Finding the kth smallest across
        # multiple sorted lists is the classic "merge k sorted lists"
        # pattern -- push each list's current smallest onto a min-heap,
        # pop the overall smallest, then push that same row's next
        # element as its new candidate.

        # Why we only ever need one heap entry per row:
        # We never need to consider a row's 2nd element before its 1st
        # has been popped, since rows are sorted -- so the heap never
        # needs more than n entries at once (one "frontier" per row),
        # giving O(n) space instead of O(n^2).

        n = len(matrix)

        # sc: O(n), one entry per row: (value, row, col)
        # Seed the heap with the first (smallest) element of each row
        heap = [(matrix[row][0], row, 0) for row in range(n)]
        heapify(heap)

        # Pop the smallest k-1 times, discarding each -- the kth pop
        # tc: O(k log n), each pop/push is O(log n) on a heap of size n
        for _ in range(k-1):
            val, row, col = heappop(heap)

            # Advance:
            # this row's next element becomes the new candidate,
            # maintaining the "one frontier per row" invariant
            if col + 1 < n:
                heappush(heap, (matrix[row][col + 1], row, col + 1))

        # The kth pop is the answer
        return heap[0][0]

        # overall: tc O((n + k) log n) -- seeding is O(n log n),
        #          k pops/pushes are O(k log n)
        # overall: sc O(n), for the heap

    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:

        # Binary Search on the ANSWER, not the index:
        # We don't binary search positions in the matrix -- we binary
        # search over the range of possible VALUES [matrix[0][0], matrix[n-1][n-1]].
        # For any candidate value x, we can count how many elements are
        # <= x using the sorted rows/columns, then narrow the range until
        # it collapses onto the actual kth smallest value.

        # Why counting is fast (Staircase / Saddleback Search):
        # Start at the bottom-left corner. If the current element is
        # <= x, every element above it in that column is also <= x
        # (columns sorted ascending upward), so we count the whole
        # column at once and move right. If it's > x, that whole row
        # to the right is > x too, so we move up. Each step moves
        # either right or up, at most 2n steps total -- O(n) per count.

        n = len(matrix)

        def countLessEqual(x: int) -> int:
            count = 0
            row, col = n - 1, 0  # start bottom-left

            # tc: O(n), at most n moves right + n moves up
            while row >= 0 and col < n:
                if matrix[row][col] <= x:
                    # entire column above (row, col) is also <= x
                    count += row + 1
                    col += 1
                else:
                    # entire row to the right is > x
                    row -= 1

            return count

        lo, hi = matrix[0][0], matrix[n - 1][n - 1]

        # Binary Search:
        # narrow [lo, hi] until it collapses onto the smallest value
        # whose count-less-equal is >= k -- that value is guaranteed
        # to actually be in the matrix
        # tc: O(log(hi - lo)), each iteration does an O(n) count
        while lo < hi:
            mid = lo + (hi - lo) // 2

            if countLessEqual(mid) >= k:
                hi = mid
            else:
                lo = mid + 1

        return lo

        # overall: tc O(n log(hi - lo)) -- effectively O(n log(max-min))
        # overall: sc O(1), only pointers and counters, no extra storage

    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:

        # NOTE: This is a best-effort, simplified reconstruction of the
        # Frederickson-Johnson style approach -- it captures the core
        # idea (recursively eliminate a constant fraction of the matrix
        # using a cleverly chosen pivot) but is NOT a verified,
        # line-for-line implementation of the original paper. Treat it
        # as educational rather than production-grade.

        n = len(matrix)

        def countLessEqual(x: int) -> int:
            # Same O(n) staircase count from Solution 2
            count = 0
            row, col = n - 1, 0
            while row >= 0 and col < n:
                if matrix[row][col] <= x:
                    count += row + 1
                    col += 1
                else:
                    row -= 1
            return count

        def medianOfSampledPivots() -> int:
            # Pivot Selection:
            # Sample the middle element of every row (each row is
            # already sorted, so its middle element is that row's
            # median) and take the median of THOSE medians. This gives
            # a pivot that is likely to be reasonably central across
            # the whole matrix, in O(n) time -- analogous to the
            # "median of medians" trick from 1D linear-time selection.
            rowMedians = sorted(matrix[row][n // 2] for row in range(n))
            return rowMedians[n // 2]

        lo, hi = matrix[0][0], matrix[n - 1][n - 1]

        # Recursive Elimination:
        # Instead of halving the VALUE range blindly (binary search),
        # pick pivots that are informed by the matrix's actual median
        # structure, so each round's count-less-equal check tends to
        # eliminate a large, roughly-constant fraction of remaining
        # candidates rather than just halving an abstract numeric range.
        # In the true FJ algorithm this fraction is tightly bounded,
        # which is what yields the O(n) total across all rounds; this
        # simplified version doesn't guarantee that bound as rigorously.
        while lo < hi:
            pivot = medianOfSampledPivots()
            pivot = max(lo, min(hi, pivot))

            countLE = countLessEqual(pivot)

            if countLE >= k:
                hi = pivot
            else:
                lo = pivot + 1

        return lo

        # intended: tc ~O(n) via constant-fraction elimination per round
        # actual (unverified): closer to O(n log(max-min)) in the worst
        #   case, since pivot quality here isn't rigorously bounded the
        #   way the paper's construction guarantees
        # sc: O(n) for medianOfSampledPivots' temporary array

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        # Note:
        # 1. minHeap stores current head for each sorted list
        # 2. minHeap sorted by value, list_index breaking ties: 
        #    (value, list_index, node)
        # 3. smallest value across heads added to list
        # 4. push to minHeap to replaced added node
        # Result: merge list in O(n log k)

        # MinHeap():
        #   - O(log n) insertion and removal)

        # MinHeap data representation: (value, index, node)
        #   - Need the value to validate min
        #   - Need index to check if ___
        #   - Need the node to modify connections for new linked list
        minHeap = []

        # For each non empty list,
        # push the head into the heap
        for i, head in enumerate(lists):
            if head:
                heappush(minHeap, (head.val, i, head))  

        # MinHeap() After:
        # Contains the first node of each of the lists,
        # with the min one, at the top of the minHeap

        # DummyHead to keep track of new head
        dummyHead = ListNode(-1)
        prev = dummyHead

        # While the minHeap still has nodes from lists
        #   - pop the smallest from the heap and add to the new list
        #   - grab a new node from the list we just lost a node from
        # tc: O(n log k)
        while minHeap:

            # Current min node
            (minVal, i, node) = heappop(minHeap)

            # Point new list to curr node, and iterate
            prev.next = node
            prev = prev.next

            # If curr min node, has more nodes in their list
            if node.next:
                # Grab next node from list and add to minHeap
                heappush(minHeap, (node.next.val, i, node.next))

        # minHeap Empty:
        # all lists are empty, final list has been merged

        mergedListHead = dummyHead.next

        # overall: tc O(n log k)
        # overall: sc O(k)
        return mergedListHead

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        # Note:
        # 1. Merge lists in pairs with standard merge two sorted lists
        # 2. Each round halves the total number of lists -> O(log k) rounds
        # 3. Each round processes all nodes (across all merges) -> O(n) work per round
        # Result: Merging k lists in place
        
        # Empty check
        if not lists: 
            return None

        # Merge two sorted linked lists
        # time complexity: iterate over lists of n length O(n)
        def mergeTwo(l1, l2):

            # dummy node trick
            dummy = ListNode(-1)
            prev = dummy

            # merge while both lists non empty
            while l1 and l2:
                # grab smaller head
                if l1.val < l2.val:
                    prev.next = l1
                    l1 = l1.next
                else:
                    prev.next = l2
                    l2 = l2.next
                # iterate
                prev = prev.next

            # attach remaining list 
            if not l1:
                prev.next = l2 
            else:
                prev.next = l1

            # return merged new merged list
            return dummy.next

        # iteratively merge lists in pairs until one list remains
        # time complexity: log(len(list)) total merges
        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(mergeTwo(l1, l2))
            lists = merged

        # overall: time complexity O(n log k)
        # overall: space complexity O(1)
        return lists[0]

    def sortArray(self, nums: List[int]) -> List[int]:

        # Merge Sort:
        # Classic divide and conquer -- split the array in half
        # recursively until each piece has 1 element (trivially sorted),
        # then merge pairs of sorted halves back together. The merge
        # step is what does the actual sorting work, in linear time
        # per level, across O(log n) levels.

        def mergeSort(arr: List[int]) -> List[int]:
            # Base case: a single element (or empty) is already sorted
            if len(arr) <= 1:
                return arr

            mid = len(arr) // 2

            # Recurse: sort each half independently
            left = mergeSort(arr[:mid])
            right = mergeSort(arr[mid:])

            # Merge the two sorted halves into one sorted array
            return merge(left, right)

        def merge(left: List[int], right: List[int]) -> List[int]:
            merged = []
            i = j = 0

            # Walk both halves simultaneously, always taking the
            # smaller front element -- this is what keeps the result
            # sorted and is also the classic "merge two sorted lists" op
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    merged.append(left[i])
                    i += 1
                else:
                    merged.append(right[j])
                    j += 1

            # Append any leftovers -- at most one of these loops runs
            merged.extend(left[i:])
            merged.extend(right[j:])

            return merged

        return mergeSort(nums)

        # overall: tc O(n log n), log n levels of recursion, O(n)
        #          merge work per level
        # overall: sc O(n), for the merged sub-arrays at each level
        #          (not in-place)

    def sortArray(self, nums: List[int]) -> List[int]:

        # Heap Sort:
        # Build a max-heap out of the entire array IN-PLACE (no heapq,
        # since the problem disallows built-in sort/heap functions).
        # Then repeatedly swap the max (root) with the last unsorted
        # element and shrink the heap by one, restoring the heap
        # property each time. This sorts the array in-place with O(1)
        # extra space -- the best space complexity of these four solutions.

        n = len(nums)

        def siftDown(heapSize: int, root: int) -> None:
            # Sift Down:
            # push the element at `root` down until it's >= both its
            # children, restoring the max-heap property for the subtree
            largest = root
            left = 2 * root + 1
            right = 2 * root + 2

            if left < heapSize and nums[left] > nums[largest]:
                largest = left
            if right < heapSize and nums[right] > nums[largest]:
                largest = right

            # If a child was bigger, swap it up and keep sifting down
            # into whichever subtree we swapped into
            if largest != root:
                nums[root], nums[largest] = nums[largest], nums[root]
                siftDown(heapSize, largest)

        # Build-Heap:
        # start from the last non-leaf node and sift down each node --
        # this bottom-up build is O(n), not O(n log n), since most
        # nodes are near the bottom and sift down a short distance
        for i in range(n // 2 - 1, -1, -1):
            siftDown(n, i)

        # Extract:
        # the root of a max-heap is always the current largest element.
        # Swap it to the end (its final sorted position), shrink the
        # heap by one, then sift the new root down to restore the heap
        for end in range(n - 1, 0, -1):
            nums[0], nums[end] = nums[end], nums[0]
            siftDown(end, 0)

        return nums

        # overall: tc O(n log n) -- O(n) to build the heap,
        #          O(n log n) for n extractions each costing O(log n)
        # overall: sc O(1), sorts in-place (ignoring recursion stack,
        #          which can be made O(1) with an iterative siftDown)

    def sortArray(self, nums: List[int]) -> List[int]:

        # To avoid Quick Sort O(n^2)
        # use pivot = nums[random.randint(left, right)], 
        # instead of pivot = nums[(left + right) // 2]

        # Quick Sort (Randomized):
        # Pick a random pivot, partition the array in-place so
        # everything smaller ends up left of the pivot and everything
        # bigger ends up right, then recurse on each side. Randomizing
        # the pivot choice avoids the classic O(n^2) worst case that
        # a fixed pivot (like "always first element") hits on already
        # sorted or adversarial input.

        def quickSort(lo: int, hi: int) -> None:
            if lo >= hi:
                return

            pivotIndex = partition(lo, hi)

            # Recurse on both sides of the pivot's final position
            quickSort(lo, pivotIndex - 1)
            quickSort(pivotIndex + 1, hi)

        def partition(lo: int, hi: int) -> int:
            # Randomize:
            # swap a random element into the pivot slot (last position)
            # so the algorithm's performance doesn't depend on input order
            randIdx = random.randint(lo, hi)
            nums[randIdx], nums[hi] = nums[hi], nums[randIdx]

            pivot = nums[hi]
            i = lo  # boundary: everything before i is < pivot

            # Lomuto Partition:
            # walk through, and whenever we find something smaller
            # than the pivot, swap it into the "smaller" region and
            # advance the boundary
            for j in range(lo, hi):
                if nums[j] < pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1

            # Place the pivot in its correct final sorted position
            nums[i], nums[hi] = nums[hi], nums[i]

            return i

        quickSort(0, len(nums) - 1)
        return nums

        # overall: tc O(n log n) expected (randomization makes O(n^2)
        #          worst case astronomically unlikely in practice)
        # overall: sc O(log n) expected, for the recursion stack
        #          (in-place partitioning otherwise)

    def sortArray(self, nums: List[int]) -> List[int]:

        # Counting Sort:
        # NOT comparison-based, so the usual O(n log n) lower bound
        # for comparison sorts doesn't apply here. Since constraints
        # guarantee values are bounded (-5*10^4 to 5*10^4, a range of
        # 10^5 + 1 possible values), we can count occurrences of each
        # value directly and reconstruct the sorted array from those
        # counts -- true O(n + range) time.

        # Why this isn't "cheating" the O(n log n) requirement:
        # the problem asks for a solution "in O(n log n) time" as a
        # baseline expectation (ruling out naive O(n^2) approaches),
        # and counting sort satisfies that trivially since
        # O(n + range) is asymptotically better when range is bounded --
        # but it's only viable BECAUSE the constraints guarantee a
        # bounded range; it wouldn't work for arbitrary integers.

        OFFSET = 50000  # shift negative values into a valid index range
        RANGE = 100001  # -50000 to 50000 inclusive

        # sc: O(range), one counter per possible value
        counts = [0] * RANGE

        # Count occurrences of each value
        # tc: O(n)
        for num in nums:
            counts[num + OFFSET] += 1

        result = []

        # Reconstruct:
        # walk counts in ascending order, appending each value as
        # many times as it occurred
        # tc: O(n + range), range dominates only when range >> n
        for i, count in enumerate(counts):
            if count > 0:
                result.extend([i - OFFSET] * count)

        return result

        # overall: tc O(n + range), range = 10^5 here -- effectively
        #          O(n) when n is reasonably large relative to range
        # overall: sc O(n + range), for the counts array and result

    def lastStoneWeight(self, stones: list[int]) -> int:
        
        # MaxHeap:
        # We use a max heap to always extract the two largest stones efficiently.
        # Since Python only provides a min heap, we simulate a max heap
        # by inserting negative values.

        # Heap Strategy:
        # 1. Build a max heap from the input stones.
        # 2. Repeatedly remove the two largest stones.
        # 3. Smash them together and, if a remainder exists, push it back into the heap.
        # 4. Continue until at most one stone remains.
        # Result: return the final stone weight or 0 if all stones are destroyed.


        # MaxHeap List:
        # Turn positive stone weights into negative weights
        # tc:
        # sc:
        maxHeap = [-stone for stone in stones]

        # MaxHeap:
        # Transform negative list into heap in place in linear time
        # MinHeap with negative numbers is a MaxHeap
        # tc:
        # sc:
        heapq.heapify(maxHeap)

        # remove top two stones until one stone left
        # tc:
        while len(maxHeap) > 1:

            # Grab two heaviest stones
            heaviest = -(heapq.heappop(maxHeap))
            second_heaviest = -(heapq.heappop(maxHeap))

            # If remainder stone
            if heaviest != second_heaviest:

                # Get remainder stone
                remainingStoneWeight = -(heaviest - second_heaviest)

                # Push remaining stone back to MaxHeap
                heapq.heappush(maxHeap, remainingStoneWeight)

        # Check: if any stone remains
        # Grab the heaviest stone
        res = -maxHeap[0] if maxHeap else 0

        # overall: tc
        # overall: sc
        return res

    def reorganizeString(self, s: str) -> str:

        # Greedy + Max-Heap:
        # Intuitively, the character with the most copies is the one
        # most at risk of ending up adjacent to itself, so it should
        # always be placed as early and as often as possible. A max-heap
        # (by count) lets us repeatedly grab "whichever character has
        # the most copies left" in O(log k) time, where k = 26 letters.

        # Why a one-round cooldown is enough:
        # After placing a character, we can't place it again immediately
        # -- but we CAN place it again next round. So instead of a full
        # queue of history, we only need to remember the single character
        # we just placed and push it back into the heap after placing
        # the next (different) character.

        # Impossibility check:
        # If any character's count exceeds ceil(n / 2), it's mathematically
        # impossible to space it out enough -- there aren't enough "gaps"
        # from other characters to separate every copy of it.

        n = len(s)

        # tc: O(n), count occurrences of each character
        counts = Counter(s)

        # Impossibility:
        # the most frequent character can't need more than half
        # (rounded up) of all positions
        if max(counts.values()) > (n + 1) // 2:
            return ""

        # Max-Heap:
        # Python's heapq is a min-heap, so negate counts to simulate
        # a max-heap -- the most frequent character surfaces first
        # sc: O(k), k = number of distinct characters (at most 26)
        heap = [(-count, char) for char, count in counts.items()]
        heapify(heap)

        result = []

        # Cooldown slot: holds the previously placed (count, char)
        # until it's safe to push back onto the heap
        prevCount, prevChar = 0, ""

        # tc: O(n log k), n pops/pushes, each O(log k)
        while heap:

            # Take:
            # grab whichever character currently has the most copies left
            count, char = heappop(heap)
            result.append(char)

            # Cooldown:
            # if we have a previously placed character still waiting
            # out its cooldown, it's now safe to make it eligible again
            if prevCount < 0:
                heappush(heap, (prevCount, prevChar))

            # Consume one copy of the character we just placed, then
            # put it on cooldown for exactly one round
            prevCount, prevChar = count + 1, char

        # Validate:
        # if we couldn't place every character, the greedy choice
        # ran into a dead end (shouldn't happen given the check above,
        # but guards against edge cases)
        return "".join(result) if len(result) == n else ""

        # overall: tc O(n log k), k = 26 -> effectively O(n)
        # overall: sc O(k) for the heap, O(n) for the result string

    def getOrder(self, tasks: List[List[int]]) -> List[int]:

        # Shortest Job First Simulation:
        # The CPU always wants "the shortest available task, breaking
        # ties by original index" -- exactly what a min-heap keyed on
        # (processingTime, index) gives us in O(log n) per operation.
        # The tricky part isn't the tie-break, it's correctly tracking
        # WHICH tasks are "available" at any given moment, since
        # availability depends on the current simulated time.

        # Why sort by enqueue time first:
        # We need to release tasks into the heap in the order they
        # become available, not in their original index order. Sorting
        # once up front lets us sweep through tasks left-to-right with
        # a pointer, only ever looking at "the next task to arrive."

        n = len(tasks)

        # Preserve original indices before sorting, since the answer
        # needs to report original task indices, not sorted positions
        # sc: O(n)
        # tc: O(n log n), the dominant cost of the whole algorithm
        indexedTasks = sorted(range(n), key=lambda i: tasks[i][0])

        # sc: O(n), holds available tasks as (processingTime, index)
        heap = []

        result = []
        time = 0        # current simulated CPU clock
        ptr = 0         # points to the next not-yet-released task

        # tc: O(n log n) total -- each task pushed/popped from the
        # heap at most once, each op O(log n)
        while len(result) < n:

            # Release:
            # push every task that has become available by "time"
            # (their enqueueTime <= time) into the heap
            while ptr < n and tasks[indexedTasks[ptr]][0] <= time:
                i = indexedTasks[ptr]
                heappush(heap, (tasks[i][1], i))
                ptr += 1

            if heap:
                # Run:
                # process the shortest available task (ties broken by
                # index automatically, since index is the tuple's
                # second element)
                processingTime, i = heappop(heap)
                result.append(i)
                time += processingTime
            else:
                # Idle:
                # nothing is available yet -- instead of idling one
                # unit at a time, jump the clock straight to the next
                # task's enqueue time, since nothing happens in between
                time = tasks[indexedTasks[ptr]][0]

        return result

        # overall: tc O(n log n), dominated by the initial sort and
        #          the heap operations
        # overall: sc O(n), for the sorted index list and the heap

    def leastInterval(self, tasks: list[str], n: int) -> int:

        # Note:
        # 1. Highest occurring tasks + idle time determine the min scheduling
        # 2. Total number of tasks determine the min scheduling
        # Result: min scheduling for list of tasks 

        # Count frequency of each task (A-Z)
        freq = defaultdict(int)
        for task in tasks:
            freq[task] += 1
        
        # highest number of occurrences for single task
        maxFreq = max(freq.values())
        
        # number of tasks with highest number of occurrences
        maxCount = sum(1 for count in freq.values() if count == maxFreq)
        
        # The minimum time is based on arranging the most frequent tasks spaced by n:
        # ex:
        # A, B, C share freq count of 9
        # idle interval n = 5
        # 
        # so:
        # [A -> B -> C -> idle -> idle...] * 8 times
        # + [A -> B -> C] last group (notice no idles needed)

        # (maxFreq-1) -> 8 times = groups
        # (n+1) = length of group (n idle time + 1 for task occurrence

        # + maxCount for last group
        intervals = (maxFreq - 1) * (n + 1) + maxCount
        
        # if totalTasks is higher than intervals, totalTasks is the lower bound
        # ie: A,B,C combo takes 51 
        #     however, rest of alphabet all has 4 count, leading to 119
        # we will take the 119
        # (in this case, we wont have to use idle)
        res = max(intervals, len(tasks))

        # overall: time complexity
        # overall: space complexity
        return res

    def leastInterval(self, tasks: list[str], n: int) -> int:

        # Note:
        # Simulates task scheduling process 
        # 1. MaxHeap picks current most frequent remaining task first
        # 2. Queue (FIFO) simulates cool down to store tasks that have been run
        # but must wait 'n' intervals before they can be scheduled again
        # 3. Each iteration represents 1 unit of CPU time
        # 4. Iterate until both MaxHeap and Queue are empty
        # Result: time is total CPU time needed, including idle intervals

        # counts
        freq = Counter(tasks)
        
        # MaxHeap with negative counts
        maxHeap = [-count for count in freq.values()]
        heapq.heapify(maxHeap)
        
        # total CPU time simulated
        time = 0
        
        # Queue to hold cooldown tasks: (ready_time, count)
        cooldown = deque()
        
        # until both are empty
        while maxHeap or cooldown:

            # 1 CPU tick
            time += 1
            
            # grab most frequent task
            if maxHeap:
                
                # remove most freq task from root, and decrement by 1 
                cnt = heapq.heappop(maxHeap) + 1
                if cnt != 0:
                    # put task into cool down,
                    # and calculate time until next available use
                    cooldown.append((time + n, cnt))
            
            # check if any task in cool down is ready to be added back to maxHeap
            if cooldown and cooldown[0][0] == time:

                # pop FIFO
                _, cnt = cooldown.popleft()

                # push task occurrence count back to maxHeap
                heapq.heappush(maxHeap, cnt)
        
        # overall: time complexity
        # overall: space complexity
        return time

    def leastInterval(self, tasks: List[str], n: int) -> int:

        # Note:
        # Simulates task scheduling with a MaxHeap + cool down queue
        # 1. MaxHeap picks current most frequent remaining task first
        # 2. Queue (FIFO) simulates cool down to store tasks that have been run
        # but must wait 'n' intervals before they can be scheduled again
        # 3. if MaxHeap is empty but cool down queue is not, we 'jump' 
        #    directly to the next ready task instead of simulating idle ticks,
        #.   skipping over unnecessary +1 increments and speeds up simulation
        # Result: time is total CPU time needed, including idle intervals,
        #         with fewer iterations
        
        
        # counts
        freq = Counter(tasks)
        
        # MaxHeap with negative counts
        maxHeap = [-count for count in freq.values()]
        heapq.heapify(maxHeap)

        # total CPU time simulated
        time = 0

        # Queue to hold cooldown tasks: (-cnt, idleTime)
        q = deque()  

        # until both are empty
        while maxHeap or q:

            # CPU tick
            time += 1

            # if maxHeap is empty
            if not maxHeap:
                # time 'jump' to next cool down
                time = q[0][1]

            # maxHeap is non empty
            else:

                # remove most freq task from root, and decrement by 1 
                cnt = 1 + heapq.heappop(maxHeap)
                if cnt:
                    # put task into cool down,
                    # and calculate time until next available use 
                    q.append([cnt, time + n])

            # check if any task in cool down is ready to be added back to maxHeap
            if q and q[0][1] == time:
                
                # pop FIFO
                (cnt, idleTime) = q.popleft()

                heapq.heappush(maxHeap, cnt)

        # overall: time complexity
        # overall: space complexity
        return time

class Twitter:

    def __init__(self):

        # IRL Use Case: 
        # Balanced usage scenario users follow moderate number of accounts, tweet counts are not huge.

        # Note:
        # Tweets: Stores tweets as deques (lists) per user.
        # News Feed: Merges k sorted lists using a maxHeap to always pick the most
        #            recent tweet across the user and their followees.

        # Pros: Simple implementation, efficient for moderate tweet counts.
        # Cons: Heap merge has some overhead; memory grows with many tweets per user.

        self.followees = defaultdict(set)
        self.tweets = defaultdict(deque)
        self.time = 0
        self.FEED_SIZE = 10

    # time complexity:
    # space complexity:
    def postTweet(self, userId: int, tweetId: int) -> None:

        # Note:
        #

        self.time += 1
        self.tweets[userId].append((self.time, tweetId))

        if len(self.tweets[userId]) > 100:
            self.tweets[userId].popleft()

    # time complexity:
    # space complexity:
    def follow(self, followerId: int, followeeId: int) -> None:

        # Note:
        #

        if followerId != followeeId:
            self.followees[followerId].add(followeeId)

    # time complexity:
    # space complexity:
    def unfollow(self, followerId: int, followeeId: int) -> None:

        # Note:
        #

        self.followees[followerId].discard(followeeId)

    # time complexity:
    # space complexity:
    def getNewsFeed(self, userId: int) -> list[int]:

        # Note:
        #

        # heap stores (-timestamp, tweetId, userId, index_in_user_tweets)
        heap = []

        # The list of users to fetch tweets from: self + followees
        users = self.followees[userId] | {userId}
        
        # Init pointers for each user tweet list (start from newest)
        for u in users:

            if self.tweets[u]:

                # Index of last tweet in deque (newest)
                idx = len(self.tweets[u]) - 1
                timestamp, tweetId = self.tweets[u][idx]
                heapq.heappush(heap, (-timestamp, tweetId, u, idx))
        
        result = []

        while heap and len(result) < self.FEED_SIZE:

            neg_time, tweetId, u, idx = heapq.heappop(heap)
            result.append(tweetId)

            # Move pointer to next newest tweet if available
            if idx > 0:
                idx -= 1
                timestamp, tweetId = self.tweets[u][idx]
                heapq.heappush(heap, (-timestamp, tweetId, u, idx))
        
        return result

    # overall: time complexity
    # overall: space complexity