Code Logo

Find Smallest Letter Greater Than Target

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Given a characters array letters sorted in non-decreasing order and a character target, return the smallest character in the array that is greater than the target. If no such character exists, wrap around and return the first character in the array. This is known as the ceiling of the target in circular array form.

A linear scan would check each character in O(n) time. Binary search improves this to O(log n) by finding the leftmost character greater than the target. If the target is greater than or equal to all characters, the answer wraps to index 0.

The binary search follows the standard pattern: compare the middle character with the target. If the middle character is greater than the target, search the left half for an even smaller character. Otherwise, search the right half. After the loop, lo is the insertion point. If lo equals the array length, wrap to index 0 using the modulo operator.

Edge cases include a single-character array (always return that character), target smaller than all characters (return the first), and target larger than all characters (wrap to first).

The upper bound binary search variant (lo < hi, narrowing to mid rather than mid-1 on success) finds the first element greater than the target. After the loop, lo is the insertion point: the index where target would be inserted to maintain sorted order. If lo equals the array length, the wrap-around rule ensures a non-empty result.

Example Input & Output

Example 1
Input
["c","f","j"], "a"
Output
"c"
Explanation

c is the first letter greater than a.

Example 2
Input
["c","f","j"], "c"
Output
"f"
Explanation

f is the smallest letter > c.

Example 3
Input
["a"], "a"
Output
"a"
Explanation

Single letter, a > a is false, wrap to a.

Example 4
Input
["c","f","j"], "j"
Output
"c"
Explanation

No letter > j, wrap to first letter c.

Example 5
Input
["a","b"], "z"
Output
"a"
Explanation

No letter > z, wrap to a.

Algorithm Flow

Recommendation Algorithm Flow for Find Smallest Letter Greater Than Target

Solution Approach

Find the smallest letter in a sorted array that is greater than a given target. Use binary search with the insertion point pattern. Maintain left and right pointers. At each step, compute mid. If the middle letter is greater than the target, search the left half. Otherwise, search the right half. After the loop exits, left is the insertion point. Use modulo to wrap around: return letters[left % n], which handles the case where all letters are <= target by returning the first letter.

function nextGreatestLetter(letters, target) {
  var left = 0, right = letters.length;
  while (left < right) {
    var mid = Math.floor((left + right) / 2);
    if (letters[mid] > target) right = mid;
    else left = mid + 1;
  }
  return letters[left % letters.length];
}

The modulo operation at the end is key: if left equals the array length (meaning all letters are <= target), left % n gives 0 and returns the first letter, satisfying the wrap-around requirement.

Time complexity is O(log n), space complexity is O(1).

Best Answers

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