Community Problem
Find Smallest Letter Greater Than Target
Difficulty: Easy
Classic upper_bound on a sorted character array, with a wrap-around twist that makes the binary-search invariants worth thinking through carefully.
Find Smallest Letter Greater Than Target
Classic upper_bound on a sorted character array, with a wrap-around twist that makes the binary-search invariants worth thinking through carefully.
By CodeSnatch
March 27, 2026
·
Updated May 18, 2026
761 views
10
4.6 (13)
Picked this for the EASY-tier official Cat 4 entry because off-by-one bugs in upper_bound are the single most common mistake I see in real onsites, and the wrap-around twist forces you to be honest about whether your invariant covers the not-found case. The half-open [lo, hi) template is the version that survives senior interviews unscathed.
Find Smallest Letter Greater Than Target
Given a sorted (non-decreasing) array of lowercase characters letters and a target lowercase character target, return the smallest character in letters that is strictly greater than target. Duplicates are allowed in letters. The comparison wraps around: if every character in letters is <= target, the answer is letters[0].
Examples
Example 1:
- Input:
letters = ['c', 'f', 'j'],target = 'a' - Output:
'c' - Explanation:
'c'is the smallest letter strictly greater than'a'.
Example 2:
- Input:
letters = ['c', 'f', 'j'],target = 'c' - Output:
'f' - Explanation:
'c'is not strictly greater than'c', so we skip to the next.
Example 3:
- Input:
letters = ['c', 'f', 'j'],target = 'j' - Output:
'c' - Explanation: No character in
lettersis greater than'j', so wrap toletters[0].
Example 4:
- Input:
letters = ['x', 'x', 'y', 'y'],target = 'z' - Output:
'x' - Explanation: All letters are
<= 'z', wrap to the first.
Constraints
2 <= letters.length <= 10^4letters[i]is a lowercase English letter.lettersis sorted in non-decreasing order.letterscontains at least two distinct letters.targetis a lowercase English letter.
Follow-up
Which binary-search template handles the wrap-around case most cleanly: equality lo <= hi with explicit not-found handling, or the half-open [lo, hi) upper_bound that returns hi when nothing qualifies?
Solution
Hints
Approach
This is the classic upper_bound pattern (find the first element strictly greater than a target) with a wrap-around when no such element exists. The half-open [lo, hi) binary search is the cleanest template here because the loop ends with lo == hi pointing exactly at the first qualifying index, or at letters.length when nothing qualifies. The wrap is just % length.
Key insight
Rather than searching for target itself and patching up edge cases (target absent, target at the end, duplicates), search directly for the BOUNDARY: "the first index whose letter is strictly greater than target". The half-open template exposes that boundary as lo at termination.
Algorithm
- Set
lo = 0,hi = letters.length. - While
lo < hi:mid = (lo + hi) >> 1.- If
letters[mid] <= target: the boundary is to the right, setlo = mid + 1. - Else: the boundary could be
miditself, sethi = mid.
- After the loop,
lo == hiis the first index withletters[lo] > target, orletters.lengthif no such index exists. - Return
letters[lo % letters.length].
Complexity
Metric Value
------ -------------------
Time O(log n)
Space O(1)A standard binary search on n = letters.length.
Why it works
The loop invariant is: every index i < lo satisfies letters[i] <= target, and every index i >= hi satisfies letters[i] > target. Both halves of the invariant are preserved by each iteration:
letters[mid] <= target -> extend the 'left' half by setting lo = mid + 1
letters[mid] > target -> extend the 'right' half by setting hi = midWhen lo == hi, both halves meet, and lo is exactly the first qualifying index. If every letter is <= target, lo ends at letters.length and the modulo wraps to 0.
Pitfalls
- Off-by-one: using
lo <= hiwithhi = letters.length - 1is the closed-interval template, which works but the wrap edge-case becomes a special branch. The half-open template handles wrap with a single% n. - Comparing with
<instead of<=in the recursion: if duplicates of the target exist (['c', 'c', 'f']withtarget = 'c'),<would not push past them. The predicate isletters[mid] <= target. - Calling the answer
letters[lo]without the modulo: when nothing qualifies,lo == letters.lengthand indexing is out of bounds.
Solution Code