Next Letter After the Target
Problem
You are given a list of lowercase letters sorted in non-decreasing order, containing at least two different letters, and a target letter. Return the smallest letter in the list that is strictly greater than the target. If no letter is greater, wrap around and return the first letter of the list.
Examples
Input: letters = ["c", "f", "j"], target = "a"
Output: "c"Input: letters = ["c", "f", "f", "j"], target = "f"
Output: "j"
Why: strictly greater means both copies of f are skippedInput: letters = ["c", "f", "j"], target = "j"
Output: "c"
Why: edge case, nothing is greater than j, so the answer wraps to the frontHints
0 / 3
A linear scan works, but the list is sorted. Which classic search answers the question of where the first letter greater than the target sits?
This is an upper bound search: find the first index whose letter is strictly greater than the target. Every index before it holds a letter that is less than or equal to the target.
Binary search with lo = 0 and hi = len(letters). If the middle letter is less than or equal to the target, move lo past it, otherwise move hi to it. When the search ends at lo, return the letter at lo modulo the length, which covers the wrap.
Solution
The first letter strictly greater than the target is an upper bound, one of the boundary searches where the loop keeps a half-open range and never returns early. Letters less than or equal to the target push lo past the middle, larger letters pull hi down to it, so when the two meet, lo is the first index holding a greater letter. If every letter is less than or equal to the target, lo ends at the length of the list, and taking it modulo the length turns that into the wrap to the front. Time is O(log n) and space is O(1).
def next_letter(letters, target):
lo, hi = 0, len(letters)
while lo < hi: # find the first letter greater than target
mid = (lo + hi) // 2
if letters[mid] <= target:
lo = mid + 1
else:
hi = mid
return letters[lo % len(letters)] # past the end wraps to the front
print(next_letter(["c", "f", "j"], "a")) # -> c
print(next_letter(["c", "f", "f", "j"], "f")) # -> j
print(next_letter(["c", "f", "j"], "j")) # -> cStuck on the idea rather than the code? Binary Search Variants covers it.