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'
andletters == ['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
Top comments (0)