Skip to content

2102. Sequentially Ordinal Rank Tracker 👍

  • Time: Constructor: $O(1)$, add(name: str, score: int): $O(|\texttt{add(name: str, score: int)}|)$, get(): $O(|\texttt{get()}|)$
  • Space: $O(|\texttt{add(name: str, score: int)}|)$
 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
36
37
38
39
40
41
42
43
44
45
struct Location {
  string name;
  int score;
  Location(const string& name, int score) : name(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;
};
 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
class Location {
  public String name;
  public int score;
  public Location(String name, int score) {
    this.name = name;
    this.score = score;
  }
}

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 Queue<Location> l = new PriorityQueue<>(
      (a, b) -> a.score == b.score ? -a.name.compareTo(b.name) : a.score - b.score);
  private Queue<Location> r = new PriorityQueue<>(
      (a, b) -> a.score == b.score ? a.name.compareTo(b.name) : b.score - a.score);
  private int k;
}
 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
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  # 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