#744

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find Smallest Letter Greater Than Target

Locate the smallest character in a sorted array that is strictly greater than a given target using efficient binary search techniques.

array binary search

Problem Statement

You are given a sorted array of lowercase characters and a target character. Your task is to find and return the smallest character in the array that is lexicographically greater than the target.

If no such character exists, return the first character in the array. For example, given letters = ["c","f","j"] and target = "a", the correct output is "c" since it is the smallest letter greater than "a".

Examples

Example 1

Input: letters = ["c","f","j"], target = "a"

Output: "c"

The smallest character that is lexicographically greater than 'a' in letters is 'c'.

Example 2

Input: letters = ["c","f","j"], target = "c"

Output: "f"

The smallest character that is lexicographically greater than 'c' in letters is 'f'.

Example 3

Input: letters = ["x","x","y","y"], target = "z"

Output: "x"

There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

Constraints

2 <= letters.length <= 104
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

Solution Approach

Binary Search Over Array

Perform a standard binary search to locate the first letter greater than the target. Compare the mid element with the target and move left or right accordingly. This ensures O(log n) time complexity.

Handle Wrap-Around Case

If the target is greater than or equal to all letters in the array, return the first letter. This handles cases where the lexicographical search exceeds the array's maximum value.

Avoid Duplicate Pitfalls

Skip repeated letters during comparison to ensure the smallest valid letter is returned. Duplicates can mislead simple linear searches, but binary search handles them efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) due to binary search, and space complexity is O(1) as no extra structures are used beyond indices.

What Interviewers Usually Probe

Candidate should immediately suggest binary search rather than linear scan.
Look for handling of wrap-around cases where target >= all letters.
Ensure candidate correctly identifies first letter greater than target, not just any larger letter.

Common Pitfalls or Variants

Common pitfalls

Forgetting to wrap around to letters[0] when target exceeds all array elements.
Using linear search instead of binary search, missing O(log n) efficiency.
Incorrectly handling duplicates, returning repeated elements instead of the first valid greater letter.

Follow-up variants

Return index instead of letter for the smallest letter greater than target.
Find the largest letter smaller than target using a mirrored binary search approach.
Handle arrays with cyclic lexicographical order or custom character sets.

FAQ

What is the best approach for 'Find Smallest Letter Greater Than Target'?

Binary search over the sorted array is optimal; it quickly identifies the first letter greater than target and handles wrap-around cases.

How do I handle duplicates in the letters array?

Binary search naturally skips duplicates when moving left or right, but ensure you always select the first valid letter greater than target.

What if the target is larger than all letters in the array?

Return the first letter in the array to handle the wrap-around condition correctly.

Can I solve this problem with linear search?

Yes, but it will take O(n) time and is inefficient; binary search guarantees O(log n) performance for large arrays.

Why is this problem considered a 'Binary search over the valid answer space' pattern?

Because the solution requires searching for a single optimal value in a sorted set, testing each potential letter efficiently with binary search rather than brute force.

terminal

Solution

Solution 1: Binary Search

Since `letters` is sorted in non-decreasing order, we can use binary search to find the smallest character that is larger than `target`.

1

2

3

4

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        i = bisect_right(letters, ord(target), key=lambda c: ord(c))
        return letters[i % len(letters)]

Continue Practicing

#731 my calendar ii #729 my calendar i #719 find k th smallest pair distance