DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Find Smallest Letter Greater Than Target

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.

SOLUTION:

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        beg = 0
        end = n - 1
        while beg <= end:
            mid = (beg + end) // 2
            if mid < n - 1 and letters[mid] <= target and letters[mid + 1] > target:
                return letters[mid + 1]
            elif beg == end:
                if mid < n - 1:
                    return letters[mid]
                else:
                    return letters[0]
            elif letters[mid] > target:
                end = mid
            else:
                beg = mid + 1
Enter fullscreen mode Exit fullscreen mode

Top comments (0)