Mo's Algorithm Query Order

Problem

Given the array length n and queries as [left, right] pairs, return the indices of the queries in the order Mo's algorithm would process them.

The left endpoint is bucketed into blocks of size roughly the square root of n, and within a block the right endpoint is sorted ascending for even blocks and descending for odd blocks, which keeps the right pointer mostly monotone.

Hint

Python's sort is stable, so equal keys keep their original relative order.

Test cases

case 1

in: [10,[[0,9],[1,3],[2,5],[4,8],[0,0],[5,9]]]

expected: [4,1,2,0,5,3]

case 2

in: [4,[[0,3],[1,2],[0,0]]]

expected: [2,1,0]

case 3

in: [1,[[0,0]]]

expected: [0]

case 4

in: [6,[]]

expected: []

case 5

in: [9,[[0,8],[1,1],[2,2]]]

expected: [1,2,0]

Starter codePython

def mos_query_order(n, queries):
    # Your code here
    pass

5 test cases · run your code against them in the editor