Constraints

• 1 <= rows, cols <= 1000
• 1 <= k <= max(rows, cols)
• 0 <= len(moves) <= rows * cols
• Each player value is intended to be 1 or 2, but invalid values should return -1 for that move

Examples

Solution

def solution(rows, cols, k, moves):
    board = {}
    results = []
    game_over = False
    directions = ((1, 0), (0, 1), (1, 1), (1, -1))

    for row, col, player in moves:
        if game_over or player not in (1, 2) or not (0 <= row < rows and 0 <= col < cols) or (row, col) in board:
            results.append(-1)
            continue

        board[(row, col)] = player
        won = False

        for dr, dc in directions:
            count = 1

            r, c = row + dr, col + dc
            while count < k and 0 <= r < rows and 0 <= c < cols and board.get((r, c)) == player:
                count += 1
                r += dr
                c += dc

            r, c = row - dr, col - dc
            while count < k and 0 <= r < rows and 0 <= c < cols and board.get((r, c)) == player:
                count += 1
                r -= dr
                c -= dc

            if count >= k:
                won = True
                break

        if won:
            game_over = True
            results.append(player)
        else:
            results.append(0)

    return results

Time complexity: O(M * k), where M is the number of moves. Space complexity: O(M).

Hints

1. Only the most recent move can create a new win, so you never need to rescan the whole board.
2. For each move, check four direction pairs: horizontal, vertical, main diagonal, and anti-diagonal.

Constraints

• 1 <= rows, cols
• 1 <= rows * cols <= 200000
• 1 <= k <= max(rows, cols)
• 0 <= len(operations) <= 200000

Examples

Solution

