Constraints

• 0 <= len(codes) <= 10^4 and all codes are distinct.
• 0 <= total number of records across all batches <= 2 * 10^5.
• Every record code belongs to codes.
• Timestamps are globally non-decreasing, and codes are lexicographically sorted within each timestamp.
• Each (timestamp, code) appears at most once.

Examples

Solution

def solution(codes, batches):
    sorted_codes = sorted(codes)
    m = len(sorted_codes)
    result = []
    current_ts = None
    current_row = None
    code_ptr = 0

    for batch in batches:
        for ts, code, value in batch:
            if current_ts is None or ts != current_ts:
                if current_ts is not None:
                    while code_ptr < m:
                        current_row.append(-1)
                        code_ptr += 1
                    result.append((current_ts, current_row))
                current_ts = ts
                current_row = []
                code_ptr = 0

            while code_ptr < m and sorted_codes[code_ptr] < code:
                current_row.append(-1)
                code_ptr += 1

            if code_ptr < m and sorted_codes[code_ptr] == code:
                current_row.append(value)
                code_ptr += 1
            else:
                raise ValueError('Record code not present in codes list or input order invalid')

    if current_ts is not None:
        while code_ptr < m:
            current_row.append(-1)
            code_ptr += 1
        result.append((current_ts, current_row))

    return result

Time complexity: O(M log M + T * M + R), where M is the number of codes, T is the number of emitted timestamps, and R is the number of input records.. Space complexity: O(M) auxiliary space, excluding the returned output..

Hints

1. You only need to keep one row in memory at a time: the current timestamp's row.
2. Because codes for the same timestamp are already sorted, you can walk through the sorted code list with a pointer and fill missing positions with -1.

Constraints

• 0 <= len(codes) <= 10^4 and all codes are distinct.
• 0 <= total number of records across all batches <= 2 * 10^5.
• Every record code belongs to codes.
• Timestamps are globally non-decreasing, so records for one timestamp stay contiguous.
• Codes within a timestamp may appear in any order; repeated (timestamp, code) pairs use last-write-wins.

Examples

Solution

def solution(codes, batches):
    sorted_codes = sorted(codes)
    index = {code: i for i, code in enumerate(sorted_codes)}
    m = len(sorted_codes)
    result = []
    current_ts = None
    current_row = None

    for batch in batches:
        for ts, code, value in batch:
            if current_ts is None or ts != current_ts:
                if current_ts is not None:
                    result.append((current_ts, current_row))
                current_ts = ts
                current_row = [-1] * m

            current_row[index[code]] = value

    if current_ts is not None:
        result.append((current_ts, current_row))

    return result

Time complexity: O(M log M + T * M + R), where M is the number of codes, T is the number of emitted timestamps, and R is the number of input records.. Space complexity: O(M) auxiliary space, excluding the returned output..

Hints

1. The timestamp order guarantee still lets you keep only one active row at a time.
2. Precompute a dictionary from code to column index so you can write directly into the correct cell even when codes arrive out of order.

Constraints

• 0 <= len(codes) <= 10^4 and all codes are distinct.
• 0 <= total number of records across all batches <= 2 * 10^5.
• 0 <= max_lag.
• Every record code belongs to codes. Codes within a timestamp may be in any order, and repeated (timestamp, code) pairs use last-write-wins.
• Bounded lateness guarantee: each arriving record satisfies timestamp >= max_seen_so_far - max_lag.

Examples

Solution

def solution(codes, batches, max_lag):
    from heapq import heappush, heappop

    sorted_codes = sorted(codes)
    index = {code: i for i, code in enumerate(sorted_codes)}
    m = len(sorted_codes)

    active = {}
    heap = []
    emitted_per_batch = []
    max_seen = None

    def flush_safe(cutoff):
        out = []
        while heap and heap[0] <= cutoff:
            ts = heappop(heap)
            out.append((ts, active.pop(ts)))
        return out

    for batch in batches:
        for ts, code, value in batch:
            if max_seen is None or ts > max_seen:
                max_seen = ts

            if ts not in active:
                active[ts] = [-1] * m
                heappush(heap, ts)

            active[ts][index[code]] = value

        cutoff = float('-inf') if max_seen is None else max_seen - max_lag
        emitted_per_batch.append(flush_safe(cutoff))

    final_flush = []
    while heap:
        ts = heappop(heap)
        final_flush.append((ts, active.pop(ts)))
    emitted_per_batch.append(final_flush)

    return emitted_per_batch

Time complexity: O(M log M + R + U log U + T * M), where M is the number of codes, R is the number of input records, U is the number of distinct timestamps that ever become active, and T is the number of emitted timestamps.. Space complexity: O(A * M + A + M), where A is the maximum number of active timestamps kept before they become safe to emit..

Hints

1. Track the largest timestamp seen so far; then max_seen - max_lag acts like a watermark for what is safe to emit.
2. Use a dictionary for active rows and a min-heap of active timestamps so you can flush the smallest safe timestamps in order.