422. Find Smallest Letter Greater Than Target

Given a sorted array of characters letters and a character target, return the smallest character in letters that is strictly greater than target. Letters wrap around: if no character is greater, return letters[0].

Input: A sorted character array letters and a character target.

Output: The smallest character greater than target (wraps to letters[0] if none).

Examples

Input: ['c','f','j'], 'a'
Output: 'c'
Explanation: 'c' is the smallest letter greater than 'a'.

Input: ['c','f','j'], 'c'
Output: 'f'
Explanation: 'c' is not strictly greater than 'c'; next is 'f'.

Input: ['c','f','j'], 'j'
Output: 'c'
Explanation: No letter greater than 'j'; wrap around to letters[0]='c'.

Constraints

• 2 <= letters.length <= 10^4
• letters[i] is lowercase English letter
• letters is sorted in non-decreasing order
• letters has at least 2 distinct characters

Asked by