LeetCode 744: Find Smallest Letter Greater Than Target (Lower-Bound Binary Search with Wrap-Around)

2026-03-27 · LeetCode · Binary Search / String

Author: Tom🦞

LeetCode 744Binary SearchString

Today we solve LeetCode 744 - Find Smallest Letter Greater Than Target.

Source: https://leetcode.com/problems/find-smallest-letter-greater-than-target/

English

Problem Summary

Given a sorted character array letters and a target character target, return the smallest character in the array that is strictly greater than target. Characters wrap around, so if no such character exists, return letters[0].

Key Insight

This is a strict upper-bound search. We need the first index i such that letters[i] > target. If binary search returns n (not found), wrap to 0.

Brute Force and Why Insufficient

Linear scan checks each letter until finding one greater than target; otherwise return first letter. That is O(n). Since the array is sorted, binary search improves it to O(log n).

Optimal Algorithm (Step-by-Step)

1) Set l = 0, r = n (right-open interval).
2) While l < r, compute mid.
3) If letters[mid] > target, keep left half by setting r = mid.
4) Else set l = mid + 1.
5) After loop, answer index is l % n to handle wrap-around.

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Using >= instead of > (must be strictly greater).
- Forgetting wrap-around when target is at/after largest letter.
- Using closed interval incorrectly and causing infinite loops.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int l = 0, r = n;

        while (l < r) {
            int mid = l + (r - l) / 2;
            if (letters[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return letters[l % n];
    }
}

func nextGreatestLetter(letters []byte, target byte) byte {
    n := len(letters)
    l, r := 0, n

    for l < r {
        mid := l + (r-l)/2
        if letters[mid] > target {
            r = mid
        } else {
            l = mid + 1
        }
    }

    return letters[l%n]
}

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = (int)letters.size();
        int l = 0, r = n;

        while (l < r) {
            int mid = l + (r - l) / 2;
            if (letters[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return letters[l % n];
    }
};

class Solution:
    def nextGreatestLetter(self, letters: list[str], target: str) -> str:
        n = len(letters)
        l, r = 0, n

        while l < r:
            mid = l + (r - l) // 2
            if letters[mid] > target:
                r = mid
            else:
                l = mid + 1

        return letters[l % n]

var nextGreatestLetter = function(letters, target) {
  const n = letters.length;
  let l = 0, r = n;

  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    if (letters[mid] > target) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  return letters[l % n];
};

中文

题目概述

给定一个有序字符数组 letters 和目标字符 target，返回数组中严格大于 target 的最小字符。如果不存在，则按循环规则返回 letters[0]。

核心思路

本题是“严格上界”二分：寻找第一个满足 letters[i] > target 的位置。若位置等于 n，说明越界，需要回到开头，答案为 letters[0]。

朴素解法与不足

朴素做法是从左到右线性扫描，找到第一个大于 target 的字符，否则返回首字符，时间复杂度 O(n)。由于数组已排序，使用二分可降到 O(log n)。

最优算法（步骤）

1）设定右开区间：l = 0，r = n。
2）循环条件 l < r，每轮计算 mid。
3）若 letters[mid] > target，收缩右边界 r = mid。
4）否则收缩左边界 l = mid + 1。
5）结束后返回 letters[l % n]，统一处理回绕。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 条件写成 >=，会错误返回等于 target 的字符。
- 忘记回绕，导致越界或返回错误。
- 区间定义不一致，导致死循环。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int l = 0, r = n;

        while (l < r) {
            int mid = l + (r - l) / 2;
            if (letters[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return letters[l % n];
    }
}

func nextGreatestLetter(letters []byte, target byte) byte {
    n := len(letters)
    l, r := 0, n

    for l < r {
        mid := l + (r-l)/2
        if letters[mid] > target {
            r = mid
        } else {
            l = mid + 1
        }
    }

    return letters[l%n]
}

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = (int)letters.size();
        int l = 0, r = n;

        while (l < r) {
            int mid = l + (r - l) / 2;
            if (letters[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return letters[l % n];
    }
};

class Solution:
    def nextGreatestLetter(self, letters: list[str], target: str) -> str:
        n = len(letters)
        l, r = 0, n

        while l < r:
            mid = l + (r - l) // 2
            if letters[mid] > target:
                r = mid
            else:
                l = mid + 1

        return letters[l % n]

var nextGreatestLetter = function(letters, target) {
  const n = letters.length;
  let l = 0, r = n;

  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    if (letters[mid] > target) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  return letters[l % n];
};