# 744. Find Smallest Letter Greater Than Target

## 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 <= 104
• letters[i] is a lowercase English letter.
• letters is sorted in non-decreasing order.
• letters contains at least two different characters.
• target is a lowercase English letter.

## Solutions

• class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int left = 0, right = letters.length;
while (left < right) {
int mid = (left + right) >> 1;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % letters.length];
}
}

• class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int left = 0, right = letters.size();
while (left < right) {
int mid = left + right >> 1;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % letters.size()];
}
};

• class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
left, right = 0, len(letters)
while left < right:
mid = (left + right) >> 1
if ord(letters[mid]) > ord(target):
right = mid
else:
left = mid + 1
return letters[left % len(letters)]


• func nextGreatestLetter(letters []byte, target byte) byte {
left, right := 0, len(letters)
for left < right {
mid := (left + right) >> 1
if letters[mid] > target {
right = mid
} else {
left = mid + 1
}
}
return letters[left%len(letters)]
}

• function nextGreatestLetter(letters: string[], target: string): string {
const n = letters.length;
let left = 0;
let right = letters.length;
while (left < right) {
let mid = (left + right) >>> 1;
if (letters[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return letters[left % n];
}


• class Solution {
/**
* @param String[] $letters * @param String$target
* @return String
*/
function nextGreatestLetter($letters,$target) {
$left = 0;$right = count($letters); while ($left <= $right) {$mid = floor($left + ($right - $left) / 2); if ($letters[$mid] >$target) {
$right =$mid - 1;
} else {
$left =$mid + 1;
}
}
if ($left >= count($letters)) {
return $letters[0]; } else { return$letters[\$left];
}
}
}

• impl Solution {
pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
let n = letters.len();
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if letters[mid] > target {
right = mid;
} else {
left = mid + 1;
}
}
letters[left % n]
}
}