AlgoMaster Logo

Find Smallest Letter Greater Than Target

Last Updated: March 29, 2026

easy

Understanding the Problem

We have a sorted array of lowercase letters and a target character. Our job is to find the next letter in the array that comes strictly after the target alphabetically. Not equal to, strictly greater than. If the target is greater than or equal to every letter in the array, we wrap around and return the very first letter.

Think of it like a circular alphabet. You're standing at some letter, and you want to find the next available letter from the sorted collection. If you've gone past all of them, you loop back to the beginning.

The sorted order is the big clue here. Whenever you see "sorted" and "find a value," binary search should immediately come to mind. But let's start with the straightforward approach first.

Key Constraints:

  • 2 <= letters.length <= 10^4 → With n up to 10,000, even an O(n^2) approach would work fine. But a linear scan O(n) or binary search O(log n) are both very comfortable here.
  • letters is sorted in non-decreasing order → This is the critical constraint. Sorted input is an open invitation for binary search.
  • letters[i] is a lowercase English letter → Only 26 possible characters. The range is tiny, but that doesn't change the algorithmic approach.
  • target is a lowercase English letter → Always valid input, no special validation needed.

Approach 1: Linear Scan

Intuition

The simplest approach: just walk through the sorted array from left to right. The first character you find that's strictly greater than the target is your answer. Since the array is already sorted in non-decreasing order, the first one you hit will naturally be the smallest such character.

If you make it through the entire array without finding anything greater, that means the target is greater than or equal to every letter. In that case, the problem says to wrap around and return the first letter.

Algorithm

  1. Iterate through each character in letters from left to right.
  2. If the current character is strictly greater than target, return it immediately.
  3. If the loop finishes without finding any character greater than target, return letters[0].

Example Walkthrough

1Start scan: target = 'c', check letters[0]
0
c
i
1
f
2
j
1/3

Code

The linear scan works but completely ignores the sorted structure of the array. Since the input is sorted, we can use binary search to find the answer in O(log n) instead of O(n).

Approach 2: Binary Search

Intuition

The array is sorted. That's a direct signal for binary search. But there's a twist: we're not searching for an exact match. We want the smallest element that is strictly greater than the target. This is a classic "find the leftmost position satisfying a condition" variant of binary search.

At any point during the search, we look at the middle element. If letters[mid] > target, then mid could be our answer, but there might be a smaller valid one to the left. So we save it as a candidate and search the left half. If letters[mid] <= target, then mid and everything to its left are too small or equal, so we search the right half.

The clever part is the wrap-around handling. By initializing result = 0 before the loop, if we never find any letter greater than the target, result stays at 0 and we naturally return the first element. No special-case code needed.

Algorithm

  1. Initialize left = 0, right = letters.length - 1, and result = 0 (default to index 0 for wrap-around).
  2. While left <= right:

a. Compute mid = left + (right - left) / 2.

b. If letters[mid] > target, save result = mid and search left: set right = mid - 1.

c. Otherwise (letters[mid] <= target), search right: set left = mid + 1.

  1. Return letters[result].

Example Walkthrough

1Initialize: left=0, right=2, result=0, target='c'
0
result
c
left
1
f
2
j
right
1/4

Code