Code Implementation

class Solution:
    def nextGreatestLetter(self, letters, target):
        left, right = 0, len(letters) - 1
        while left <= right:
            mid = (left + right) // 2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return letters[left % len(letters)]
      

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0, right = letters.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return letters[left % letters.size()];
    }
};
      

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return letters[left % letters.length];
    }
}
      

var nextGreatestLetter = function(letters, target) {
    let left = 0, right = letters.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (letters[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return letters[left % letters.length];
};
      

Problem Description

You are given a sorted list of lowercase letters called letters and a target letter target. The task is to find the smallest letter in letters that is strictly greater than target. The list of letters is considered circular, meaning if target is greater than or equal to all elements in letters, you should return the first letter in the list.

• The input array letters is sorted in non-decreasing order and contains only lowercase English letters.
• There is always at least one valid answer.
• Each letter may appear multiple times.
• You must not reuse elements; simply return the next greatest letter after target.

Thought Process

At first glance, the problem seems to ask for the next character after target in a sorted list. A simple way to solve this would be to scan the list from the beginning and return the first letter greater than target. However, because the list is sorted, we can do better than a linear scan.

The key insight is that since letters is sorted, we can use binary search to efficiently find the correct letter. Binary search allows us to eliminate half of the search space at each step, making the solution much faster for large lists.

Also, the circular nature of the list means that if target is greater than or equal to all letters in the list, we need to "wrap around" and return the first letter.

Solution Approach

Let's break down the optimized approach step by step:

1. Use Binary Search:
   • Initialize two pointers, left at 0 and right at the last index of letters.
   • While left is less than or equal to right:
     • Find the middle index mid.
     • If letters[mid] is less than or equal to target, move left to mid + 1 (search the right half).
     • Otherwise, move right to mid - 1 (search the left half).
2. Handle Wrap-Around:
   • After the loop, left points to the smallest index where letters[left] is greater than target.
   • If left goes past the end of the array, use modulo to wrap around: letters[left % len(letters)].

This approach works efficiently because binary search reduces the number of comparisons, and the modulo operation handles the circular condition elegantly.

Example Walkthrough

Let's use the example: letters = ['c', 'f', 'j'], target = 'c'.

1. Initialize left = 0, right = 2.
2. First iteration:
   • mid = 1 (letters[1] = 'f'), which is greater than 'c'.
   • Move right to mid - 1 = 0.
3. Second iteration:
   • mid = 0 (letters[0] = 'c'), which is equal to 'c'.
   • Move left to mid + 1 = 1.
4. The loop ends because left = 1 and right = 0.
5. Return letters[1], which is 'f'.

If target = 'j', after the loop left = 3. Since 3 is equal to the length of letters, we wrap around and return letters[0], which is 'c'.

Time and Space Complexity

• Brute-force approach: Scans the array linearly. Time complexity is O(n) where n is the length of letters. Space complexity is O(1) since no extra space is used.
• Optimized binary search approach: Binary search reduces the time complexity to O(log n) because the search space is halved at each step. Space complexity remains O(1).

The optimized approach is much faster for large input sizes due to the logarithmic time complexity.

Summary

To solve the "Find Smallest Letter Greater Than Target" problem, we leverage the sorted property of the input list by applying binary search. This allows us to efficiently find the next greatest letter and handle the circular behavior with a simple modulo operation. The approach is both elegant and efficient, providing a solution that is easy to understand and optimal in performance.