DSA problem
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 no such character exists, return letters[0] — the comparison wraps around.
The shape of the problem is the classic upper_bound binary search: find the smallest index i such that letters[i] > target. The single twist is the wraparound: when every element is <= target, the answer is the first element instead of "not found." Folding that into the binary search is a tiny modulo trick.
Set lo = 0 and hi = n and iterate while lo < hi. If letters[mid] <= target, the answer lies strictly to the right (lo = mid + 1). Otherwise mid itself is a candidate (hi = mid). When the loop ends, lo is either a valid index in [0, n - 1] (a strictly larger character exists) or it equals n (no such character, meaning wrap). The clean way to express both branches is return letters[lo % n].
The result is O(log n) time and O(1) space. This problem is also a good drill on the difference between <= (used here, for upper bound) and < (which would give a lower bound, the wrong answer when letters contains the target value).
Examples
letters = ["c","f","j"], target = "a""c"letters = ["c","f","j"], target = "c""f"letters = ["x","x","y","y"], target = "z""x"Constraints
- 2 <= letters.length <= 10^4
- 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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.