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

My Accepted Solution

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

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