EasyArrayBinary Search

Find Smallest Letter Greater Than Target

1 approach, code in every language

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 see the solution

You get 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

After the pattern

Now solve one you haven't seen.

Next Divider Label Round the Drawer is our own problem on the technique behind Find Smallest Letter Greater Than Target: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free