[Solved] 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.

Question

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:

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.

Python Solution

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