Find Smallest Letter Greater Than Target — LeetCode 744 Python Solution

The problem

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Example

Input

letters = ["c","f","j"], target = "a"

Output

"c"

Explanation

The smallest character that is lexicographically greater than 'a' in letters is 'c'.

Python solution

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        i = bisect_right(letters, ord(target), key=lambda c: ord(c))
        return letters[i % len(letters)]

Complexity

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 744. Find Smallest Letter Greater Than Target is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems