Constraints

• 0 <= n <= 20
• 0 <= len(moves) <= 10^4
• Each board value is 0 or a positive power of 2
• The board is square

Examples

Solution

def solution(board, moves):
    if not board:
        return []

    n = len(board)

    def compress(line):
        vals = [x for x in line if x != 0]
        merged = []
        i = 0
        while i < len(vals):
            if i + 1 < len(vals) and vals[i] == vals[i + 1]:
                merged.append(vals[i] * 2)
                i += 2
            else:
                merged.append(vals[i])
                i += 1
        merged.extend([0] * (n - len(merged)))
        return merged

    for mv in moves:
        if mv == 'L':
            board = [compress(row) for row in board]
        elif mv == 'R':
            board = [list(reversed(compress(list(reversed(row))))) for row in board]
        elif mv == 'U':
            cols = []
            for c in range(n):
                col = compress([board[r][c] for r in range(n)])
                cols.append(col)
            board = [[cols[c][r] for c in range(n)] for r in range(n)]
        elif mv == 'D':
            cols = []
            for c in range(n):
                original = [board[r][c] for r in range(n)]
                col = list(reversed(compress(list(reversed(original)))))
                cols.append(col)
            board = [[cols[c][r] for c in range(n)] for r in range(n)]
    return board

Time complexity: O(n^2 * m), where m = len(moves). Space complexity: O(n^2).

Hints

1. Solve one row or one column at a time: remove zeros, merge adjacent equal values once, then pad with zeros.
2. You only need one merge routine. For right/down moves, reverse first and reverse back after merging.

Constraints

• The board size is always 4 x 4
• Each board value is either 0 or a power of 2 up to 32768
• The encoded result fits in an unsigned 64-bit integer

Examples

Solution

def solution(mode, data):
    if mode == 'encode':
        board = data
        code = 0
        idx = 0
        for row in board:
            for val in row:
                if val == 0:
                    exp = 0
                else:
                    exp = val.bit_length() - 1
                code |= exp << (4 * idx)
                idx += 1
        return code

    if mode == 'decode':
        code = data
        board = [[0] * 4 for _ in range(4)]
        for idx in range(16):
            exp = (code >> (4 * idx)) & 15
            board[idx // 4][idx % 4] = 0 if exp == 0 else (1 << exp)
        return board

    raise ValueError('mode must be either encode or decode')

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

Hints

1. A 2048 tile is fully determined by its exponent, so 4 bits per cell are enough here.
2. For cell index i in row-major order, use bit positions [4*i, 4*i+3].

Constraints

• 1 <= n <= 2 * 10^5
• 1 <= number of operations <= 2 * 10^5
• 1 <= weight <= 10^9
• Sample queries are always valid: 1 <= r <= current total weight

Examples

Solution

def solution(n, operations):
    bit = [0] * (n + 1)
    weights = [0] * (n + 1)

    def add(i, delta):
        while i <= n:
            bit[i] += delta
            i += i & -i

    def find_by_prefix(target):
        idx = 0
        curr = 0
        bit_mask = 1
        while (bit_mask << 1) <= n:
            bit_mask <<= 1

        while bit_mask:
            nxt = idx + bit_mask
            if nxt <= n and curr + bit[nxt] < target:
                idx = nxt
                curr += bit[nxt]
            bit_mask >>= 1
        return idx + 1

    ans = []
    for op in operations:
        if op[0] == 'insert':
            _, item_id, weight = op
            delta = weight - weights[item_id]
            weights[item_id] = weight
            add(item_id, delta)
        elif op[0] == 'delete':
            _, item_id = op
            if weights[item_id] != 0:
                add(item_id, -weights[item_id])
                weights[item_id] = 0
        else:
            _, r = op
            ans.append(find_by_prefix(r))

    return ans

Time complexity: O(q log n), where q is the number of operations. Space complexity: O(n).

Hints

1. You need fast prefix-sum updates and prefix-sum searches. A Fenwick tree or segment tree is a natural fit.
2. To answer sample(r), find the first index whose prefix sum is at least r.

Constraints

• 1 <= window_size <= 10^9
• 0 <= threshold <= 10^5
• 0 <= number of events <= 2 * 10^5
• Events are sorted by nondecreasing time

Examples

Solution

def solution(window_size, threshold, events):
    from collections import defaultdict, deque

    queues = defaultdict(deque)
    counts = defaultdict(dict)
    distinct = defaultdict(int)
    overloaded = defaultdict(bool)
    alerts = []

    for t, app, ex in events:
        q = queues[ex]
        app_counts = counts[ex]
        expire_before = t - window_size + 1

        while q and q[0][0] < expire_before:
            old_t, old_app = q.popleft()
            app_counts[old_app] -= 1
            if app_counts[old_app] == 0:
                del app_counts[old_app]
                distinct[ex] -= 1

        if distinct[ex] <= threshold:
            overloaded[ex] = False

        q.append((t, app))
        if app not in app_counts:
            app_counts[app] = 0
            distinct[ex] += 1
        app_counts[app] += 1

        if distinct[ex] > threshold and not overloaded[ex]:
            alerts.append((t, ex))
            overloaded[ex] = True

    return alerts

Time complexity: O(m), where m is the number of events. Space complexity: O(m).

Hints

1. Process each exchange independently using a queue of recent events.
2. Store per-application counts inside the window so duplicates from the same application do not increase the distinct count.

Constraints

• 0 <= number of operations <= 2 * 10^5
• Priority values fit in standard integer range
• task_id values are integers
• Delete on a missing task should be ignored

Examples

Solution

def solution(operations):
    import heapq

    heap = []
    active = {}
    seq = 0
    ans = []

    for op in operations:
        if op[0] == 'insert':
            _, task_id, priority = op
            seq += 1
            active[task_id] = (priority, seq)
            heapq.heappush(heap, (-priority, seq, task_id))
        elif op[0] == 'delete':
            _, task_id = op
            active.pop(task_id, None)
        else:
            while heap:
                neg_priority, insert_seq, task_id = heapq.heappop(heap)
                if task_id in active and active[task_id] == (-neg_priority, insert_seq):
                    del active[task_id]
                    ans.append(task_id)
                    break
            else:
                ans.append(None)

    return ans

Time complexity: O(q log q), where q is the number of operations. Space complexity: O(q).

Hints

1. A heap gives the next candidate quickly, but deletions and replacements leave stale entries behind.
2. Keep the current active version of each task in a dictionary and discard stale heap entries when popped.