Sequentially ordinal rank tracker

Design Heap (Priority Queue) Data Stream Ordered Set

61.5% acceptance

Feb 23, 2026

407

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

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeSet;

pub struct SORTracker {
  // left: top `rank` elements (answered so far). Key: (-score, name). Max = last answered.
  left: BTreeSet<(i32, String)>,
  // right: remaining elements. Key: (-score, name). Min = next to answer.
  right: BTreeSet<(i32, String)>,
}

impl SORTracker {
  pub fn new() -> Self {
    SORTracker {
      left: BTreeSet::new(),
      right: BTreeSet::new(),
    }
  }

  pub fn add(&mut self, name: String, score: i32) {
    let key = (-score, name);
    self.right.insert(key);
    // Rebalance: the best element in right must be <= worst in left
    if !self.left.is_empty() {
      let right_min = self.right.iter().next().unwrap().clone();
      let left_max = self.left.iter().next_back().unwrap().clone();
      if right_min < left_max {
        self.right.remove(&right_min);
        self.left.remove(&left_max);
        self.right.insert(left_max);
        self.left.insert(right_min);
      }
    }
  }

  pub fn get(&mut self) -> String {
    // Move min of right to left, return its name
    let right_min = self.right.iter().next().unwrap().clone();
    self.right.remove(&right_min);
    let name = right_min.1.clone();
    self.left.insert(right_min);
    name
  }
}