Constraints

• 0 <= len(request_times) <= 200000
• 1 <= window_size <= 10^9
• 1 <= limit <= 10^5
• request_times is sorted in non-decreasing order

Examples

Solution

def solution(limit, window_size, request_times):
    from collections import deque
    if limit <= 0:
        return [False] * len(request_times)
    window = deque()
    result = []
    for t in request_times:
        while window and window[0] <= t - window_size:
            window.popleft()
        if len(window) < limit:
            window.append(t)
            result.append(True)
        else:
            result.append(False)
    return result

Time complexity: O(n), where n is the number of requests. Space complexity: O(limit) in the worst case for the active window.

Hints

1. Only accepted requests inside the current time window matter.
2. A queue or deque is enough because timestamps arrive in sorted order.

Constraints

• 0 <= total number of requests across all threads <= 200000
• 1 <= number of threads <= 10000
• 1 <= window_size <= 10^9
• 1 <= limit <= 10^5
• Each thread's request list is sorted in non-decreasing order

Examples

Solution

def solution(limit, window_size, thread_requests):
    import heapq
    from collections import deque

    if limit <= 0:
        return [[False] * len(reqs) for reqs in thread_requests]

    result = [[False] * len(reqs) for reqs in thread_requests]
    heap = []

    for tid, reqs in enumerate(thread_requests):
        if reqs:
            heapq.heappush(heap, (reqs[0], tid, 0))

    window = deque()

    while heap:
        t, tid, idx = heapq.heappop(heap)

        while window and window[0] <= t - window_size:
            window.popleft()

        if len(window) < limit:
            result[tid][idx] = True
            window.append(t)

        next_idx = idx + 1
        if next_idx < len(thread_requests[tid]):
            heapq.heappush(heap, (thread_requests[tid][next_idx], tid, next_idx))

    return result

Time complexity: O(N log T), where N is the total number of requests and T is the number of threads. Space complexity: O(T + limit) excluding the output.

Hints

1. This is like merging k sorted lists while maintaining one shared sliding window.
2. A min-heap can give you the next global request in timestamp order.

Constraints

• 0 <= len(operations) <= 200000
• 1 <= window_size <= 10^9
• 1 <= limit <= 10^5
• Advance values are non-negative integers

Examples

Solution

def solution(limit, window_size, operations):
    from collections import deque

    current_time = 0
    window = deque()
    result = []

    for op in operations:
        if not op:
            continue
        if op[0] == 'advance':
            current_time += op[1]
        elif op[0] == 'allow':
            while window and window[0] <= current_time - window_size:
                window.popleft()
            if limit > 0 and len(window) < limit:
                window.append(current_time)
                result.append(True)
            else:
                result.append(False)
        else:
            raise ValueError('Unknown operation')

    return result

Time complexity: O(m), where m is the number of operations. Space complexity: O(limit) in the worst case for the active window.

Hints

1. Treat `allow` as reading from stored state, not from a parameter.
2. Only accepted request times need to be stored.

Constraints

• 0 <= len(nums) <= 200000
• nums is sorted in non-decreasing order
• -10^9 <= nums[i], target <= 10^9

Examples

Solution

def solution(nums, target):
    left, right = 0, len(nums) - 1
    answer = -1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            if nums[mid] == target:
                answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

Time complexity: O(log n). Space complexity: O(1).

Hints

1. When you find the target, do not stop immediately if duplicates may exist.
2. Think about how to shrink the search space toward the leftmost valid index.

Constraints

• 0 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= number of distinct values or larger

Examples

Solution

def solution(nums, k):
    class Node:
        __slots__ = ('freq', 'keys', 'prev', 'next')

        def __init__(self, freq):
            self.freq = freq
            self.keys = set()
            self.prev = None
            self.next = None

    def insert_after(node, new_node):
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node

    def remove(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    if k <= 0 or not nums:
        return []

    head = Node(0)
    tail = Node(0)
    head.next = tail
    tail.prev = head

    where = {}

    for x in nums:
        if x not in where:
            if head.next is tail or head.next.freq != 1:
                insert_after(head, Node(1))
            node = head.next
            node.keys.add(x)
            where[x] = node
        else:
            cur = where[x]
            next_freq = cur.freq + 1
            if cur.next is tail or cur.next.freq != next_freq:
                insert_after(cur, Node(next_freq))
            nxt = cur.next
            nxt.keys.add(x)
            where[x] = nxt

            cur.keys.remove(x)
            if not cur.keys:
                remove(cur)

    result = []
    node = tail.prev
    while node is not head and len(result) < k:
        for x in sorted(node.keys):
            result.append(x)
            if len(result) == k:
                break
        node = node.prev

    return result

Time complexity: O(n + u log u) in the worst case, where n is the stream length and u is the number of distinct values. Space complexity: O(u).

Hints

1. Move an element only from frequency f to frequency f + 1 as you process the stream.
2. A map from value to its current bucket lets you update frequencies in O(1) amortized time.

Constraints

• 1 <= number of people <= 200
• 0 <= total number of busy intervals <= 200000
• 0 <= start < end <= 1440
• Each bounds entry satisfies 0 <= work_start < work_end <= 1440

Examples

Solution

def solution(calendars, bounds, duration):
    def merge_intervals(intervals):
        intervals = sorted(intervals)
        merged = []
        for s, e in intervals:
            if s >= e:
                continue
            if not merged or s > merged[-1][1]:
                merged.append([s, e])
            else:
                merged[-1][1] = max(merged[-1][1], e)
        return merged

    if not calendars or not bounds or len(calendars) != len(bounds):
        return []

    start = max(b[0] for b in bounds)
    end = min(b[1] for b in bounds)
    if start >= end:
        return []

    busy = []
    for calendar in calendars:
        for s, e in merge_intervals(calendar):
            s = max(s, start)
            e = min(e, end)
            if s < e:
                busy.append([s, e])

    busy = merge_intervals(busy)

    result = []
    cursor = start
    for s, e in busy:
        if cursor < s and s - cursor >= duration:
            result.append([cursor, s])
        cursor = max(cursor, e)

    if cursor < end and end - cursor >= duration:
        result.append([cursor, end])

    return result

Time complexity: O(B log B), where B is the total number of busy intervals. Space complexity: O(B).

Hints

1. First reduce the search space to the intersection of all working bounds.
2. Merge overlapping or touching busy intervals before looking for gaps.

Constraints

• 0 <= number of shards <= 10000
• 0 <= total busy intervals across all shards <= 200000
• 0 <= day_start < day_end <= 10^9
• Intervals may be unsorted, overlapping, or partially outside the day bounds

Examples

Solution

def solution(shards, day_start, day_end, duration):
    if day_start >= day_end:
        return []
    if duration <= 0:
        return [[day_start, day_end]]

    events = {}
    for shard in shards:
        for s, e in shard:
            s = max(s, day_start)
            e = min(e, day_end)
            if s >= e:
                continue
            events[s] = events.get(s, 0) + 1
            events[e] = events.get(e, 0) - 1

    if not events:
        return [[day_start, day_end]] if day_end - day_start >= duration else []

    result = []
    active = 0
    cursor = day_start

    for t in sorted(events):
        if cursor < t and active == 0 and t - cursor >= duration:
            result.append([cursor, t])
        active += events[t]
        cursor = t

    if cursor < day_end and active == 0 and day_end - cursor >= duration:
        result.append([cursor, day_end])

    return result

Time complexity: O(M log M), where M is the number of emitted event timestamps. Space complexity: O(M).

Hints

1. Convert each busy interval into two events: +1 at start and -1 at end.
2. After combining events with the same timestamp, sweep from left to right and look for stretches where the active count is zero.

Constraints

• 0 <= number of rooms <= 200
• 0 <= total initial meetings <= 20000
• 0 <= number of requests <= 5000
• Within a room, initial meetings do not overlap but may be unsorted
• All intervals satisfy start < end

Examples

Solution

def solution(rooms, requests):
    room_ids = sorted(rooms.keys())
    schedules = {}
    usage = {}
    booked = {}

    for room_id in room_ids:
        schedule = sorted([list(meeting) for meeting in rooms[room_id]])
        schedules[room_id] = schedule
        usage[room_id] = len(schedule)
        booked[room_id] = sum(e - s for s, e in schedule)

    def find_position(schedule, start):
        lo, hi = 0, len(schedule)
        while lo < hi:
            mid = (lo + hi) // 2
            if schedule[mid][0] < start:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def can_place(schedule, start, end):
        idx = find_position(schedule, start)
        if idx > 0 and schedule[idx - 1][1] > start:
            return False, idx
        if idx < len(schedule) and schedule[idx][0] < end:
            return False, idx
        return True, idx

    result = []

    for start, end in requests:
        best_room = None
        best_key = None
        best_idx = None

        for room_id in room_ids:
            ok, idx = can_place(schedules[room_id], start, end)
            if not ok:
                continue
            key = (usage[room_id], booked[room_id], room_id)
            if best_key is None or key < best_key:
                best_key = key
                best_room = room_id
                best_idx = idx

        if best_room is None:
            result.append(-1)
            continue

        schedules[best_room].insert(best_idx, [start, end])
        usage[best_room] += 1
        booked[best_room] += end - start
        result.append(best_room)

    return result

Time complexity: O(Q * R * log S), where Q is the number of requests, R is the number of rooms, and S is the maximum meetings in any one room. Space complexity: O(total initial meetings + assigned meetings).

Hints

1. For each room, keep its meetings sorted by start time so availability can be checked quickly.
2. Turn the priority rule into a tuple like `(usage_count, total_booked_duration, room_id)`.