Find Smallest Letter Greater Than Target - Java Solution

1. Introduction

In this blog post, we'll explore a problem that involves searching for the smallest letter greater than a given target in a sorted array of lowercase letters. This problem is a variant of binary search and demonstrates how binary search can be adapted for circularly sorted arrays.

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. The letters wrap around, meaning that if the target is greater than all the letters in the array, the search wraps around to the beginning of the array.

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 5:

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

Output: "d"

2. Solution Steps

1. Use binary search to find the smallest letter greater than the target.

2. If the target is greater than or equal to the last element in the array, return the first element.

3. If the target is found or the search space is exhausted, return the element just after the last mid-point.

4. Adjust the binary search to wrap around the array if necessary.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        char[] letters1 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'a': " + nextGreatestLetter(letters1, 'a'));

        char[] letters2 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'd': " + nextGreatestLetter(letters2, 'd'));

        char[] letters3 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'f': " + nextGreatestLetter(letters3, 'f'));

        char[] letters4 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'j': " + nextGreatestLetter(letters4, 'j'));

        char[] letters5 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'n': " + nextGreatestLetter(letters5, 'n'));
    }

    // Method to find the smallest letter greater than the target
    public static char nextGreatestLetter(char[] letters, char target) {
        int start = 0, end = letters.length - 1;

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

            if (letters[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return letters[start % letters.length];
    }
}

Output:

Smallest letter greater than 'a': d
Smallest letter greater than 'd': h
Smallest letter greater than 'f': h
Smallest letter greater than 'j': l
Smallest letter greater than 'n': d

Explanation:

The nextGreatestLetter method performs a binary search to find the smallest letter greater than the target. If the target letter is found or if we reach the end of the array, the method returns the next letter in the sorted array, wrapping around if necessary. 

For example, for the input array ['d', 'h', 'l'] and target 'f', the method returns 'h', which is the smallest letter greater than 'f'. Similarly, for target 'n', it wraps around and returns 'd'.