Watch 10 video solutions for Find Smallest Letter Greater Than Target, a easy level problem involving Array, Binary Search. This walkthrough by Eric Programming has 8,315 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.
Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.
Example 1:
Input: letters = ["c","f","j"], target = "a" Output: "c" Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
Example 2:
Input: letters = ["c","f","j"], target = "c" Output: "f" Explanation: 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" Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
Constraints:
2 <= letters.length <= 104letters[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.Problem Overview: You get a sorted array of lowercase characters and a target character. The task is to return the smallest letter in the array that is strictly greater than the target. The array is circular, meaning if the target is greater than or equal to all characters, the answer wraps around to the first element.
Approach 1: Brute Force Linear Scan (O(n) time, O(1) space)
The most direct solution is to iterate through the array from left to right and return the first character that is greater than the target. Because the array is already sorted, the first match you encounter is guaranteed to be the smallest valid letter. If the loop finishes without finding a larger character, return the first element in the array to handle the circular condition. This approach uses a simple for loop over the array and constant extra memory.
This method works well for small inputs and is easy to reason about during an interview. However, it scans every element in the worst case. With larger arrays, the linear time cost becomes unnecessary since the data is already sorted.
Approach 2: Binary Search (O(log n) time, O(1) space)
The optimal solution uses binary search to exploit the sorted order of the letters. Instead of checking every character, maintain two pointers left and right. At each step compute mid. If letters[mid] is less than or equal to the target, move left to mid + 1 because that character cannot be the answer. Otherwise move right to mid since it could still be the smallest valid letter.
When the search finishes, left points to the first element greater than the target. Because the array is circular, the final index is left % n. This handles the wrap‑around case where all characters are smaller than or equal to the target.
This approach performs only logarithmic comparisons and keeps memory usage constant. Problems like this are classic examples of applying lower bound style binary search on a sorted structure.
Recommended for interviews: Start by explaining the linear scan since it demonstrates understanding of the problem and the circular condition. Then optimize using binary search. Interviewers usually expect the O(log n) binary search solution because the array is sorted and the task essentially asks for the first element greater than a target.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Linear Scan | O(n) | O(1) | Simple implementation or very small arrays where performance is not critical |
| Binary Search | O(log n) | O(1) | Preferred when the array is sorted and efficient lookup of the next greater element is required |