744. Find Smallest Letter Greater Than Target
Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 0
Acceptance rate: 45.6%
Problem Breakdown
The problem requires finding the smallest element in a sorted list of lowercase letters that is larger than a given target letter. The list wraps around, meaning if no letter is larger than the target, the answer should be the smallest letter in the list.
Inputs:
letters: A list of sorted characters (lowercase letters).target: A single character (lowercase letter).
Outputs:
- A single character from the
letterslist that is the smallest and larger than thetarget.
Implicit Constraints or Tricky Edge Cases:
- The list wraps around, so if no letter is larger than the target, return the smallest letter.
- The list contains at least 2 unique letters.
- The length of the list can be up to 10,000.
Intuition
A brute-force approach would involve iterating through the list and finding the first letter that is larger than the target. This approach has a time complexity of O(n), which is inefficient given the constraints.
The key insight is to leverage the sorted nature of the list and use binary search to find the smallest letter larger than the target in O(log n) time. Binary search works well here because it allows us to efficiently narrow down the possible positions of the target’s successor by comparing the middle element with the target.
Approach
- Initialize Pointers: Start with two pointers,
leftat the beginning of the list andrightat the end. - Binary Search Loop:
- Calculate the middle index
mid. - If the letter at
midis less than or equal to the target, move theleftpointer tomid + 1. - Otherwise, move the
rightpointer tomid.
- Calculate the middle index
- Wrap Around: After the loop, if
leftequals the length of the list, it means all letters are smaller than or equal to the target, so return the first letter in the list. - Return Result: Return the letter at the
leftpointer.
Complexity Analysis
- Time Complexity: O(log n) due to the binary search approach.
- Space Complexity: O(1) as we are using a constant amount of extra space.
Solution
def nextGreatestLetter(letters, target):
left, right = 0, len(letters)
while left < right:
mid = (left + right) // 2
if letters[mid] <= target:
left = mid + 1
else:
right = mid
# If left is equal to the length of the list, wrap around to the first letter
return letters[left % len(letters)]
Edge Cases Handled
- Target Larger Than All Letters: The loop will eventually set
leftto the length of the list, and the modulo operation ensures we return the first letter. - Target Equal To A Letter In The List: The condition
letters[mid] <= targetensures that we move past equal letters to find the next larger one. - List With Two Unique Letters: The binary search handles this by correctly narrowing down the position of the next largest letter.