Next Gate Letter
EasyBinary Search
Problem
An airport labels its open gates with single lowercase letters, given in non-decreasing order as gates (a letter may be listed more than once). A passenger holds a boarding letter target.
Return the first open gate letter that comes strictly after target in the alphabet. If no such letter exists, wrap around and return the first letter in gates.
Example 1
- Input:
- gates = ["b", "e", "k"], target = "c"
- Output:
- "e"
"e" is the smallest gate letter greater than "c".
Example 2
- Input:
- gates = ["b", "e", "k"], target = "k"
- Output:
- "b"
Nothing is greater than "k", so the search wraps to the first gate.
Example 3
- Input:
- gates = ["a", "a", "d"], target = "a"
- Output:
- "d"
Constraints
- 2 ≤ gates.length ≤ 10^4
- gates[i] and target are lowercase letters
- gates is sorted in non-decreasing order and has at least two distinct letters.
Hint
Show the first hint
'Strictly greater' is a boundary: false for every letter ≤ target, true afterwards.
Walkthrough
How to approach it
01Clarify before coding
- Strictly greater or greater-or-equal? Strictly greater: an equal letter does not count.
- What if nothing is greater? Wrap around to gates[0].
- Can letters repeat? Yes, which is why you want the first strictly greater one, not any match.
02Brute force
Scan from the left and return the first letter greater than target, or gates[0] if none.
Cost: O(n) time, O(1) space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.