Find Smallest Letter Greater Than Target
Problem
Given a sorted array of distinct lowercase letters and a target letter, find the smallest element in the array that is strictly greater than target. The letters wrap around — if every letter ≤ target, return letters[0].
letters = ["c", "f", "j"], target = "a""c"def next_greatest_letter(letters, target):
lo, hi = 0, len(letters)
while lo < hi:
mid = (lo + hi) // 2
if letters[mid] <= target:
lo = mid + 1
else:
hi = mid
return letters[lo % len(letters)]function nextGreatestLetter(letters, target) {
let lo = 0, hi = letters.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (letters[mid] <= target) lo = mid + 1;
else hi = mid;
}
return letters[lo % letters.length];
}class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int lo = 0, hi = letters.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (letters[mid] <= target) lo = mid + 1;
else hi = mid;
}
return letters[lo % letters.length];
}
}class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int lo = 0, hi = letters.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (letters[mid] <= target) lo = mid + 1;
else hi = mid;
}
return letters[lo % letters.size()];
}
};Explanation
We want the first letter that is strictly greater than the target in a sorted list. This is a classic "upper bound" binary search: find the leftmost position whose letter is bigger than target.
The window starts as [0, len). At each step, if letters[mid] <= target, that letter is too small (or equal), so the answer is further right and we set lo = mid + 1. Otherwise letters[mid] is a candidate, so we keep it by setting hi = mid.
When the loop ends, lo points at the first letter greater than the target. The wrap-around is handled neatly by letters[lo % len]: if every letter was <= target, lo equals the length and the modulo sends it back to index 0.
Example: letters = ["c","f","j"], target = "a". Every mid is greater than 'a', so hi keeps shrinking until lo = 0, giving 'c'. If the target were 'j' instead, lo would become 3 and 3 % 3 = 0 wraps to 'c'.
Each step halves the range, so the search runs in O(log n) time.