Find Smallest Letter Greater Than Target — Easy Problem & Solution

Problem statement

letters is sorted in non-decreasing order and contains at least two different characters.

Return the smallest character in letters that is strictly greater than target. If no such character exists, wrap around and return the first character of letters.

Example 1

Input: letters = ["c","d","e","k"], target = "e"
Output: k
Explanation: The next letter after e in the list is k.

Example 2

Input: letters = ["c","f","j"], target = "j"
Output: c
Explanation: Nothing is greater than j, so it wraps to the front.

Example 3

Input: letters = ["x","x","y","y"], target = "z"
Output: x

Constraints

• 2 <= letters.length <= 10000
• letters[i] is a lowercase English letter.
• letters is sorted in non-decreasing order.
• letters contains at least two different characters.
• target is a lowercase English letter.

How to solve Find Smallest Letter Greater Than Target

This is an upper bound: find the leftmost index whose letter is strictly greater than target. Binary search locates it, and running past the end means every letter is at most target, so the wrap takes over.

Approach

1. Search over [0, n] for the first index with letters[mid] > target.
2. Move hi to mid when the letter is greater, otherwise lo past mid.
3. Return letters[lo], or letters[0] when lo == n.

Why it works

Because the array is sorted, the predicate letters[i] > target is false for a prefix and true for the rest, so the boundary is unique and binary search converges on it. The guarantee that two different characters exist means the wrap never returns something equal to target in a way that breaks the 'strictly greater' promise — the wrapped answer is deliberately smaller.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Using >= finds an equal letter, which the problem excludes.
• Forgetting the wrap-around returns out of bounds for a target at or above every letter.
• A linear scan works at this size but misses the point of the exercise.

Reference solution

Python

from typing import List

def nextGreatestLetter(letters: List[str], target: str) -> str:
    lo, hi = 0, len(letters)
    while lo < hi:
        mid = (lo + hi) // 2
        if letters[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    return letters[0] if lo == len(letters) else letters[lo]

JavaScript

var nextGreatestLetter = function(letters, target) {
    var lo = 0, hi = letters.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (letters[mid] > target) hi = mid; else lo = mid + 1;
    }
    return lo === letters.length ? letters[0] : letters[lo];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy