Katkat
Back

Every Reachable Priority Gap After At Most One Bounded Bump

CitadelSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Given n network ports each tagged with a priority code below n, find every value the lowest unused priority code could take after at most one bounded increment. Tests careful case analysis of how a single bump opens or closes a gap, and returning the answer efficiently.

A router has n ports. Port i carries a priority tag tags[i], and every tag satisfies 0 <= tags[i] < n. Multiple ports may share the same tag. You may perform at most one operation: pick a single port whose tag is less than n - 1 and increase its tag by 1 (a tag of n - 1 can never be bumped, since tags must stay below n).

The priority gap of the tag assignment is the smallest non-negative integer that is not used by any port — this is the next priority class the scheduler would hand out. Return every priority gap value reachable by performing either zero operations or exactly one.

Function Signature

def reachable_priority_gaps(tags: list[int]) -> list[int]:

Rules

  • An operation chooses one index i with tags[i] < n - 1 and replaces tags[i] with tags[i] + 1. Doing nothing is always allowed, so the gap of the original array is always reachable.
  • Each candidate operation is evaluated independently, starting from the original array — operations are not applied in sequence.
  • Return the distinct reachable gap values in strictly increasing order.

Constraints

  • 1 <= n == len(tags) <= 10^5
  • 0 <= tags[i] <= n - 1, and values may repeat.

Examples

Example 1

Input:  tags = [2, 0, 1]
Output: [0, 1, 3]

No operation leaves the gap at 3 (every value 0, 1, 2 is used). Bumping the port tagged 0 gives [2, 1, 1], whose gap is 0. Bumping a port tagged 1 gives [2, 0, 2], whose gap is 1. The port tagged 2 equals n - 1 and can't be bumped, so a gap of 2 is unreachable.

Example 2

Input:  tags = [0, 0, 2, 2]
Output: [1, 3]

No operation leaves the gap at 1. Bumping one of the 2-tagged ports gives [0, 0, 3, 2], whose gap is still 1, since tag 2 sits above the gap and doesn't touch it. Bumping one of the 0-tagged ports gives [1, 0, 2, 2]: one port is still tagged 0, so 0 remains used, but now a port is tagged 1 too — the gap jumps all the way to 3, since 0, 1 and 2 are all used and 3 is not.

Example 3

Input:  tags = [4, 1, 1, 0, 3]
Output: [0, 2, 5]

No operation leaves the gap at 2 (0, 1, 3, 4 are used, 2 is not). Bumping the tag-0 port gives [4, 1, 1, 1, 3], whose gap is 0. Bumping one of the tag-1 ports gives [4, 1, 2, 0, 3]: now 0, 1, 2, 3, 4 are all used, so the gap jumps all the way to 5.

Hints

Hint 1

Start from the gap of the untouched array; call it g. Any port tagged below g is guaranteed to exist.

Hint 2

If a port's tag v < g is the only port carrying that tag, bumping it immediately creates a new, smaller gap at v — work out why nothing above v matters once that happens.

Hint 3

The one subtle case: bumping a tag of g - 1 when there's a spare copy of it doesn't remove g - 1, but it does fill in g itself. Where does the gap move to then?

Hint 4

You never need to recompute the gap from scratch for every possible bump — express the answer using just the frequency counts and a couple of targeted scans.

Follow-up questions

  • How would the answer change if up to two bumps were allowed instead of one?
  • How would you support this as an online structure where tags are bumped one at a time and you need the current gap after each real bump, not just the reachable set?
  • What's the largest possible size of the reachable set as a function of n, and for what kind of input is it achieved?
  • How would you adapt this if ports could also be removed, not just bumped?