Merth and I devised a couple of reasonable solutions in SAX, I'll present them here a little more thoroughly. The general idea is similar to an LRU cache: pair a data structure that is good at ordering but bad at indexing with a data structure that is good at indexing but bad at ordering.
Let's define some notation for this problem. Your input array of integers is
A, and
i is the index of the element you just visited.
I'll present two equivalent solutions here. The first uses more storage but is more explicit. The second uses less storage but is a little more opaque.
Solution 1
Our first data structure is a doubly linked list, complete with start and end pointers. The invariant we'll maintain in this list is "if node A comes before node B, then A was used less recently than B".
Our second data structure is an array containing pointers. This array has the same size
n as the input array of integers, and the
ith element is a pointer to the linked list node holding the
ith element.
To visit an element of the input array, we move it to the back of the linked list. We can then retrieve the most recently visited element, remove it from the doubly linked list, and add it back to the end. Effectively, this is removing an element from a stack and pushing it back on top. The bottom of the stack is the least recently visited element. We use a Doubly Linked List to implement our stack for the O(1) operations.
From SAX: (not rewriting this
)
I wrote:
call our doubly linked list DLL and our array map AM. When accessing element with index i, retrieve a pointer to its DLL node by accessing AM[i]. Then, we move this DLL node (call it DLL_i) to the end of the doubly linked list. Update DLL_i's predecessor to point to its successor and its successor to point to its predecessor. If DLL_i's predecessor was null, then its successor is the new head of the DLL & is also the least recently used element. Update the old last element of the DLL to have DLL_i as its successor (also update DLL_i to have the old last element as its predecessor) and update DLL_i to have no successor. Return the head of the DLL as the least recently used element
.
Solution 2
We don't actually need to use that many pointers. We can store the predecessors and successors in separate arrays, each indexed in the same way as AM. predecessors[i] would then give the unique index i' such that node i' has node i as a successor.
This solution uses more or less the same update logic as the first solution. 
