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:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Example 4:

1
2

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

Example 4:

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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.