Find Smallest Letter Greater Than Target
Understanding the Problem
We have a sorted array of lowercase letters and a target character. The task is to find the smallest letter in the array that comes strictly after the target alphabetically. Equal does not count, the letter must be strictly greater. If the target is greater than or equal to every letter in the array, we wrap around and return the first letter.
The wrap-around makes the alphabet behave like a circle. If no letter sits past the target, the answer loops back to index 0.
The array is sorted, which is what makes binary search applicable. We start with a linear scan to establish the baseline, then improve on it.
Key Constraints:
lettersis sorted in non-decreasing order → This is the constraint that drives the approach. A sorted array supports binary search.letters[i]is a lowercase English letter → Only 26 distinct values are possible, but the algorithm does not depend on that small alphabet.targetis a lowercase English letter → Input is always valid, so no validation is needed.
Approach 1: Linear Scan
Intuition
Walk through the array from left to right and return the first character that is strictly greater than the target. Because the array is sorted in non-decreasing order, the first such character encountered is also the smallest one that qualifies.
If the loop reaches the end without finding any greater character, the target is greater than or equal to every letter. The problem then asks us to wrap around and return the first letter.
Algorithm
- Iterate through each character in
lettersfrom left to right. - If the current character is strictly greater than
target, return it immediately. - If the loop finishes without finding any character greater than
target, returnletters[0].
Example Walkthrough
Code
- Time Complexity: O(n). In the worst case, we scan through all n elements before finding the answer or determining we need to wrap around.
- Space Complexity: O(1). We only use a loop variable. No extra data structures needed.
The linear scan ignores the sorted structure of the array. Binary search uses that structure to find the answer in O(log n) instead of O(n).
Approach 2: Binary Search
Intuition
We are not searching for an exact match. We want the smallest element that is strictly greater than the target, which is the "find the leftmost position satisfying a condition" variant of binary search.
At each step we look at the middle element. If letters[mid] > target, then mid is a valid answer, but a smaller valid one might exist to the left, so we record mid as a candidate and search the left half. If letters[mid] <= target, then mid and everything to its left are too small or equal, so we search the right half.
The wrap-around is handled by initializing result = 0 before the loop. If no letter is greater than the target, result never changes and we return the first element, with no special case at the end.
The search maintains an invariant: result always holds the index of the smallest greater-than-target letter found so far, and any smaller valid index still lies within [left, right]. Each iteration either records a candidate and shrinks right (when letters[mid] > target) or advances left past values that are too small or equal. Because the array is sorted, discarding a half never skips a smaller valid index: everything at or before a <= target element is also <= target, and everything after a candidate is larger than it. When the range empties, result holds the leftmost qualifying index, or 0 if none qualified.
Algorithm
- Initialize
left = 0,right = letters.length - 1, andresult = 0(default to index 0 for wrap-around). - While
left <= right: - Compute
mid = left + (right - left) / 2. - If
letters[mid] > target, saveresult = midand search left: setright = mid - 1. - Otherwise (
letters[mid] <= target), search right: setleft = mid + 1. - Return
letters[result].
Example Walkthrough
Code
- Time Complexity: O(log n). Each iteration halves the search space. For n = 10,000, that's about 14 comparisons instead of scanning all 10,000 elements.
- Space Complexity: O(1). We only use a few integer variables (
left,right,mid,result). No extra data structures.