Find smallest letter greater than target

Array Binary Search

58.9% acceptance

Feb 21, 2026

5130

2227

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters. Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

/*
 * You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.
 * Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.
 * Example 1:
 * Input: letters = ["c","f","j"], target = "a"
 * Output: "c"
 * Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
 * Example 2:
 * Input: letters = ["c","f","j"], target = "c"
 * Output: "f"
 * Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.
 * Example 3:
 * Input: letters = ["x","x","y","y"], target = "z"
 * Output: "x"
 * Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
 * Constraints:
 * 2 <= letters.length <= 104
 * 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.
 */
impl Solution {
  pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
    let (mut lo, mut hi) = (0usize, letters.len());
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if letters[mid] <= target { lo = mid + 1; } else { hi = mid; }
    }
    letters[lo % letters.len()]
  }
}