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:
ith best location of all locations already added, where i is the number of times the system has been queried (including the current query).
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 <= 101 <= score <= 105get does not exceed the number of calls to add.4 * 104 calls in total will be made to add and get.Problem Overview: You design a data structure that receives location entries as (name, score) and repeatedly returns the next best location in rank order. Ranking is based on higher score first, and lexicographically smaller name as the tie breaker. Every call to get() should return the next location in the sorted ranking without recomputing the entire order.
Approach 1: Balanced Tree for Dynamic Sorting (O(log n) time per operation, O(n) space)
Maintain all locations in a balanced ordered structure such as TreeSet, SortedList, or another balanced BST keyed by (-score, name). This keeps the elements automatically sorted by rank. Each add(name, score) inserts the element into the tree in O(log n). A pointer or iterator tracks the index of the next result for get(). Because the structure remains sorted at all times, the next ranked location can be returned in O(log n) or O(1) depending on the implementation. This approach is straightforward and mirrors the problem statement directly: maintain global ordering and walk through it sequentially. It relies on data structures commonly discussed in ordered set or balanced tree problems.
Approach 2: Min-Heap for Efficient Retrieval (O(log n) time per operation, O(n) space)
A more interview-friendly design uses two heaps to track the boundary between returned and unreturned ranks. Maintain a max-heap for candidates that have not yet been returned and a min-heap containing the top k ranked elements already considered for retrieval. When a new location arrives via add(), push it into the max-heap ordered by score and name. During get(), move the best candidate into the min-heap so it becomes the next ranked element and return the top of that structure. The heaps maintain the ordering invariant while supporting fast inserts and rank adjustments. Each push or pop costs O(log n). This technique is common in heap (priority queue) and data stream problems where the dataset grows over time and queries interleave with updates.
Recommended for interviews: The heap-based approach is typically what interviewers expect. It demonstrates that you can maintain dynamic rankings without sorting the entire dataset after every insertion. Implementing the two-heap boundary shows strong understanding of priority queues and streaming data structures. The balanced tree solution is still valid and easier to reason about, but the heap design highlights deeper algorithmic thinking and control over ranking boundaries.
This approach takes advantage of balanced tree structures, such as a TreeSet or SortedSet, to keep the list of scenic locations sorted by score and name dynamically.
For each add operation, insert the location into the tree in the correct order. For each get operation, simply retrieve the ith best location, which ensures O(log n) complexity for each operation, making it efficient for large data.
In this solution, we use the SortedList from the sortedcontainers module in Python to keep all locations sorted by score in descending order. The scores are negated to simulate a max-heap behavior, as the default sort is ascending. The add method inserts elements in O(log n) time, and the get method returns the location at the current query index.
Time Complexity: O(log n) per add operation, O(1) per get operation.
Space Complexity: O(n) for storing locations.
A priority queue (min-heap) provides an efficient way to manage the top k elements, maintaining the best k locations required by queries. This approach keeps a fixed-size heap which gets adjusted when new scores are added.
This solution leverages a heapq to keep track of the locations ordered by score. The scores with lowest values are popped off the heap while maintaining the correct kth location for retrieval. The heap effectively manages capacity sizing automatically.
Python
JavaScript
Time Complexity: O(log n) for adding to heap, O(1) for getting the top element.
Space Complexity: O(n).
We can use an ordered set to store the attractions, and a variable i to record the current number of queries, initially i = -1.
When calling the add method, we take the negative of the attraction's rating, so that we can use the ordered set to sort by rating in descending order. If the ratings are the same, sort by the dictionary order of the attraction names in ascending order.
When calling the get method, we increment i by one, and then return the name of the i-th attraction in the ordered set.
The time complexity of each operation is O(log n), where n is the number of added attractions. The space complexity is O(n).
We notice that the query operations in this problem are performed in strictly increasing order. Therefore, we can use a method similar to the median in the data stream. We define two priority queues good and bad. good is a min-heap, storing the current best attractions, and bad is a max-heap, storing the current i-th best attraction.
Each time the add method is called, we add the attraction's rating and name to good, and then add the worst attraction in good to bad.
Each time the get method is called, we add the best attraction in bad to good, and then return the worst attraction in good.
The time complexity of each operation is O(log n), where n is the number of added attractions. The space complexity is O(n).
| Approach | Complexity |
|---|---|
| Approach 1: Balanced Tree for Dynamic Sorting | Time Complexity: O(log n) per add operation, O(1) per get operation. |
| Approach 2: Min-Heap for Efficient Retrieval | Time Complexity: O(log n) for adding to heap, O(1) for getting the top element. |
| Ordered Set | — |
| Double Priority Queue (Min-Max Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Balanced Tree / Ordered Set | O(log n) per add, O(1)-O(log n) per get | O(n) | When a language provides built-in ordered sets or balanced BST structures |
| Two Heaps (Min-Heap + Max-Heap) | O(log n) per operation | O(n) | Best for interview settings and streaming scenarios where elements are added continuously |
Sequentially Ordinal Rank Tracker |Leetcode 2102|Live coding session 🔥🔥🔥🔥| Leetcode Hard|Contest 67 • Coding Decoded • 1,550 views views
Watch 5 more video solutions →Practice Sequentially Ordinal Rank Tracker with our built-in code editor and test cases.
Practice on FleetCode