How to Find Smallest Letter Greater Than Target?

Given a list of sorted array containing only lowercase letters, and a target letter, your task is to find the smallest letter in the list that is greater than the target. Also, you would need to wrap the result – if the target is ‘z’ and in the sorted array [‘a’, ‘b’], the answer is ‘a’.

Linear Scan

As the letters are already sorted, we ca do a O(N) linear scan until the smallest element found that is larger than the target.

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        for (const auto &n: letters) {
            if (n > target) {
                return n;
            }
        }
        return letters[0];
    }
};

Binary Search

The sorted array makes it possible to do a binary search algorithm. The complexity is O(nlogn) where n is the size of the array.

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int lo = 0, hi = letters.size();
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (letters[mi] <= target) {
                lo = mi + 1;
            } else {
                hi = mi;
            }
        }
        return letters[lo % letters.size()];                
    }
};

Record Last Position

We can use a set or a static array of size 26 to record if a lowercase letter has appeared in the list. Then we can start from the target and move the index one by one towards to the right (close-wise, wrap it to the front) until we found another recorded letter.

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        bool data[26] = { false };
        for (const auto &n: letters) {
            data[n - 97] = true;
        }
        target -= 97;        
        do {
            target = (target + 1) % 26;    
        } while (!data[target]);
        return static_cast<char>(97 + target);
    }
};

–EOF (The Ultimate Computing & Technology Blog) —