Binary Search

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

Rajeev SinghAlgorithms1 mins read

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

Smallest Letter Greater than Target

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 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"

Binary search to find the smallest letter greater than target

This problem is a variation of the problem Find the ceiling of an element in a sorted array. The implementation approach is also similar. We apply binary search to find the smallest letter greater than the target. Here is the full implementation:

import java.util.Scanner;

class NextLetter {
    private static int findNextLetter(char[] letters, char target) {
        int n = letters.length;
        int start = 0, end = n - 1;

        char nextLetter = letters[start];

        while (start <= end) {
            int mid = (start + end) / 2;

            if (target < letters[mid]) {
                /*
                 * letters[mid] is the smallest letter found so far that is greater than target.
                 * So update nextLetter to this value and keep checking in the left side of the
                 * array to find an even smaller letter that is greater than target
                 */
                nextLetter = letters[mid];
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return nextLetter;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        char[] letters = new char[n];
        for (int i = 0; i < n; i++) {
            letters[i] = keyboard.next().charAt(0);
        }
        char target = keyboard.next().charAt(0);
        keyboard.close();

        System.out.printf("NextLetter(%c) = %c%n", target, findNextLetter(letters, target));
    }
}
# Output
$ javac NextLetter.java
$ java NextLetter
3
d h l
a
NextLetter(a) = d


$ java NextLetter
3
d h l
d
NextLetter(d) = h


$ java NextLetter
3
d h l
f
NextLetter(f) = h


$ java NextLetter
3
d h l
j
NextLetter(j) = l


$ java NextLetter
3
d h l
l
NextLetter(l) = d


$ java NextLetter
3
d h l
n
NextLetter(n) = d