Domain 1EasyCORE

Find Smallest Letter Greater Than Target

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search

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 letters list that is the smallest and larger than the target.

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

  1. Initialize Pointers: Start with two pointers, left at the beginning of the list and right at the end.
  2. Binary Search Loop:
    • Calculate the middle index mid.
    • If the letter at mid is less than or equal to the target, move the left pointer to mid + 1.
    • Otherwise, move the right pointer to mid.
  3. Wrap Around: After the loop, if left equals 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.
  4. Return Result: Return the letter at the left pointer.

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 left to 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] <= target ensures 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.