algoadvance

Leetcode 744. Find Smallest Letter Greater Than Target

Problem Statement

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

Letters also wrap around. For example, if the target is z and letters contains letters from a to c, the answer is a.

You can assume:

• letters has at least two characters.
• letters is sorted in non-decreasing order.
• letters contains only lowercase English letters from a to z.

Clarifying Questions

1. Q: Is the input list guaranteed to be non-empty and sorted?
   • A: Yes, the input list letters is guaranteed to be non-decreasingly sorted and contains at least two characters.
2. Q: Are there any constraints on the length of the list?
   • A: No specific constraints are mentioned, but typical constraints are the size fitting within typical memory and execution time limits.
3. Q: Can letters contain duplicate characters?
   • A: Yes, letters can contain duplicate characters.
4. Q: What should be returned if there is no character in the list greater than the target?
   • A: Since the list wraps around, we will return the smallest character in this case.

Strategy

To solve this problem efficiently, we can use a Binary Search algorithm due to the sorted nature of the letters list. The steps will be:

1. Use a binary search to find the smallest character greater than target.
2. If no such character is found within the range, return the first character of the list (due to the wrap-around property).

Code

Here’s the C++ implementation:

#include <vector>
#include <iostream>

char nextGreatestLetter(std::vector<char>& letters, char target) {
    int left = 0;
    int right = letters.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (letters[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // Element at 'left' is the smallest element greater than target,
    // or the element is wrap around the list
    return letters[left % letters.size()];
}

int main() {
    std::vector<char> letters = {'c', 'f', 'j'};
    char target = 'd';
    std::cout << "The smallest letter greater than " << target << " is " << nextGreatestLetter(letters, target) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this algorithm is O(log n) due to the binary search mechanism.

• Space Complexity: The space complexity is O(1) since we are using only a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?