Algorithm
Problem Name: 744. Find Smallest Letter Greater Than Target
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.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int start = 0;
int end = letters.length - 1;
int minIdx = Integer.MAX_VALUE;
while (start < = end) {
int mid = (start + end) / 2;
if (letters[mid] > target) {
minIdx = mid;
end = mid - 1;
} else {
start = mid + 1;
}
}
return minIdx == Integer.MAX_VALUE ? letters[0] : letters[minIdx];
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const nextGreatestLetter = function (letters, target) {
const n = letters.length
if (target < letters[0] || target >= letters[n - 1]) return letters[0]
let left = 0
let right = n - 1
while (left < right) {
let mid = left + ((right - left) >> 1)
if (letters[mid] <= target) left = mid + 1
else right = mid
}
return letters[right]
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def nextGreatestLetter(self, letters, target):
return letters[bisect.bisect(letters, target) % len(letters)]
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0744_FindSmallestLetterGreaterThanTarget
{
public char NextGreatestLetter(char[] letters, char target)
{
int lo = 0, hi = letters.Length - 1;
while (lo < = hi)
{
var mid = lo + (hi - lo) / 2;
if (letters[mid] <= target) lo = mid + 1;
else hi = mid - 1;
}
return letters[lo % letters.Length];
}
}
}
Input
Output