744. Find Smallest Letter Greater Than Target

Problem Description

Given a characters array letters that is sorted in non-decreasing order and a character target, 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.

Examples:

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

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

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

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

Input: letters = ["c","f","j"], target = "j"
Output: "c"
Explanation: There is no character in letters that is lexicographically greater than 'j' so we return letters[0].

Constraints:

• 2 ≤ letters.length ≤ 10^4
• letters[i] is a lowercase English letter
• letters is sorted in non-decreasing order
• letters contains at least two different characters
• target is a lowercase English letter

Python Solution

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        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)]

Implementation Notes:

• Uses binary search to find the smallest letter greater than target
• Time complexity: O(log n) where n is the length of letters array
• Space complexity: O(1) as it uses constant extra space

Java Solution

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];
    }
}

C++ Solution

class Solution {
public:
    char nextGreatestLetter(vector& 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()];
    }
};

JavaScript Solution

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

C# Solution

public 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];
    }
}

Implementation Notes:

• Uses binary search to find the smallest letter greater than target
• Time complexity: O(log n) where n is the length of letters array
• Space complexity: O(1) as it uses constant extra space