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'.

Example

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

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.