🤖 Solving LeetCode Problem 744: Find the Smallest Letter Greater Than Target

Problem Statement

Given a sorted array of characters letters containing only lowercase English letters, and a target letter target, find the smallest element in the array that is greater than the target. Note that the letters wrap around, meaning that if the target is greater than or equal to the largest letter in the array, the search should wrap around and return the smallest letter in the array.

Example 1:

Input: letters = ['c', 'f', 'j'], target = 'a'
Output: 'c'

Example 2:

Input: letters = ['c', 'f', 'j'], target = 'c'
Output: 'f'

Example 3:

Input: letters = ['c', 'f', 'j'], target = 'd'
Output: 'f'

---

Observations

1. The array is sorted, which makes binary search an ideal candidate for efficiently finding the result.
2. If the target is smaller than or equal to the smallest letter in the array, we should return that smallest letter.
3. If the target is larger than the largest letter in the array, we should return the first letter, because the array wraps around.

With these observations in mind, let's design our solution using binary search.

---

Approach

Binary search works by repeatedly dividing the search space in half. Here's how we'll apply it to this problem:

1. Initialize Variables: Start with two pointers, start at the beginning (0) and end at the end (letters.length - 1) of the array.
2. Binary Search:
   • Calculate the middle index.
   • If letters[mid] is greater than target, move the end pointer to mid - 1.
   • If letters[mid] is less than or equal to target, move the start pointer to mid + 1.
3. Wrap Around: Once the binary search completes, the smallest letter greater than the target will be at the start index. If start exceeds the bounds of the array, use modulo operation to wrap around to the first letter in the array.
4. Return Result: Return the letter at the start % letters.length index.

---

Java Code Implementation

public class Solution {
    public static void main(String[] args) {

        char[] letters = {'c', 'f', 'j'};
        char target = 'a';

        char ans = nextGreatestLetter(letters, target);
        System.out.println(ans);
    }

    static char nextGreatestLetter(char[] letters, char target){

        int start = 0;
        int end = letters.length - 1;

        while (start <= end){

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

            if (target >= letters[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        // Since letters wrap around, we return letters[start % letters.length]
        return letters[start % letters.length];
    }
}

---

Explanation of the Code

1. Initialization:

   • We start with start = 0 and end = letters.length - 1, which represent the beginning and end of the array.

2. Binary Search Logic:

   • The condition if (target >= letters[mid]) moves the start pointer to mid + 1 when the target is greater than or equal to the middle element.
   • Otherwise, we move the end pointer to mid - 1.

3. Handling Wrap Around:

   • After the loop, the smallest letter greater than the target will be at the start index. If start is beyond the array's last index, we use start % letters.length to wrap around and access the first element.

---

Why Binary Search?

Binary search is ideal for this problem because:

• Efficiency: The time complexity of binary search is O(log n), which is much faster than a linear scan (O(n)) for large arrays.
• Sorted Array: The array is sorted, which is the prerequisite for applying binary search.

---

Edge Cases

1. Target Larger than Any Letter: If the target is greater than or equal to the last letter in the array, the search wraps around and returns the first letter.
2. Target Smaller than Smallest Letter: The binary search will find the smallest letter greater than the target.

---