Hard

Sequentially Ordinal Rank Tracker

LAB

Simulate add and get operations for scenic locations. get returns the name with rank equal to the number of get calls so far by higher score then smaller name.

EXAMPLES

Example 1

Input
{
  "operations": [
    "add",
    "add",
    "get",
    "add",
    "get"
  ],
  "names": [
    "bradford",
    "branford",
    "",
    "alps",
    ""
  ],
  "scores": [
    2,
    3,
    0,
    2,
    0
  ]
}

Output
[
  "branford",
  "alps"
]

FUNCTION SHAPE

operations: stringArraynames: stringArrayscores: intArray→stringArray

SOLUTION NOTE

Use (-score, name) tuple: negate score for descending sort, name for ascending tiebreaker. Track query count for sequential access.

Reveal reference solution +

pythonREFERENCE

class SORTracker:
    def __init__(self):
        from sortedcontainers import SortedList
        self.players = SortedList()
        self.query_count = 0

    def add(self, name: str, score: int) -> None:
        # Negate score for descending order
        # For same score, smaller name comes first (ascending)
        self.players.add((-score, name))

    def get(self) -> str:
        result = self.players[self.query_count][1]
        self.query_count += 1
        return result

TimeO(log n) add, O(log n) get

SpaceO(n)

Open on LeetCode ↗