Find Smallest Letter Greater Than Target
Find Smallest Letter Greater Than Target is a easy binary search problem solved with the bisect pattern.
The best approach, optimal (binary search for the upper bound), runs in O(log n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (linear scan) up.
Problem
You are given a list of lowercase letters letters, sorted in non-decreasing order, and a lowercase letter target.
Return the smallest letter in letters that is strictly greater than target. If there is no such letter, wrap around and return the first letter of the list.
Examples
Example 1
- Input
letters = ['b', 'd', 'g', 'g', 'm'], target = 'd'- Output
'g'- Why
- 'd' itself does not count because it is not strictly greater; the next letter in the list is 'g'.
Example 2
- Input
letters = ['e', 'k', 'p'], target = 'a'- Output
'e'- Why
- Every letter is greater than 'a', and 'e' is the smallest of them.
Example 3
- Input
letters = ['c', 'h', 'h', 'r'], target = 'r'- Output
'c'- Why
- No letter is greater than 'r', so the search wraps around and returns the first letter.
Constraints
2 <= letters.length <= 10^4letters[i]is a lowercase English letter.lettersis sorted in non-decreasing order and contains at least two different letters.targetis a lowercase English letter.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (linear scan) | O(n) | O(1) |
| Optimal (binary search for the upper bound) | O(log n) | O(1) |
1Brute force (linear scan)
O(n)In the worst case every letter is checked once.O(1)No extra storage.Walk the sorted list from the left and return the first letter that is strictly greater than target. If the loop finishes, nothing is greater, so wrap around to the first letter.
- For each letter c in order: if c > target, return c.
- Return letters[0].
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
for (char c : letters) {
if (c > target) return c;
}
return letters[0];
}
}class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
for c in letters:
if c > target:
return c
return letters[0]class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
for (char c : letters) {
if (c > target) return c;
}
return letters[0];
}
};function nextGreatestLetter(letters, target) {
for (const c of letters) {
if (c > target) return c;
}
return letters[0];
}2Optimal (binary search for the upper bound)
O(log n)The search range halves every step.O(1)Two indices.Because the list is sorted, all letters <= target form a prefix and all letters > target form the rest. Binary search for the boundary: keep a half-open range [lo, hi) and move lo past any middle letter that is not greater than the target. When the range closes, lo is the first greater letter, or n if none exists.
- lo = 0, hi = n.
- While lo < hi: mid = (lo + hi) / 2. If letters[mid] <= target, lo = mid + 1; otherwise hi = mid.
- Return letters[lo] if lo < n, else letters[0].
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 lo < letters.length ? letters[lo] : letters[0];
}
}class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
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] if lo < len(letters) else letters[0]class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int lo = 0, hi = letters.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (letters[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo < (int)letters.size() ? letters[lo] : letters[0];
}
};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 lo < letters.length ? letters[lo] : letters[0];
}Edge cases to test
targetis smaller than every letter: return the first lettertargetis greater than or equal to the last letter: wrap around toletters[0]targetappears several times; the answer must skip all of its copiestargetis not in the list at all but falls between two letters
Hints
Hint 1
You want the first position whose letter is strictly greater than target. The list is sorted, so what does that suggest?
Hint 2
Binary search for the leftmost index with letters[i] > target (an upper bound).
Hint 3
If that index is past the end, nothing is greater, so return letters[0].
FAQ
What is the best time complexity for Find Smallest Letter Greater Than Target?
Optimal (binary search for the upper bound) runs in O(log n) time and O(1) extra space. The search range halves every step.
Which pattern does Find Smallest Letter Greater Than Target use?
It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.
Is there a brute force solution for Find Smallest Letter Greater Than Target?
Yes. Brute force (linear scan) takes O(n) time and O(1) space. Walk the sorted list from the left and return the first letter that is strictly greater than target.
Which edge cases should I test for Find Smallest Letter Greater Than Target?
target is smaller than every letter: return the first letter; target is greater than or equal to the last letter: wrap around to letters[0]; target appears several times; the answer must skip all of its copies; target is not in the list at all but falls between two letters.