Find Smallest Letter Greater Than Target

Problem

Given a sorted array of characters (wrapping around alphabetically) and a target, return the smallest character that compares strictly greater than target. Wraps around to the start.

Constraints

• 2 ≤ letters.length ≤ 10⁴

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def nextGreatestLetter(self, letters, target):
        import bisect
        i = bisect.bisect_right(letters, target)
        return letters[i % len(letters)]

Java

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int lo = 0, hi = letters.length;
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (letters[m] <= target) lo = m + 1;
            else                       hi = m;
        }
        return letters[lo % letters.length];
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.