Constraints

• 0 <= len(A), len(B) <= 200000
• Array values fit in 32-bit signed integer
• Duplicates may appear any number of times
• The arrays are not guaranteed to be sorted

Examples

Solution

def solution(A, B):
    return set(A) == set(B)

Time complexity: O(n + m), where n = len(A) and m = len(B). Space complexity: O(u + v), where u and v are the number of unique elements in A and B.

Hints

1. Duplicates do not matter, so focus on unique elements only.
2. A hash-based container can compare the unique contents of both arrays in linear time.

Constraints

• 0 <= len(events) <= 200000
• 0 <= W_ms, T_end <= 10^9
• 0 <= K <= 200000
• Each event is [timestamp_ms, ad_id]
• events is sorted by timestamp_ms ascending
• ad_id fits in 32-bit signed integer

Examples

Solution

def solution(events, W_ms, T_end, K):
    from bisect import bisect_left, bisect_right
    from collections import Counter

    if K <= 0 or not events:
        return []

    timestamps = [event[0] for event in events]
    start = T_end - W_ms
    left = bisect_left(timestamps, start)
    right = bisect_right(timestamps, T_end)

    if left >= right:
        return []

    counts = Counter()
    for i in range(left, right):
        ad_id = events[i][1]
        counts[ad_id] += 1

    ranked = sorted(counts.items(), key=lambda item: (-item[1], item[0]))
    return [ad_id for ad_id, _ in ranked[:K]]

Time complexity: O(n + m + u log u), where n is the number of events, m is the number of events inside the window, and u is the number of distinct ad IDs in the window. Space complexity: O(n + u).

Hints

1. Since events are sorted by time, first find the left and right boundaries of the window.
2. After counting frequencies inside the window, sort by (-count, ad_id) for deterministic output.

Constraints

• 0 <= len(operations) <= 200000
• Ingest operations are of the form [1, timestamp_ms, ad_id]
• Query operations are of the form [2, T_end, W_ms, K]
• Timestamps in ingest operations are non-decreasing
• 0 <= timestamp_ms, T_end, W_ms <= 10^9
• 0 <= K <= 200000
• ad_id fits in 32-bit signed integer

Examples

Solution

def solution(operations):
    from bisect import bisect_left, bisect_right
    from collections import Counter

    timestamps = []
    ad_ids = []
    answers = []

    for op in operations:
        if not op:
            continue

        if op[0] == 1:
            _, timestamp_ms, ad_id = op
            timestamps.append(timestamp_ms)
            ad_ids.append(ad_id)
        elif op[0] == 2:
            _, T_end, W_ms, K = op

            if K <= 0 or not timestamps:
                answers.append([])
                continue

            start = T_end - W_ms
            left = bisect_left(timestamps, start)
            right = bisect_right(timestamps, T_end)

            if left >= right:
                answers.append([])
                continue

            counts = Counter()
            for i in range(left, right):
                counts[ad_ids[i]] += 1

            ranked = sorted(counts.items(), key=lambda item: (-item[1], item[0]))
            answers.append([ad_id for ad_id, _ in ranked[:K]])

    return answers

Time complexity: O(n + sum(log n + m_i + u_i log u_i)) over all queries, where n is the number of ingested events, m_i is the number of events in query i's window, and u_i is the number of distinct ad IDs in that window. Space complexity: O(n), where n is the number of ingested events stored.

Hints

1. Because ingested timestamps are non-decreasing, you can store them in a simple array and binary search query boundaries.
2. For each query, only count impressions whose indices fall inside the time window.

Constraints

• 0 <= len(source), len(target) <= 200000
• Both strings contain lowercase English letters a-z
• Each character from source can be used at most once

Examples

Solution

def solution(source, target):
    from collections import Counter

    if len(target) > len(source):
        return False

    available = Counter(source)
    needed = Counter(target)

    for ch, cnt in needed.items():
        if available[ch] < cnt:
            return False

    return True

Time complexity: O(n + m), where n = len(source) and m = len(target). Space complexity: O(1) if the alphabet is fixed to 26 lowercase letters, otherwise O(u) for the number of distinct characters.

Hints

1. Count how many times each character is needed in target.
2. If any character is required more often than it appears in source, the answer is False.