In this guide, you will get 2102. Sequentially Ordinal Rank Tracker LeetCode Solution with the best time and space complexity. The solution to Sequentially Ordinal Rank Tracker problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Sequentially Ordinal Rank Tracker
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).
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”.
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.
Complexity Analysis
Time Complexity: O(|\texttt{get()}|)
Space Complexity: O(|\texttt{add()}|)
2102. Sequentially Ordinal Rank Tracker LeetCode Solution in C++
struct Location {
string name;
int score;
Location(const string& name, int score)
: name(std::move(name)), score(score) {}
};
class SORTracker {
public:
void add(const string& name, int score) {
l.emplace(name, score);
if (l.size() > k + 1) {
const Location location = l.top();
l.pop();
r.emplace(location.name, location.score);
}
}
string get() {
const string name = l.top().name;
if (!r.empty()) {
const Location location = r.top();
r.pop();
l.emplace(location.name, location.score);
}
++k;
return name;
}
private:
struct CompareLeftMinHeap {
bool operator()(const Location& a, const Location& b) {
return a.score == b.score ? a.name < b.name : a.score > b.score;
}
};
struct CompareRightMaxHeap {
bool operator()(const Location& a, const Location& b) {
return a.score == b.score ? a.name > b.name : a.score < b.score;
}
};
priority_queue<Location, vector<Location>, CompareLeftMinHeap> l;
priority_queue<Location, vector<Location>, CompareRightMaxHeap> r;
int k = 0;
}; /* code provided by PROGIEZ */
2102. Sequentially Ordinal Rank Tracker LeetCode Solution in Java
class SORTracker {
public void add(String name, int score) {
l.offer(new Location(name, score));
if (l.size() > k + 1)
r.offer(l.poll());
}
public String get() {
final String name = l.peek().name;
if (!r.isEmpty())
l.offer(r.poll());
++k;
return name;
}
private record Location(String name, int score) {}
private Queue<Location> l =
new PriorityQueue<>(Comparator.comparing((Location a) -> a.score)
.thenComparing((Location a) -> a.name, Comparator.reverseOrder()));
private Queue<Location> r =
new PriorityQueue<>(Comparator.comparing((Location a) -> a.score, Comparator.reverseOrder())
.thenComparing((Location a) -> a.name));
private int k;
} // code provided by PROGIEZ
2102. Sequentially Ordinal Rank Tracker LeetCode Solution in Python
class Location:
def __init__(self, name: str, score: int):
self.name = name
self.score = score
def __lt__(self, location):
if self.score == location.score:
return self.name > location.name
return self.score < location.score
class SORTracker:
def __init__(self):
self.l = []
self.r = []
self.k = 0 the number of times get() called
def add(self, name: str, score: int) -> None:
heapq.heappush(self.l, Location(name, score))
if len(self.l) > self.k + 1:
location = heapq.heappop(self.l)
heapq.heappush(self.r, (-location.score, location.name))
def get(self) -> str:
name = self.l[0].name
if self.r:
topScore, topName = heapq.heappop(self.r)
heapq.heappush(self.l, Location(topName, -topScore))
self.k += 1
return name # code by PROGIEZ
