Find Smallest Letter Greater Than Target

Problem

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

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"

Constraints:

2 <= letters.length <= 10⁴
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.

Solution

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

    // if wrap is required (ie. target is >= everything in letters)
    if (target >= letters[hi]) {
        return letters[lo];
    }

    // no wrap => standard binary search (ie. find insertion index)
    while (lo <= hi) {
        const mid = Math.floor((lo + hi) / 2);
        const char = letters[mid];
        if (char <= target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return letters[lo]
};

We will implement a binary search solution. We first check if wrapping is required, if it is required, the next greatest letter must be the first letter in letters. If no wrapping is required, we can use standard binary search to find the insertion position of target in letters, and return the letter currently occupying that position (ie. that letter is the smallest character in the array that is larger than target).

Problem​

Solution​

Problem

Solution