def solution(rows, cols, k, operations):
    class Fenwick:
        def __init__(self, n):
            self.n = n
            self.bit = [0] * (n + 1)
            for i in range(1, n + 1):
                self.bit[i] = i & -i

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

        def kth(self, k):
            idx = 0
            bit_mask = 1 << self.n.bit_length()
            while bit_mask:
                nxt = idx + bit_mask
                if nxt <= self.n and self.bit[nxt] < k:
                    idx = nxt
                    k -= self.bit[nxt]
                bit_mask >>= 1
            return idx + 1

    def check_win(row, col, player):
        for dr, dc in directions:
            count = 1

            r, c = row + dr, col + dc
            while count < k and 0 <= r < rows and 0 <= c < cols and board.get((r, c)) == player:
                count += 1
                r += dr
                c += dc

            r, c = row - dr, col - dc
            while count < k and 0 <= r < rows and 0 <= c < cols and board.get((r, c)) == player:
                count += 1
                r -= dr
                c -= dc

            if count >= k:
                return True
        return False

    n = rows * cols
    fenwick = Fenwick(n)
    total_empty = n
    board = {}
    directions = ((1, 0), (0, 1), (1, 1), (1, -1))
    game_over = False
    results = []

    for op in operations:
        if op[0] == 'move':
            _, row, col, player = op
            if game_over or player not in (1, 2) or not (0 <= row < rows and 0 <= col < cols) or (row, col) in board:
                results.append(-1)
                continue

            board[(row, col)] = player
            fenwick.add(row * cols + col + 1, -1)
            total_empty -= 1

            if check_win(row, col, player):
                game_over = True
                results.append(player)
            else:
                results.append(0)

        elif op[0] == 'ai':
            _, player, rank = op
            if game_over or player not in (1, 2) or total_empty == 0 or not (0 <= rank < total_empty):
                results.append((-1, -1))
                continue

            idx = fenwick.kth(rank + 1) - 1
            results.append((idx // cols, idx % cols))
        else:
            results.append(-1)

    return results

Time complexity: Each 'move' is O(k + log(rows * cols)); each 'ai' query is O(log(rows * cols)). Space complexity: O(rows * cols + P), where P is the number of played cells.

Hints

1. If `rank` tells you which empty cell to choose, the AI query becomes a k-th available-position query.
2. A Fenwick tree or segment tree can track which cells are still empty in row-major order.

Constraints

• Up to 10^6 operations
• Record timestamps are non-decreasing
• Timestamps fit in a signed 64-bit integer

Examples

Solution

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

    times = []
    prefix = []
    results = []

    for op in operations:
        if op[0] == 'record':
            t = op[1]
            if times and times[-1] == t:
                prefix[-1] += 1
            else:
                times.append(t)
                prefix.append((prefix[-1] if prefix else 0) + 1)
        else:
            _, start, end = op
            if start > end or not times:
                results.append(0.0)
                continue

            right = bisect_right(times, end) - 1
            if right < 0:
                results.append(0.0)
                continue

            left = bisect_left(times, start) - 1
            count = prefix[right]
            if left >= 0:
                count -= prefix[left]

            results.append(count / (end - start + 1))

    return results

Time complexity: record: O(1) amortized, getQPS: O(log U), where U is the number of distinct recorded timestamps. Space complexity: O(U).

Hints

1. Many consecutive `record` calls may share the same timestamp, so storing one count per distinct time can save space.
2. Use binary search on the distinct timestamps to count how many requests fall inside a query range.

Constraints

• 0 <= len(timestamps) <= 10^6
• 0 <= len(queries) <= 10^6
• Timestamps are sorted in non-decreasing order
• Timestamps fit in a signed 64-bit integer

Examples

Solution

def solution(timestamps, queries):
    from bisect import bisect_left, bisect_right

    results = []
    for start, end in queries:
        if start > end or not timestamps:
            results.append(0.0)
            continue

        left = bisect_left(timestamps, start)
        right = bisect_right(timestamps, end)
        results.append((right - left) / (end - start + 1))

    return results

Time complexity: O(Q log N), where N is the number of timestamps. Space complexity: O(1) extra space, excluding the output list.

Hints

1. In a sorted array, the number of values inside a range can be found with two binary searches.
2. You only need the first index >= startTime and the first index > endTime.

Constraints

• 1 <= bucket_size <= 10^9
• 0 <= len(timestamps) <= 200000
• 0 <= len(queries) <= 200000
• Timestamps fit in a signed 64-bit integer

Examples

Solution

def solution(bucket_size, timestamps, queries):
    from bisect import bisect_left, bisect_right

    bucket_counts = {}
    for t in timestamps:
        b = t // bucket_size
        bucket_counts[b] = bucket_counts.get(b, 0) + 1

    bucket_ids = sorted(bucket_counts)
    prefix = []
    running = 0
    for b in bucket_ids:
        running += bucket_counts[b]
        prefix.append(running)

    def bucket_sum(lo, hi):
        if lo > hi or not bucket_ids:
            return 0
        left = bisect_left(bucket_ids, lo)
        right = bisect_right(bucket_ids, hi) - 1
        if left > right:
            return 0
        total = prefix[right]
        if left > 0:
            total -= prefix[left - 1]
        return total

    def overlap_len(bucket_id, start, end):
        bucket_start = bucket_id * bucket_size
        bucket_end = bucket_start + bucket_size - 1
        left = max(start, bucket_start)
        right = min(end, bucket_end)
        if left > right:
            return 0
        return right - left + 1

    results = []
    for start, end in queries:
        if start > end:
            results.append(0.0)
            continue

        duration = end - start + 1
        start_bucket = start // bucket_size
        end_bucket = end // bucket_size

        if start_bucket == end_bucket:
            approx_count = bucket_counts.get(start_bucket, 0) * (duration / bucket_size)
        else:
            approx_count = 0.0
            approx_count += bucket_counts.get(start_bucket, 0) * (overlap_len(start_bucket, start, end) / bucket_size)
            approx_count += bucket_counts.get(end_bucket, 0) * (overlap_len(end_bucket, start, end) / bucket_size)
            approx_count += bucket_sum(start_bucket + 1, end_bucket - 1)

        results.append(approx_count / duration)

    return results

Time complexity: Preprocessing: O(N + U log U); each query: O(log U), where U is the number of non-empty buckets. Space complexity: O(U).

Hints

1. Map each timestamp `t` to bucket `t // bucket_size` and count how many records fall in each bucket.
2. For a partial bucket, multiply that bucket's count by `overlap_length / bucket_size`.