392. Next Letter Up
A choir director has a sorted list of the letters printed on the sheet music stands, each a lowercase English letter, and the list may repeat letters. She calls out a letter target and wants the next letter in the list that comes strictly after it in the alphabet.
Given the sorted array letters and the character target, return the smallest letter in letters that is strictly greater than target. The alphabet wraps around: if no letter is greater, return the first letter of letters. The array contains at least two different letters. Aim for O(log n) time.
Example 1
- Input:
- letters = ["b","e","h","k"], target = "f"
- Output:
- "h"
- Explanation:
The letters greater than f are h and k, and the smallest is h.
Example 2
- Input:
- letters = ["m","p","t"], target = "t"
- Output:
- "m"
- Explanation:
No letter is greater than t, so the answer wraps around to the first letter, m.
Constraints
2 ≤ letters.length ≤ 104letters[i] and target are lowercase English letters.letters is sorted in non-decreasing order and contains at least two different letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)