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.

#744

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

寻找比目标字母大的最小字母

给你一个字符数组 letters ，该数组按非递减顺序排序，以及一个字符 target 。 letters 里至少有两个不同的字符。返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。示例 1：输入: letters =…

数组二分查找

题目描述

给你一个字符数组 letters，该数组按 非递减顺序 排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

示例 1：

输入: letters = ['c', 'f', 'j'], target = 'a'
输出: 'c'
解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:

输入: letters = ['c','f','j'], target = 'c'
输出: 'f'
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:

输入: letters = ['x','x','y','y'], target = 'z'
输出: 'x'
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

提示：

2 <= letters.length <= 10⁴
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母

lightbulb

解题思路

方法一：二分查找

由于 $\textit{letters}$ 是按照非递减顺序排序的，所以我们可以使用二分查找来找到大于 $\textit{target}$ 的最小字符。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = n$ 。对于每一次二分查找，我们计算中间位置 $mid = (l + r) / 2$ ，如果 $letters[mid] > \textit{target}$ ，则说明我们需要在左半部分继续查找，即 $r = mid$ ；否则我们需要在右半部分继续查找，即 $l = mid + 1$ 。

最后我们返回 $letters[l \bmod n]$ 即可。

时间复杂度 $O(\log n)$ ，其中 $n$ 是 $\textit{letters}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

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)]

speed

复杂度分析

指标	值
时间	complexity is O(log n) due to binary search, and space complexity is O(1) as no extra structures are used beyond indices.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#731 我的日程安排表 II #729 我的日程安排表 I #719 找出第 K 小的数对距离