Find Smallest Letter Greater Than Target: Binary Search on Letters

Given a sorted array of lowercase letters and a target letter, find the smallest letter in the array that is strictly greater than the target. If no such letter exists, wrap around and return the first letter in the array.

This is LeetCode 744: Find Smallest Letter Greater Than Target, and it is a clean exercise in adapting binary search to a slightly different goal. Instead of finding an exact match, you are searching for the first element that crosses a threshold.

Why this problem matters

Most people learn binary search as "find the target or return -1." That version of binary search is important, but it only covers one use case. Many real problems ask you to find a boundary: the first element greater than X, the last element less than Y, or the insertion point for a missing value.

LeetCode 744 forces you to think about binary search as a boundary-finding tool rather than an exact-match tool. Specifically:

• No exact match needed: you never check letters[mid] == target and return early. You always want the first letter after the target.
• Wrap-around behavior: if every letter in the array is less than or equal to the target, you return letters[0]. This tests whether your solution handles the "not found" case gracefully.
• Sorted with duplicates: the array can contain repeated letters, so your comparison logic must handle equality correctly.

Once you see this as a left-bound binary search variant, the solution is short and elegant.

The approach: binary search for the first letter past the target

The idea is the same as classic binary search. Maintain two pointers, lo and hi, that define your search range. Compute mid, compare letters[mid] to the target, and shrink the range.

The key difference: when letters[mid] is less than or equal to the target, it cannot be the answer. Move lo past it. When letters[mid] is strictly greater than the target, it could be the answer, but there might be something smaller to the left. Move hi to narrow down further.

When the loop ends, lo points to the smallest letter that is strictly greater than the target. If lo has gone past the end of the array, every letter was less than or equal to the target, so you wrap around to index 0.

The code

def next_greatest_letter(letters, target):
    lo, hi = 0, len(letters) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if letters[mid] <= target:
            lo = mid + 1
        else:
            hi = mid - 1

    return letters[lo % len(letters)]

Let's break this down:

• lo, hi = 0, len(letters) - 1 sets the search range to the full array using inclusive bounds.
• while lo <= hi keeps searching as long as there is at least one candidate left.
• if letters[mid] <= target: lo = mid + 1 eliminates mid and everything to its left. If letters[mid] equals or is less than the target, it is not a valid answer.
• else: hi = mid - 1 means letters[mid] is greater than the target, so it could be the answer. But there might be a smaller valid letter to the left, so we narrow the range.
• letters[lo % len(letters)] handles the wrap-around. If lo equals len(letters), every letter was less than or equal to the target, and the modulo sends us back to index 0.

Visual walkthrough

Let's trace through letters = ["c", "f", "j"] with target = "d".

Two comparisons and we have the answer. The binary search narrows the range quickly, and lo lands on exactly the right index.

Why <= instead of < in the comparison

This is the detail that trips people up. In standard binary search (LeetCode 704), you check for equality: if nums[mid] == target: return mid. Here, there is no early return on equality. If letters[mid] equals the target, it is not a valid answer because you need a letter strictly greater than the target.

By using letters[mid] <= target, you push lo past any letter that matches the target. This ensures lo always converges to the first letter that is strictly greater. If you used letters[mid] < target instead, you would stop at a letter equal to the target, which is wrong.

Complexity analysis

Binary search halves the search range at every step, giving O(log n) comparisons. You use only three variables (lo, hi, mid) regardless of input size.

The building blocks

This problem uses the same core building block as Binary Search (LeetCode 704): search space halving. You maintain an inclusive range [lo, hi], compute a midpoint, and eliminate half the range based on a comparison.

The only twist is the comparison logic. Instead of checking for equality and returning early, you always push toward a boundary. This is the same modification you see in:

• Search Insert Position (LeetCode 35): find where the target would be inserted. Same "no early return" approach, and lo converges to the insertion point.
• First Bad Version (LeetCode 278): find the first version where a boolean predicate flips to true. Same boundary-finding structure.
• Find Minimum in Rotated Sorted Array (LeetCode 153): find the boundary where the rotation happens.

Once the basic binary search template is second nature, all of these variants are small adjustments to the comparison and the return value. The loop skeleton stays the same.

Edge cases to watch for

• Target is smaller than all letters: e.g., letters = ["c", "f", "j"], target = "a". The loop never moves lo, so lo = 0 and you return letters[0] = "c". Correct, since "c" is the smallest letter greater than "a".
• Target is larger than all letters: e.g., letters = ["c", "f", "j"], target = "k". The loop pushes lo all the way to len(letters). The modulo wraps it to 0, returning letters[0] = "c". This matches the problem's wrap-around rule.
• Target equals the largest letter: e.g., letters = ["c", "f", "j"], target = "j". Same wrap-around behavior. lo ends at 3, modulo gives 0, return "c".
• All letters are the same: e.g., letters = ["c", "c", "c"], target = "c". Every comparison hits <=, so lo pushes to 3. Wrap-around returns letters[0] = "c". This is correct because the problem guarantees at least two distinct characters... but even without that guarantee, the wrap-around handles it.
• Target equals a letter in the middle: e.g., letters = ["a", "c", "f"], target = "c". The <= comparison ensures lo moves past the "c", landing on "f".

From understanding to recall

You can probably follow every step of the walkthrough above. But could you write this solution from scratch in an interview next week? The comparison direction (<= vs <), the modulo for wrap-around, the fact that there is no early return on equality: these are the details that slip away.

Spaced repetition locks them in. You write the solution from memory today, again in two days, again in a week. Each rep takes less than a minute, and after a few rounds the boundary-finding binary search template is automatic. You stop worrying about whether it is <= or < because your fingers know.

This problem fits into the search space halving building block, the same one behind standard binary search, Search Insert Position, and First Bad Version. Drilling them as a group helps you see the shared structure and recall each variant independently.

Related posts

• Binary Search (LeetCode 704) - The foundational binary search template that this problem builds on
• Search Insert Position - The closest sibling problem, same boundary-finding binary search with no early return
• First Bad Version - Binary search on a boolean predicate, another variation of the same building block