LeetCode 744: Find Smallest Letter Greater Than Target

Problem Restatement

We are given a sorted list of lowercase letters:

letters

and a target character:

target

We must return the smallest character in letters that is strictly greater than target.

The letters wrap around.

This means:

if no character is greater than target,
return the first character in the array

The official problem states that letters is sorted in non-decreasing order and contains at least two different characters. (leetcode.com)

Input and Output

Example function shape:

def nextGreatestLetter(
    letters: list[str],
    target: str,
) -> str:
    ...

Examples

Example 1

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

The smallest character greater than "a" is:

"c"

So the answer is:

"c"

Example 2

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

We need a character strictly greater than "c".

The answer is:

"f"

Example 3

letters = ["x", "x", "y", "y"]
target = "z"

No character is greater than "z".

So we wrap around and return:

"x"

First Thought: Linear Scan

Since the array is sorted, we could scan from left to right.

The first character satisfying:

letter > target

is the answer.

If no such character exists, return the first character.

This works in O(n) time.

But the array is already sorted, so binary search is a better fit.

Key Insight

We want the first element satisfying:

letters[i] > target

This is a standard binary search pattern:

find first valid position

If no valid position exists, wrap around to index 0.

Algorithm

Use binary search on the sorted array.

Maintain:

left = 0
right = len(letters)

While:

left < right

compute:

mid = (left + right) // 2

If:

letters[mid] <= target

then the answer must be to the right:

left = mid + 1

Otherwise:

right = mid

At the end:

• If left == len(letters), wrap around.
• Otherwise return letters[left].

A compact way is:

letters[left % len(letters)]

Correctness

The array is sorted in non-decreasing order.

The binary search maintains the invariant that every index before left contains a character less than or equal to target, and every index at or after right is still a possible answer.

When:

letters[mid] <= target

the character at mid cannot be the answer because the answer must be strictly greater than target. Therefore all indices up to mid can be discarded, and setting:

left = mid + 1

is correct.

When:

letters[mid] > target

the position mid could be the answer, so we keep it in the search range by setting:

right = mid

The loop stops when left == right. At that point, left is the first index whose character is strictly greater than target.

If left equals the array length, then no character is greater than target. By the wraparound rule, the correct answer is the first character in the array.

Therefore the algorithm always returns the required character.

Complexity

Let n = len(letters).

Implementation

class Solution:
    def nextGreatestLetter(
        self,
        letters: list[str],
        target: str,
    ) -> str:
        left = 0
        right = len(letters)

        while left < right:
            mid = (left + right) // 2

            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid

        return letters[left % len(letters)]

Code Explanation

We search over the full array:

left = 0
right = len(letters)

Notice that right is exclusive.

Inside the loop:

mid = (left + right) // 2

If the middle character is too small or equal to the target:

if letters[mid] <= target:

then the answer must be further right:

left = mid + 1

Otherwise, the middle position may already be the first valid answer:

right = mid

At the end, left points to the first character greater than target.

If no such character exists, left becomes:

len(letters)

The modulo operation wraps it back to index 0:

letters[left % len(letters)]

Testing

def run_tests():
    s = Solution()

    assert s.nextGreatestLetter(
        ["c", "f", "j"],
        "a",
    ) == "c"

    assert s.nextGreatestLetter(
        ["c", "f", "j"],
        "c",
    ) == "f"

    assert s.nextGreatestLetter(
        ["x", "x", "y", "y"],
        "z",
    ) == "x"

    assert s.nextGreatestLetter(
        ["a", "b"],
        "z",
    ) == "a"

    assert s.nextGreatestLetter(
        ["a", "b"],
        "a",
    ) == "b"

    assert s.nextGreatestLetter(
        ["e", "e", "e", "k", "q", "q"],
        "e",
    ) == "k"

    print("all tests passed")

run_tests()