Problem description:

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:

1
2
Input: letters = ["c","f","j"], target = "a"
Output: "c"

Example 2:

1
2
Input: letters = ["c","f","j"], target = "c"
Output: "f"

Example 3:

1
2
Input: letters = ["c","f","j"], target = "d"
Output: "f"

Example 4:

1
2
Input: letters = ["c","f","j"], target = "g"
Output: "j"

Example 5:

1
2
Input: letters = ["c","f","j"], target = "j"
Output: "c"

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:

1
2
3
4
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        pos = bisect_right(letters, target)
        return letters[0] if pos == len(letters) else letters[pos]

time complexity: $O(logn)$
space complexity: $O()$
reference:
related problem: