744. Find Smallest Letter Greater Than Target

1. Description

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’.

2. Example

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”

Example 4

Input:
letters = [“c”, “f”, “j”]
target = “g”
Output: “j”

Example 5

Input:
letters = [“c”, “f”, “j”]
target = “j”
Output: “c”

Example 6

Input:
letters = [“c”, “f”, “j”]
target = “k”
Output: “c”

3. 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.

4. Solutions

Binary Search

n = i_letters.size()
Time complexity: O($log_2n$)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    // char nextGreatestLetter(vector<char>& letters, char target)
    char nextGreatestLetter(vector<char> &i_letters, char target)
    {
        int begin = 0, end = i_letters.size();
        while(begin < end)
        {
            int middle = (begin + end) / 2;

            if(i_letters[middle] <= target)
                begin = middle + 1;
            else
                end = middle;
        }

        return i_letters[begin % i_letters.size()];
    }
};