problemeasyalgorithmsleetcode-744leetcode 744leetcode744

Find smallest letter greater than target in a sorted array of letters

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Given an array of lowercase letters sorted in ascending order, and a target letter, find the smallest letter in the array that is greater than the target.

Note that, Letters also wrap around. For example, if target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples

Example 1:

Input: letters = ["d", "h", "l"], target = "a"
Output: "d"

Example 2:

Input: letters = ["d", "h", "l"], target = "d"
Output: "h"

Example 3:

Input: letters = ["d", "h", "l"], target = "f"
Output: "h"

Example 4:

Input: letters = ["d", "h", "l"], target = "j"
Output: "l"

Example 4:

Input: letters = ["d", "h", "l"], target = "n"
Output: "d"

Solution

This problem is similar to - [Find ceiling of target element in a sorted array](find-ceiling-of-target-element-in-a-sorted-array)

Method 1 - Binary Search

These solutions leverage binary search to efficiently find the smallest letter greater than the target, taking advantage of the sorted nature of the input array.

Code

Java
public class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int low = 0, high = letters.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return letters[low % letters.length];
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[] letters = {'c', 'f', 'j'};
        char target = 'a';
        System.out.println(
            sol.nextGreatestLetter(letters, target)); // Output: c
    }
}
Python
def nextGreatestLetter(letters, target):
    low, high = 0, len(letters) - 1

    while low <= high:
        mid = (low + high) // 2
        if letters[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1

    return letters[low % len(letters)]

Complexity

  • ⏰ Time complexity: O(log n), due to binary search.
  • 🧺 Space complexity: O(1), as no extra space is used apart from a few variables.

Comments