EasyArrayBinary Search

Find Smallest Letter Greater Than Target

1 approach, code in all languages

You are handed a list of lowercase letters already sorted in non-decreasing order, plus a single target letter. Return the smallest letter in the list that comes strictly after the target in the alphabet.

The list is treated as circular: if no letter beats the target, the search wraps around and the answer becomes the first letter of the list.

Example 1

Input: letters = ["c","f","j"], target = "a"

Output: "c"

The smallest letter after 'a' present in the list is 'c'.

Example 2

Input: letters = ["c","f","j"], target = "j"

Output: "c"

Nothing beats 'j', so the search wraps and returns the first letter 'c'.

Constraints

2 ≤ letters.length ≤ 10^4
letters[i] is a lowercase English letter
letters is sorted in non-decreasing order
target is a lowercase English letter

Binary Search (Upper Bound with Wrap)

Find the first letter strictly greater than the target, then wrap the index around the array length.

Loading animation…

Intuition

This is an upper-bound query: we want the leftmost position holding a letter larger than the target. Treating any letter that is less than or equal to the target as 'too small' pushes the window rightward, and the collapse lands on the first strictly-greater letter. If that lands past the end, taking the index modulo the length wraps us back to the first letter.

Algorithm walkthrough

1Set lo to 0 and hi to the number of letters, a half-open window.
2While lo is below hi, compute the midpoint.
3If the middle letter is less than or equal to the target, move lo past it.
4Otherwise pull hi down to mid because a valid answer sits at or before it.
5Return the letter at index lo modulo the length so an out-of-range result wraps to the start.

Implementation

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 % len(letters)]

Time

O(log n)

Space

O(1)

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI