A data structure puzzle

Jarno Alanko offered this puzzle on twitter:

Fun but difficult data structure puzzle with an elegant solution: Suppose we have an oracle to a permutation f on n elements. Describe a data structure taking O(sqrt(n)) space that can compute the inverse f^(-1)(x) for any x in O(sqrt(n)) time.

— Jarno N. Alanko (@jnalanko) May 22, 2021

Here’s my solution. It’s a programmer’s solution: it assumes that integers take \(O(1)\) space and hash maps allow \(O(1)\) lookups. If you know a solution that doesn’t make these assumptions, please let me know!

So, consider the decomposition of \(f\) into disjoint cycles. For every cycle that has \(k > \sqrt{n}\) elements, arbitrarily pick \(\lceil k / \sqrt{n}\rceil\) elements—“breakpoints”—such that, when moving along the cycle, the distance between any two breakpoints is at most \(\sqrt{n}\). Since there are fewer than \(\sqrt{n}\) such cycles, the total number of breakpoints is

\[ \sum_i \lceil k_i / \sqrt{n}\rceil < \sum_i (k_i / \sqrt{n}+1) < 2\sqrt{n}. \]

Store all the breakpoints in a hash map \(h\) that maps each breakpoint to the previous breakpoint in the same cycle. Then, to invert an element \(x\), use the following algorithm:

x1 := x
x2 := f(x)
while (x2 != x):
  if h contains x1:
    x1 := h(x1)
  else:
    x1 := x2
  x2 := f(x1)
return x1

This algorithm finds the inverse element by iteratively applying \(f\) until it comes back to \(x\). The hash map \(h\) provides a shortcut to instantaneously traverse a large part of the cycle. After less than \(\sqrt{n}\) iterations, the loop either finds \(x\) or finds a point \(x_1\) for which \(h(x_1)\) is defined. In the latter case, \(x\) lies (cycle-wise) in the interval \((h(x_1), x_1)\), and once the search is restarted from \(h(x_1)\), it will take less than \(\sqrt{n}\) additional loop iterations to locate \(x\).