[Solved] Find Smallest Letter Greater Than Target Binary Search LeetCode

Find Smallest Letter Greater Than Target Binary Search: 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'.

Find Smallest Letter Greater Than Target Binary Search

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"

Constraints:

• 2 <= letters.length <= 104
• 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.

Solution

C++

class Solution {
public:
    char nextGreatestLetter(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;
            }
        }
        return left == letters.size() ? letters[0] : letters[left];
    }
};

C++ shortcode

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

Java

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        
        int left = 0;
        int right = letters.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left == letters.length ? letters[0] : letters[left];
    }
}

Java shortcode

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for (int i : letters) {
            if (i > target) {
                return (char) i;
            }
        }
        return letters[0];
    }
}

Python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        left = 0
        right = len(letters) - 1
        while (left <= right):
            mid = int(left + (right - left) / 2)
            if (letters[mid] <= target):
                left = mid + 1
            else:
                right = mid - 1
        return letters[left] if left < len(letters) else letters[0]
        

Python shortcode

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        for i in letters:
            if i > target:
                return i
        return letters[0]
        

Happy Learning – If you require any further information, feel free to contact me.