Find Smallest Letter Greater Than Target Problem


Description

LeetCode Problem 744.

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

  • For example, if target == ‘z’ and letters == [‘a’, ‘b’], the answer is ‘a’.

Example 1:

1
2
Input: letters = ["c","f","j"], target = "a"
Output: "c"

Example 2:

1
2
Input: letters = ["c","f","j"], target = "c"
Output: "f"

Example 3:

1
2
Input: letters = ["c","f","j"], target = "d"
Output: "f"

Example 4:

1
2
Input: letters = ["c","f","j"], target = "g"
Output: "j"

Example 5:

1
2
Input: letters = ["c","f","j"], target = "j"
Output: "c"

Constraints:

  • 2 <= letters.length <= 10^4
  • letters[i] is a lowercase English letter.
  • letters is sorted in non-decreasing order.
  • letters contains at least two different characters.
  • target is a lowercase English letter.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int low = 0;
        int high = letters.size()-1;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        return letters[low] > target ? letters[low] : letters[0];
    }
};




Related Posts

Super Egg Drop Problem

LeetCode 887. You are given k identical eggs and you...

Peak Index In A Mountain Array Problem

LeetCode 852. Let’s call an array arr a mountainif the...

Numbers At Most N Given Digit Set Problem

LeetCode 902. Given an array of digits which is sorted...

Nth Magical Number Problem

LeetCode 878. A positive integer is magical if it is...

Koko Eating Bananas Problem

LeetCode 875. Koko loves to eat bananas. There are n...