Find Smallest Letter Greater Than Target

Table of Contents

Problem Description:

Given a sorted list of lowercase letters letters and a target letter target, you need to find the smallest letter in the list that is greater than the target. If the target is greater than or equal to the last letter in the list, the smallest letter should loop around to the first letter.

Sample Input and Expected Output:

Input:

letters = ['c', 'f', 'j']
target = 'a'

Output:

Smallest letter greater than 'a': 'c'

Input:

letters = ['c', 'f', 'j']
target = 'd'

Output:

Smallest letter greater than 'd': 'f'

Input:

letters = ['c', 'f', 'j']
target = 'k'

Output:

Smallest letter greater than 'k': 'c'

Solution in C++:

We can solve this problem using a binary search algorithm. Since the list of letters is sorted, we can perform a binary search to find the smallest letter greater than the target. If the target is greater than or equal to the last letter in the list, we return the first letter.

#include <iostream>
#include <vector>

char nextGreatestLetter(std::vector<char>& letters, char target) {
    int left = 0;
    int right = letters.size() - 1;

    // If the target is greater than or equal to the last letter, return the first letter.
    if (target >= letters[right]) {
        return letters[0];
    }

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (letters[mid] <= target) {
            left = mid + 1; // Search the right half
        } else {
            right = mid - 1; // Search the left half
        }
    }

    return letters[left]; // Smallest letter greater than the target
}

int main() {
    std::vector<char> letters = {'c', 'f', 'j'};
    char target1 = 'a';
    char target2 = 'd';
    char target3 = 'k';

    char result1 = nextGreatestLetter(letters, target1);
    char result2 = nextGreatestLetter(letters, target2);
    char result3 = nextGreatestLetter(letters, target3);

    std::cout << "Smallest letter greater than '" << target1 << "': '" << result1 << "'" << std::endl;
    std::cout << "Smallest letter greater than '" << target2 << "': '" << result2 << "'" << std::endl;
    std::cout << "Smallest letter greater than '" << target3 << "': '" << result3 << "'" << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the Binary Search algorithm is O(log n), where n is the size of the letters array. This is because at each step, we reduce the search space by half.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array.

← Binary Search Problem ← Peak Index in a Mountain Array