[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]
Abhishek Sharma
Abhishek Sharma

Started my Data Science journey in my 2nd year of college and since then continuously into it because of the magical powers of ML and continuously doing projects in almost every domain of AI like ML, DL, CV, NLP.

Articles: 517

Leave a Reply

Your email address will not be published. Required fields are marked *