Code Logo

Find Smallest Letter Greater Than Target

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Find Smallest Letter Greater Than Target

Solution Approach

Binary search for insertion point. After loop, return letters[lo % n] for wrap-around.

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

Time O(log n), Space 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];
    }
}