Sequentially Ordinal Rank Tracker

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).

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


**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 <= 10^5
At any time, the number of calls to get does not exceed the number of calls to add.
At most 4 * 10^4 calls in total will be made to add and get.

Solution

Method 1 – Two Heaps (Min-Heap and Max-Heap)

Intuition

To efficiently get the ith best location after each query, we use two heaps:

A max-heap (left) for the top i locations (best so far),
A min-heap (right) for the rest. On each get(), we move the best from right to left, so left always has i best locations, and the top of left is the ith best.

Approach

Use a max-heap (left) for the i best locations, ordered by (-score, name).
Use a min-heap (right) for the rest, ordered by (score, -name).
On add(name, score):
- Push to right, then move the best from right to left to maintain the invariant.
On get():
- Move the best from right to left so left has i elements.
- Return the top of left (ith best location).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <queue>
class SORTracker {
    typedef pair<int, string> PIS;
    priority_queue<PIS> left; // max-heap: (-score, name)
    priority_queue<PIS, vector<PIS>, greater<PIS>> right; // min-heap: (score, -name)
    int cnt = 0;
public:
    void add(string name, int score) {
        right.emplace(-score, name);
        left.push(right.top());
        right.pop();
    }
    string get() {
        ++cnt;
        right.push(left.top());
        left.pop();
        return right.top().second;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


import (
    "container/heap"
)
type item struct{score int; name string}
type maxHeap []item
func (h maxHeap) Len() int { return len(h) }
func (h maxHeap) Less(i, j int) bool {
    if h[i].score != h[j].score { return h[i].score > h[j].score }
    return h[i].name < h[j].name
}
func (h maxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *maxHeap) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
type minHeap []item
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool {
    if h[i].score != h[j].score { return h[i].score < h[j].score }
    return h[i].name > h[j].name
}
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
type SORTracker struct {
    left maxHeap
    right minHeap
}
func Constructor() SORTracker { return SORTracker{} }
func (s *SORTracker) Add(name string, score int) {
    heap.Push(&s.right, item{score, name})
    heap.Push(&s.left, heap.Pop(&s.right))
}
func (s *SORTracker) Get() string {
    heap.Push(&s.right, heap.Pop(&s.left))
    return s.right[0].name
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


import java.util.*;
class SORTracker {
    PriorityQueue<Location> left = new PriorityQueue<>((a, b) -> a.score != b.score ? b.score - a.score : a.name.compareTo(b.name));
    PriorityQueue<Location> right = new PriorityQueue<>((a, b) -> a.score != b.score ? a.score - b.score : b.name.compareTo(a.name));
    int cnt = 0;
    static class Location {
        int score; String name;
        Location(String n, int s) { name = n; score = s; }
    }
    public void add(String name, int score) {
        right.offer(new Location(name, score));
        left.offer(right.poll());
    }
    public String get() {
        right.offer(left.poll());
        return right.peek().name;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


import java.util.PriorityQueue
class SORTracker {
    data class Loc(val score: Int, val name: String)
    val left = PriorityQueue<Loc>(compareByDescending<Loc> { it.score }.thenBy { it.name })
    val right = PriorityQueue<Loc>(compareBy<Loc> { it.score }.thenByDescending { it.name })
    fun add(name: String, score: Int) {
        right.add(Loc(score, name))
        left.add(right.poll())
    }
    fun get(): String {
        right.add(left.poll())
        return right.peek().name
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


import heapq
class SORTracker:
    def __init__(self):
        self.left = []  # max-heap: (-score, name)
        self.right = [] # min-heap: (score, -name)
        self.k = 0
    def add(self, name: str, score: int) -> None:
        heapq.heappush(self.right, (-score, name))
        heapq.heappush(self.left, heapq.heappop(self.right))
    def get(self) -> str:
        heapq.heappush(self.right, heapq.heappop(self.left))
        return self.right[0][1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


use std::collections::BinaryHeap;
use std::cmp::Reverse;
struct SORTracker {
    left: BinaryHeap<(i32, String)>,
    right: BinaryHeap<Reverse<(i32, String)>>,
}
impl SORTracker {
    fn new() -> Self {
        SORTracker { left: BinaryHeap::new(), right: BinaryHeap::new() }
    }
    fn add(&mut self, name: String, score: i32) {
        self.right.push(Reverse((-score, name.clone())));
        self.left.push(self.right.pop().unwrap().0);
    }
    fn get(&mut self) -> String {
        self.right.push(Reverse(self.left.pop().unwrap()));
        self.right.peek().unwrap().0.1.clone()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Heap<T> {
    private data: T[] = [];
    constructor(private cmp: (a: T, b: T) => boolean) {}
    push(x: T) { this.data.push(x); this._up(this.data.length - 1); }
    pop(): T { const t = this.data[0], x = this.data.pop()!; if (this.data.length) { this.data[0] = x; this._down(0); } return t; }
    peek(): T { return this.data[0]; }
    _up(i: number) { const d = this.data, x = d[i]; while (i) { let p = (i - 1) >> 1; if (this.cmp(d[p], x)) break; d[i] = d[p]; i = p; } d[i] = x; }
    _down(i: number) { const d = this.data, n = d.length, x = d[i]; while (true) { let l = 2 * i + 1, r = l + 1, j = i; if (l < n && !this.cmp(d[j], d[l])) j = l; if (r < n && !this.cmp(d[j], d[r])) j = r; if (j === i) break; d[i] = d[j]; i = j; } d[i] = x; }
}
class SORTracker {
    left = new Heap<[number, string]>((a, b) => a[0] > b[0] || (a[0] === b[0] && a[1] < b[1]));
    right = new Heap<[number, string]>((a, b) => a[0] < b[0] || (a[0] === b[0] && a[1] > b[1]));
    add(name: string, score: number) {
        this.right.push([-score, name]);
        this.left.push(this.right.pop());
    }
    get(): string {
        this.right.push(this.left.pop());
        return this.right.peek()[1];
    }
}

Complexity

⏰ Time complexity: O(log n) per add/get, where n = number of locations, due to heap operations.
🧺 Space complexity: O(n), for storing all locations in the heaps.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 – Two Heaps (Min-Heap and Max-Heap)#

Intuition#

Approach#

Code#

Complexity#