# Sequentially Ordinal Rank Tracker
**Difficulty:** HARD
[External](https://leetcode.com/problems/sequentially-ordinal-rank-tracker)
Canonical: https://scaleengineer.com/dsa/problems/sequentially-ordinal-rank-tracker
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream)
**Data structures:** Heap (Priority Queue), Ordered Set
---
## Problem
A scenic location is represented by its `name` and attractiveness `score`, where `name` is a **unique** string among all locations and `score` is an integer. Locations can be ranked from the best to the worst. The **higher** the score, the better the location. If the scores of two locations are equal, then the location with the **lexicographically smaller** name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

* **Adding** scenic locations, **one at a time**.
* **Querying** the `ith` **best** location of **all locations already added**, where `i` is the number of times the system has been queried (including the current query).  
  * For example, when the system is queried for the `4th` time, it returns the `4th` best location of all locations already added.

Note that the test data are generated so that **at any time**, the number of queries **does not exceed** the number of locations added to the system.

Implement the `SORTracker` class:

* `SORTracker()` Initializes the tracker system.
* `void add(string name, int score)` Adds a scenic location with `name` and `score` to the system.
* `string get()` Queries and returns the `ith` best location, where `i` is the number of times this method has been invoked (including this invocation).

**Example 1:**

**Input**
["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]
[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
**Output**
[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

**Explanation**
SORTracker tracker = new SORTracker(); // Initialize the tracker system.
tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.
tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.
tracker.get();              // The sorted locations, from best to worst, are: branford, bradford.
                            // Note that branford precedes bradford due to its **higher score** (3 > 2).
                            // This is the 1st time get() is called, so return the best location: "branford".
tracker.add("alps", 2);     // Add location with name="alps" and score=2 to the system.
tracker.get();              // Sorted locations: branford, alps, bradford.
                            // Note that alps precedes bradford even though they have the same score (2).
                            // This is because "alps" is **lexicographically smaller** than "bradford".
                            // Return the 2nd best location "alps", as it is the 2nd time get() is called.
tracker.add("orland", 2);   // Add location with name="orland" and score=2 to the system.
tracker.get();              // Sorted locations: branford, alps, bradford, orland.
                            // Return "bradford", as it is the 3rd time get() is called.
tracker.add("orlando", 3);  // Add location with name="orlando" and score=3 to the system.
tracker.get();              // Sorted locations: branford, orlando, alps, bradford, orland.
                            // Return "bradford".
tracker.add("alpine", 2);   // Add location with name="alpine" and score=2 to the system.
tracker.get();              // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
                            // Return "bradford".
tracker.get();              // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
                            // Return "orland".

**Constraints:**

* `name` consists of lowercase English letters, and is unique among all locations.
* `1 <= name.length <= 10`
* `1 <= score <= 105`
* At any time, the number of calls to `get` does not exceed the number of calls to `add`.
* At most `4 * 104` calls **in total** will be made to `add` and `get`.

# Approaches
## Brute Force: List and Sort on Get
This approach uses a simple `ArrayList` to store the locations. When a new location is added, it's just appended to the list. The main work is done in the `get()` method. Each time `get()` is invoked, it sorts the entire list of all locations added so far based on the specified ranking criteria. After sorting, it retrieves the i-th best location, where `i` corresponds to the number of times `get()` has been called.
**Time:** `add`: O(1) amortized time.
`get`: O(N log N), where N is the current number of locations. Sorting dominates the complexity. · **Space:** O(N), where N is the total number of locations added. We need to store all location objects.
**Pros:** Simple to understand and implement.; The `add` operation is very fast.
**Cons:** The `get()` operation is very inefficient because it requires sorting the entire list of locations every time it's called.; This approach will likely result in a 'Time Limit Exceeded' error for larger inputs due to the high time complexity of `get()`.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We use a dynamic array (like `ArrayList` in Java) to keep all the scenic locations. The `add` operation is simple: we just append the new location to our list. The `get` operation is where the inefficiency lies. We maintain a counter for how many times `get` has been called. For the `i`-th call to `get`, we need the `i`-th best location. To find this, we sort the entire list of `N` locations, which takes `O(N log N)` time. Then, we can directly access the `i`-th element (at index `i-1`) in `O(1)` time. While simple to implement, this approach is not scalable as the number of locations and queries grows.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class SORTracker {

    private static class Location {
        String name;
        int score;
        Location(String name, int score) { 
            this.name = name; 
            this.score = score; 
        }
    }

    private List<Location> locations;
    private int queryCount;

    public SORTracker() {
        locations = new ArrayList<>();
        queryCount = 0;
    }
    
    public void add(String name, int score) {
        locations.add(new Location(name, score));
    }
    
    public String get() {
        queryCount++;
        Collections.sort(locations, (a, b) -> {
            if (a.score != b.score) {
                return b.score - a.score; // Higher score first
            }
            return a.name.compareTo(b.name); // Lexicographically smaller name first
        });
        return locations.get(queryCount - 1).name;
    }
}
```
### Algorithm
1.  Define a `Location` class to hold the `name` and `score`.
2.  In the `SORTracker` class, use a `java.util.ArrayList` to store all the `Location` objects.
3.  Maintain a counter, `queryCount`, initialized to 0, to track the number of `get()` calls.
4.  **`add(name, score)`**: Create a new `Location` object and add it to the list. This is an O(1) operation (amortized).
5.  **`get()`**: 
    a. Increment `queryCount`.
    b. Sort the entire list of locations. The sorting criteria are: primarily by score in descending order, and secondarily by name in lexicographically ascending order.
    c. Access the element at index `queryCount - 1` in the sorted list.
    d. Return the name of this location.

## Sorted Set (TreeSet)
To avoid re-sorting the entire list on every `get()` call, we can use a data structure that keeps elements sorted at all times. A `TreeSet` (implemented as a balanced binary search tree) is a good candidate. When a new location is added, it's inserted into the `TreeSet` in logarithmic time, preserving the sorted order. However, to retrieve the i-th element, we still need to traverse the `TreeSet` from the start, which takes time proportional to `i`. This is an improvement over the brute-force approach for the `add` operation, but `get` can still be slow.
**Time:** `add`: O(log N), where N is the current number of locations.
`get`: O(K), where K is the number of times `get` has been called. In the worst case, this is O(N). · **Space:** O(N), where N is the total number of locations added, to store the `TreeSet`.
**Pros:** The `add` operation is efficient (`O(log N)`).; The collection of locations is always kept in a sorted state, which is conceptually clean.
**Cons:** The `get()` operation is still slow with a linear time complexity, as `TreeSet` does not support efficient indexed access.; For a large number of `get()` calls, the repeated iteration from the beginning becomes a bottleneck.
### Explanation
This approach improves upon the brute-force method by using a data structure that maintains elements in a sorted order, a `TreeSet`. We provide a custom comparator to the `TreeSet` to define our specific ranking criteria. The `add` operation becomes more efficient, as inserting into a balanced binary search tree takes `O(log N)` time. The `get` operation, however, remains a performance issue. Since `TreeSet` does not provide a method to get an element by its rank in `O(1)` or `O(log N)`, we are forced to iterate. For the `i`-th call to `get`, we must start an iterator from the beginning and advance it `i` times. This results in an `O(i)` time complexity for the `get` operation, which can be as bad as `O(N)` in the worst case.

```java
import java.util.Iterator;
import java.util.TreeSet;

class SORTracker {

    private static class Location {
        String name;
        int score;
        Location(String name, int score) { 
            this.name = name; 
            this.score = score; 
        }
    }

    private TreeSet<Location> sortedLocations;
    private int queryCount;

    public SORTracker() {
        sortedLocations = new TreeSet<>((a, b) -> {
            if (a.score != b.score) {
                return b.score - a.score;
            }
            return a.name.compareTo(b.name);
        });
        queryCount = 0;
    }
    
    public void add(String name, int score) {
        sortedLocations.add(new Location(name, score));
    }
    
    public String get() {
        queryCount++;
        Iterator<Location> it = sortedLocations.iterator();
        Location result = null;
        for (int i = 0; i < queryCount; i++) {
            result = it.next();
        }
        return result.name;
    }
}
```
### Algorithm
1.  Define a `Location` class.
2.  Use a `java.util.TreeSet` to store the `Location` objects. The `TreeSet` is initialized with a custom `Comparator` that enforces the desired ranking order (score descending, name ascending).
3.  Maintain a counter, `queryCount`, initialized to 0.
4.  **`add(name, score)`**: Create a new `Location` object and add it to the `TreeSet`. The `TreeSet` automatically maintains the sorted order, making insertion an `O(log N)` operation.
5.  **`get()`**: 
    a. Increment `queryCount`.
    b. To find the `queryCount`-th best location, we must iterate through the `TreeSet` from the beginning.
    c. Create an iterator for the `TreeSet` and call `next()` `queryCount` times.
    d. The last element retrieved from the iterator is the desired location. Return its name.

## Optimal: Two Priority Queues (Heaps)
This optimal approach recognizes that the `get()` operation sequentially asks for the 1st, 2nd, 3rd, ... best location. This moving rank suggests partitioning the locations into two groups around the current rank `i`. We use two priority queues (heaps) to maintain this partition efficiently.

One heap, a max-heap, stores the `i` best locations found so far. Its top element is the `i`-th best location, which is exactly what `get()` needs to return. The other heap, a min-heap, stores all other locations. Its top element is the `(i+1)`-th best location, ready to be promoted on the next `get()` call.

Both `add` and `get` operations involve moving at most one element between the heaps, which takes logarithmic time. This makes both operations highly efficient.
**Time:** `add`: O(log N)
`get`: O(log N)
where N is the current number of locations. · **Space:** O(N), where N is the total number of locations added. We need to store all location objects across two heaps.
**Pros:** Highly efficient, with logarithmic time complexity for both `add` and `get` operations.; Scales well for a large number of locations and queries.
**Cons:** The implementation is more complex than the previous approaches.; Requires careful handling of comparators for the two heaps.
### Explanation
The most efficient solution uses two priority queues to maintain a dynamic partition of the locations. Let's call them `retrievedLocations` and `candidateLocations`.

-   `retrievedLocations`: This will be a **max-heap** according to our ranking criteria (higher score/smaller name is better). It will store the `i` locations that have been 'retrieved' by the `get` method. The element at the top of this heap will be the *worst* among these `i` locations, which is precisely the `i`-th best location overall. In Java, a `PriorityQueue` is a min-heap, so to simulate a max-heap for our custom ranking, we provide a reversed comparator.

-   `candidateLocations`: This will be a **min-heap** using the natural ranking criteria. It stores all other locations. The element at its top is the best among this group, which is the `(i+1)`-th best location overall.

The `add` operation adds a new location and rebalances the heaps to maintain the partition. A clever way to do this is to add the new location to `retrievedLocations` and then move the top element of `retrievedLocations` to `candidateLocations`. This ensures the sizes are maintained and the new location ends up in the correct heap.

The `get` operation involves moving the top element from `candidateLocations` to `retrievedLocations`, effectively increasing the number of 'retrieved' items by one. The new top of `retrievedLocations` is then the answer.

This design ensures that both `add` and `get` operations have a time complexity of `O(log N)`. 

```java
import java.util.Comparator;
import java.util.PriorityQueue;

class SORTracker {

    private static class Location {
        String name;
        int score;
        Location(String name, int score) { 
            this.name = name; 
            this.score = score; 
        }
    }

    // Stores the locations that are candidates for future get() calls.
    // It's a min-heap, so peek() returns the best location among candidates.
    private PriorityQueue<Location> candidateLocations;

    // Stores the top-i locations that have been effectively 'retrieved' by get().
    // It's a max-heap, so peek() returns the worst among them (the i-th best location).
    private PriorityQueue<Location> retrievedLocations;

    public SORTracker() {
        // Comparator for ranking: higher score is better, then lexicographically smaller name.
        Comparator<Location> comp = (a, b) -> {
            if (a.score != b.score) {
                return a.score - b.score; // Natural order for score
            }
            return b.name.compareTo(a.name); // Reversed order for name
        };

        // Min-heap based on the reversed comparator (effectively a max-heap on our ranking)
        this.retrievedLocations = new PriorityQueue<>(comp);
        // Max-heap based on the reversed comparator (effectively a min-heap on our ranking)
        this.candidateLocations = new PriorityQueue<>(comp.reversed());
    }
    
    public void add(String name, int score) {
        Location loc = new Location(name, score);
        retrievedLocations.add(loc);
        candidateLocations.add(retrievedLocations.poll());
    }
    
    public String get() {
        retrievedLocations.add(candidateLocations.poll());
        return retrievedLocations.peek().name;
    }
}
```
*Note: The comparator logic in the code snippet is adjusted to create the desired min/max heap behavior with Java's default `PriorityQueue` implementation.*
### Algorithm
1.  Maintain two priority queues (heaps).
    a. A **max-heap** (`retrievedLocations`) to store the top `i` locations, where `i` is the number of `get()` calls. The heap is ordered such that `peek()` returns the *worst* among these `i` locations (i.e., the `i`-th best location).
    b. A **min-heap** (`candidateLocations`) to store the rest of the locations. The heap is ordered such that `peek()` returns the *best* among the rest (i.e., the `(i+1)`-th best location).
2.  **`add(name, score)`**: To maintain the partition correctly without changing the number of retrieved locations (`i`), we use a simple balancing trick:
    a. Add the new location to the `retrievedLocations` (max-heap).
    b. Immediately move the top element from `retrievedLocations` to `candidateLocations` (min-heap).
    c. This ensures the new location is correctly placed on either side of the `i`-th rank boundary, and the size of `retrievedLocations` remains `i`.
3.  **`get()`**: This operation signifies that we are now interested in the `(i+1)`-th rank.
    a. Move the top element from `candidateLocations` (the `(i+1)`-th best) to `retrievedLocations`.
    b. The size of `retrievedLocations` is now `i+1`.
    c. The top of `retrievedLocations` is now the new `i`-th best location. Return its name.

# Solutions
### CPP

```cpp
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> using namespace __gnu_pbds ; template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update > ; class SORTracker { public: SORTracker () { } void add ( string name , int score ) { st . insert ({ - score , name }); } string get () { return st . find_by_order ( ++ i ) -> second ; } private: ordered_set < pair < int , string >> st ; int i = - 1 ; }; /** * Your SORTracker object will be instantiated and called as such: * SORTracker* obj = new SORTracker(); * obj->add(name,score); * string param_2 = obj->get(); */
```

### Python

```python
from sortedcontainers import SortedList class SORTracker : def __init__ ( self ): self . sl = SortedList () self . i = - 1 def add ( self , name : str , score : int ) -> None : self . sl . add (( - score , name )) def get ( self ) -> str : self . i += 1 return self . sl [ self . i ][ 1 ] # Your SORTracker object will be instantiated and called as such: # obj = SORTracker() # obj.add(name,score) # param_2 = obj.get()
```