Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Mo ordering: count distinct scan codes across an offline query batch

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

Mo ordering is an offline range-query plan for a frozen array. It groups requests by the block containing each left endpoint and sorts within a group by the right endpoint. A moving half-open window maintains a frequency counter and a distinct-key count. Adding a code changes the distinct count only when its old frequency was zero; removal changes it only when the new frequency becomes zero. Queries execute in reordered sequence, while answers return to their original request positions. This is useful when the aggregate can be updated cheaply by adding or removing one boundary element but does not have a compact prefix inverse. The program validates every request before moving the window.

Operational case

Seven scan codes are D47, D19, D47, D61, D19, D83, D47. Four requested windows are [1, 6), [0, 3), [3, 3), and [2, 7). Their distinct counts in original request order are four, two, zero, and four. The algorithm may answer those requests in a different order internally, so retaining each original position is essential. Duplicate D47 values should increase frequency without increasing the distinct count twice. Empty [3, 3) must return zero even if the previous processed window was nonempty. Changing a scan code after requests have been planned is outside this static implementation's contract.

Working Python program

python
from collections import Counter
from math import isqrt


def distinct_in_windows(scan_codes, windows):
    size = len(scan_codes)
    for start, stop in windows:
        if not 0 <= start <= stop <= size:
            raise IndexError("invalid half-open scan window")
    width = max(1, isqrt(size))
    ordered = sorted(enumerate(windows), key=lambda request: (request[1][0] // width, request[1][1]))
    counts = Counter()
    answers = [0] * len(windows)
    left = right = distinct = 0

    def add(position):
        nonlocal distinct
        code = scan_codes[position]
        if counts[code] == 0:
            distinct += 1
        counts[code] += 1

    def remove(position):
        nonlocal distinct
        code = scan_codes[position]
        counts[code] -= 1
        if counts[code] == 0:
            del counts[code]
            distinct -= 1

    for original, (start, stop) in ordered:
        while left > start:
            left -= 1
            add(left)
        while right < stop:
            add(right)
            right += 1
        while left < start:
            remove(left)
            left += 1
        while right > stop:
            right -= 1
            remove(right)
        answers[original] = distinct
    return answers


if __name__ == "__main__":
    codes = ["D47", "D19", "D47", "D61", "D19", "D83", "D47"]
    requests = [(1, 6), (0, 3), (3, 3), (2, 7)]
    print("distinct=", distinct_in_windows(codes, requests), sep="")

Output

Output
distinct=[4, 2, 0, 4]

Time, space, and tradeoff

With N values and Q requests, sorting requests takes O(Q log Q) time. A standard square-root block ordering makes O((N + Q) sqrt N) boundary moves in a conservative bound, with expected O(1) counter work per move under ordinary hash-map assumptions. Memory is O(N + Q) for the copied input, current frequencies, and answer list; the number of keys in the counter never exceeds N. Python sorting and hashing constants matter. For a handful of short windows, scanning a set over each requested slice is simpler. This program does not answer queries as they arrive, update values between queries, or claim that reordering is valid when answers determine later request endpoints.

Common Mistakes

  • Do not return answers in processing order instead of request order.
  • Do not change the distinct total on every duplicate add or partial removal.
  • Do not treat the stop endpoint as included.
  • Do not use offline reordering when later requests depend on earlier answers.

Connected lessons

Compare with Coordinate compression: preserve order with dense integer ranks, Fenwick frequency index: select the kth stored key, Two-dimensional prefixes: constant-time static rectangle sums, then run the query workload audit and contract quiz.

Persistent range-distinct counts: keep only the latest position active examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details