744. Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

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

Examples:

Input:

letters = ["c", "f", "j"]

target = "a"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "c"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "d"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "g"

Output: "j"

Input:

letters = ["c", "f", "j"]

target = "j"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "k"

Output: "c"

Note:

letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Solution:

1. From Note we know the array is not empty so there must be a solution.

2. We check the last char in the array. If target is greater or equal than the last char, the answer is the first char in the array.

3. Use binary search to find the fist element that is greater than target in this array.

Time complexity is O(logn).

Code:

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