Find Smallest Letter Greater Than Target

---

Find Smallest Letter Greater Than Target: 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 that is lexicographically
greater than 'a' in letters is 'c'.

---

Example 2:

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is 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].

---

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.

---

Try this Problem on your own or check similar problems:

1. Binary Search
2. Count Elements With Strictly Smaller and Greater Elements

Solution:

Java

public char nextGreatestLetter(char[] letters, char target) {
    int low = 0, n = letters.length, high = n;

    while(low < high){
        int mid = low + (high - low) / 2;
        if(letters[mid] > target){
            high = mid;
        }else{
            low = mid + 1;
        }
    }

    return letters[low % n];
}

JavaScript

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

  while (low < high) {
    let mid = low + Math.floor((high - low) / 2);
    if (letters[mid] > target) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

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

Python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        low = 0
        high = len(letters)

        while low < high:
            mid = low + (high - low) // 2
            if letters[mid] > target:
                high = mid
            else:
                low = mid + 1

        return letters[low % len(letters)]

C++

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int low = 0, high = letters.size();

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return letters[low % letters.size()];
    }
};

---

Time/Space Complexity:

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

---

Explanation:

Modification on Binary Search with few tricks:

• letters[low % n] at the end of loop low might have converged to the end of array, so we take the modulo to return the first element as per problem statement.
• We keep the low < high loop invariant, so at any iteration we have either found mid which is larger than target and then the high is pointing to the same element as mid (our current best solution) or it's pointing to the end of array (out of boundary) no mid elements are found that are larger than target.
• Why do we set high = mid and not high = mid + 1? From the previous point, high might be pointing to valid element (element larger than target) so we cannot remove it from the search, we can however eliminate all the other elements coming after mid since mid is the smallest element larger than target in the second half.
• At the end of loop low has converged to high and it's either pointing to smallest elements larger than target or out of array.