Description
You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.
Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.
Example 1:
Input: letters = ["c","f","j"], target = "a" Output: "c" Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
Example 2:
Input: letters = ["c","f","j"], target = "c" Output: "f" Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.
Example 3:
Input: letters = ["x","x","y","y"], target = "z" Output: "x" Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
Constraints:
2 <= letters.length <= 104letters[i]is a lowercase English letter.lettersis sorted in non-decreasing order.letterscontains at least two different characters.targetis a lowercase English letter.
Solutions
This solution applies binary search to efficiently find the next greatest letter in O(log n) time. It maintains left and right pointers that narrow the search space by comparing the middle character to the target: if the middle character is too small, it moves left forward; otherwise, it moves right backward. Once the pointers converge, left points to the smallest character greater than the target, and if left reaches the array's end, it wraps around to the first character.
/**
* @param {character[]} letters
* @param {character} target
* @return {character}
*/
var nextGreatestLetter = function(letters, target) {
let left = 0;
let right = letters.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (letters[mid] <= target) {
left++;
} else {
right--;
}
}
return left === letters.length ? letters[0] : letters[left];
};