Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

In a sorted array, all letters strictly greater than the target form a suffix. We need its first element, so binary search can discard half the remaining candidates at each step. If that suffix is empty, the required wraparound answer is the first letter.

Approach

Initialize the answer to letters[0] for the wraparound case.
Inspect the middle of the current inclusive search interval. If its letter is greater than the target, record it and search to its left for a smaller qualifying letter.
Otherwise search to its right. Equality belongs in this branch because the answer must be strictly greater.
Return the recorded answer when the interval is exhausted. Duplicate letters require no special treatment.

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        # for c in letters:
            # if c > target: return c
        # return letters[0]

        l = 0
        h = len(letters) - 1
        res = letters[0]

        while l <= h:
            mid = l + (h - l) // 2
            if letters[mid] > target:
                res = letters[mid]
                h = mid - 1
            else:
                l = mid + 1

        return res

Complexity analysis

For n letters, binary search takes O(log n) time and O(1) auxiliary space.