We need the smallest letter strictly greater than target in a sorted circular list. Use binary search to find the first index i where letters[i] > target. If no such index exists, wrap around and return letters[0].
""" 0744.1 - Find Smallest Letter Greater Than Target - Solution 1 - Binary Search """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
"""Return the smallest character in letters that is strictly greater than target."""
lo, hi = 0, len(letters) # hi is exclusive
while lo < hi:
mid = (lo + hi) // 2
if letters[mid] <= target:
lo = mid + 1
else:
hi = mid
# If lo == len(letters), all letters are <= target, so we wrap around.
return letters[lo % len(letters)]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
s = Solution()
print(s.nextGreatestLetter(["c", "f", "j"], "a")) # c
print(s.nextGreatestLetter(["c", "f", "j"], "c")) # f
print(s.nextGreatestLetter(["c", "f", "j"], "d")) # f
print(s.nextGreatestLetter(["c", "f", "j"], "j")) # c
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()