Implement Stable Cursor Pagination

Implement Stable Cursor Paginationmedium

medium

Offset pagination can skip or repeat records when new rows are inserted between requests. Cursor pagination instead continues from a stable ordered key. When timestamps can tie, that key needs a deterministic secondary value.

Design a CursorPaginator class:

CursorPaginator() creates a stateless paginator.
int[] page(int[][] records, int cursorCreatedAt, int cursorId, int pageSize) returns the next record IDs.

Every record is [id, createdAt], and IDs are unique. Order records by:

createdAt descending.
id descending when timestamps are equal.

For the first page, both cursor values are -1. Otherwise, return only records strictly after the cursor in that descending order: a record qualifies when its createdAt is smaller than cursorCreatedAt, or when the timestamps are equal and its id is smaller than cursorId.

Return at most pageSize IDs. The cursor record may have been deleted and does not need to appear in records. Do not mutate the input matrix.

Example 1:

Input:

Output:

Explanation: Records 2 and 1 share timestamp 100, so the larger ID comes first. Record 3 is the next newest record.

Example 2:

Input:

Output:

Explanation: The cursor (100,2) is compared as a key rather than searched as a row. ID 1 is below it at timestamp 100, followed by the older records.

Constraints

0 <= records.length <= 10^4
records[i].length == 2
0 <= records[i][0], records[i][1] <= 10^9
Record IDs are unique.
Either cursorCreatedAt == cursorId == -1, or both cursor values are non-negative.
1 <= pageSize <= 10^4
At most 100 calls are made to page.

Hints

Call	Returns
new CursorPaginator()	null
page([[1,100],[2,100],[3,90],[4,80]], -1, -1, 3)	[2,1,3]

The first page sorts equal timestamps by descending ID, so records 2 and 1 precede record 3.

Run checks these cases. Submit also runs a larger hidden set.