744. Find Smallest Letter Greater Than Target Easy

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

Example 1:
Input: letters = ["c", "f", "j"], target = "a"
Output: "c"
Explanation: The smallest character lexicographically greater than 'a' in letters is 'c'.

Example 2:
Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character lexicographically greater than 'c' in letters is 'f'.

Example 3:
Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

Approach

Input: An ascending sorted character array letters, a target value.

Output: Return the first character in the array that is strictly greater than target. If it doesn't exist, return the first character.

This problem belongs to the Basic Search category, suitable for using binary search in a sorted array to quickly locate the target value.

We shrink the search interval continuously through binary search. The specific steps are as follows:

Initialize the left and right boundaries: left = 0, right = len(letters) - 1

Loop the following logic until left > right:

Calculate the middle position mid = (left + right) // 2

• If letters[mid] <= target, it means the character greater than the target is in the right half, update left = mid + 1.
• If letters[mid] > target, it means there might still be characters greater than target in the [left, mid] interval, update right = mid - 1.

Finally, when the loop ends, the position where left is at must be the first element greater than the target.

However, it's also possible that it exceeds the array (the last element could also be less than or equal to target), so we still need left % len(letters) or directly take the first value.

Implementation

python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left, right = 0, len(letters) - 1  # Initialize left and right pointers

        # Binary search to find the first character greater than target
        while left <= right:
            mid = (left + right) // 2  # Calculate middle position
            if letters[mid] <= target:
                # If the current character is less than or equal to the target, the answer is on the right
                left = mid + 1
            else:
                # If the current character is greater than the target, the answer might be on the left (including current mid)
                right = mid - 1

        # At this point, left is the index of the first character greater than target
        # If left exceeds the array bounds, it means target is >= all characters
        # Since it wraps around circularly as per the problem, return letters[0]
        return letters[left % len(letters)]

javascript

/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function(letters, target) {
    let left = 0;
    let right = letters.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

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

    return letters[left % letters.length];
};

Complexity Analysis

• Time Complexity: O(log n)
• Space Complexity: O(1)

Links

744. Find Smallest Letter Greater Than Target (English)

744. 寻找比目标字母大的最小字母 (Chinese)