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”
- code
class Solution(object):
def nextGreatestLetter(self, letters, target):
index = bisect.bisect(letters, target)
return letters[index % len(letters)]
At the end, if our insertion position says to insert target into the last position letters.length, we return letters[0] instead. This is what the modulo operation does.
- code
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
if target >= letters[-1]: return letters[0]
l, r = 0, len(letters) - 1
while l < r:
mid = l + (r-l) // 2
if letters[mid] <= target:
l = mid + 1
else:
r = mid
return letters[l]