744. Find Smallest Letter Greater Than Target

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You have an array of characters letters that is sorted in non-decreasing order (alphabetically), and you're given a character target. The array contains at least two different characters.

Your task is to find the smallest character in letters that comes after target in alphabetical order (lexicographically greater). If no such character exists in the array, you should wrap around and return the first character in letters.

For example:

If letters = ['c', 'f', 'j'] and target = 'a', the answer is 'c' because it's the smallest character greater than 'a'.
If letters = ['c', 'f', 'j'] and target = 'd', the answer is 'f' because it's the smallest character greater than 'd'.
If letters = ['c', 'f', 'j'] and target = 'j', the answer is 'c' because no character in the array is greater than 'j', so we wrap around to the beginning.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Binary search finds the first letter strictly greater than the target in the sorted array with wrap-around.

Open in Flowchart

Intuition

Since the array is already sorted, we can use this property to find our answer efficiently. Think of it like looking up a word in a dictionary - you don't need to check every single word; you can jump to approximately where you expect the word to be and then narrow down your search.

The key insight is that we need to find the first character that is strictly greater than our target. In a sorted array, all characters greater than target will be grouped together on the right side, and all characters less than or equal to target will be on the left side. This naturally forms a boundary that we can search for.

Binary search is perfect for this because it repeatedly divides the search space in half. We're essentially asking: "Where would target be inserted if we wanted to maintain the sorted order?" The answer to this question gives us the index of the first character greater than target.

The search looks for the first index whose character is strictly greater than target. This is the same position that bisect_right would return: if target is 'd' and we have ['a', 'c', 'f', 'j'], that index is 2 (pointing to 'f').

If all characters in the array are less than or equal to target, no such index exists. The solution records this as first_true_index = -1 and returns the first character, which is the wrap-around the problem asks for.

Pattern Learn more about Binary Search patterns.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The solution uses binary search with the standard boundary-finding template to find the smallest character that is larger than target.

Defining the Feasible Function

For this problem, we define feasible(mid) as: "Is letters[mid] greater than target?"

This creates a boolean array pattern across indices:

letters:  ['c', 'f', 'j']
target:   'd'
feasible: [false, true, true]

We want to find the first true index - the smallest index where letters[mid] > target.

Binary Search Template

We use the standard template with first_true_index tracking:

Initialize left = 0, right = n - 1 (last valid index), and first_true_index = -1
While left <= right:
- Calculate mid = (left + right) // 2
- If letters[mid] > target (feasible):
  - Record first_true_index = mid as a potential answer
  - Search left half: right = mid - 1 (look for smaller valid index)
- Else:
  - Search right half: left = mid + 1
After the loop, first_true_index contains the index of the smallest character greater than target, or -1 if none exists

Handling the Wrap-Around

The problem requires wrapping to the first character if no greater character exists. We handle this by checking first_true_index:

If first_true_index != -1: return letters[first_true_index]
If first_true_index == -1: return letters[0] (wrap around)

This explicit handling is cleaner than using modulo arithmetic because it makes the wrap-around logic visible and intentional.

Example Walkthrough

Let's walk through an example with letters = ['c', 'f', 'j'] and target = 'd'.

Step 1: Initialize

Array: ['c', 'f', 'j']
left = 0, right = 2 (last valid index)
first_true_index = -1

Step 2: First iteration (left=0, right=2)

Calculate mid = (0 + 2) // 2 = 1
Check letters[1] which is 'f'
Is 'f' > 'd'? Yes! (feasible)
Record first_true_index = 1
Search left: right = mid - 1 = 0

Step 3: Second iteration (left=0, right=0)

Calculate mid = (0 + 0) // 2 = 0
Check letters[0] which is 'c'
Is 'c' > 'd'? No! (not feasible)
Search right: left = mid + 1 = 1

Step 4: Loop ends (left=1 > right=0)

first_true_index = 1 (found a valid answer)
Return letters[1] which is 'f'

The answer is 'f', which is correct as it's the smallest character greater than 'd'.

Wrap-around example: letters = ['c', 'f', 'j'], target = 'j'

Step 1: Initialize

left = 0, right = 2, first_true_index = -1

Step 2: First iteration (left=0, right=2)

mid = 1, letters[1] = 'f'
Is 'f' > 'j'? No!
Search right: left = 2

Step 3: Second iteration (left=2, right=2)

mid = 2, letters[2] = 'j'
Is 'j' > 'j'? No!
Search right: left = 3

Step 4: Loop ends (left=3 > right=2)

first_true_index = -1 (no character greater than target found)
Wrap around: return letters[0] which is 'c'

This demonstrates how tracking first_true_index explicitly handles the wrap-around case when no character is greater than the target.

Solution Implementation

1class Solution:
2    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
3        """
4        Find the smallest character in letters that is lexicographically greater than target.
5        If no such character exists, return the first character in letters (wrap around).
6
7        Args:
8            letters: A sorted list of characters in non-decreasing order
9            target: The target character to find the next greatest letter for
10
11        Returns:
12            The smallest character greater than target, or the first character if none exists
13        """
14        n = len(letters)
15        left, right = 0, n - 1
16        first_true_index = -1
17
18        # Binary search to find the first index where letters[mid] > target
19        while left <= right:
20            mid = (left + right) // 2
21
22            # Feasible condition: is this character greater than target?
23            if letters[mid] > target:
24                first_true_index = mid  # Record potential answer
25                right = mid - 1  # Search left for smaller valid index
26            else:
27                left = mid + 1  # Search right
28
29        # Handle wrap-around: if no character is greater, return first character
30        if first_true_index == -1:
31            return letters[0]
32        return letters[first_true_index]
33

1class Solution {
2    public char nextGreatestLetter(char[] letters, char target) {
3        int n = letters.length;
4        int left = 0;
5        int right = n - 1;
6        int firstTrueIndex = -1;
7
8        // Binary search to find the first index where letters[mid] > target
9        while (left <= right) {
10            int mid = left + (right - left) / 2;
11
12            // Feasible condition: is this character greater than target?
13            if (letters[mid] > target) {
14                firstTrueIndex = mid;  // Record potential answer
15                right = mid - 1;  // Search left for smaller valid index
16            } else {
17                left = mid + 1;  // Search right
18            }
19        }
20
21        // Handle wrap-around: if no character is greater, return first character
22        if (firstTrueIndex == -1) {
23            return letters[0];
24        }
25        return letters[firstTrueIndex];
26    }
27}
28

1class Solution {
2public:
3    char nextGreatestLetter(vector<char>& letters, char target) {
4        int n = letters.size();
5        int left = 0;
6        int right = n - 1;
7        int firstTrueIndex = -1;
8
9        // Binary search to find the first index where letters[mid] > target
10        while (left <= right) {
11            int mid = left + (right - left) / 2;
12
13            // Feasible condition: is this character greater than target?
14            if (letters[mid] > target) {
15                firstTrueIndex = mid;  // Record potential answer
16                right = mid - 1;  // Search left for smaller valid index
17            } else {
18                left = mid + 1;  // Search right
19            }
20        }
21
22        // Handle wrap-around: if no character is greater, return first character
23        if (firstTrueIndex == -1) {
24            return letters[0];
25        }
26        return letters[firstTrueIndex];
27    }
28};
29

1/**
2 * Finds the smallest character in the sorted array that is lexicographically greater than the target.
3 * If no such character exists, returns the first character in the array (wraps around).
4 *
5 * @param letters - A sorted array of lowercase letters in non-decreasing order
6 * @param target - The target character to find the next greatest letter for
7 * @returns The smallest character greater than target, or the first character if none exists
8 */
9function nextGreatestLetter(letters: string[], target: string): string {
10  const n = letters.length;
11  let left = 0;
12  let right = n - 1;
13  let firstTrueIndex = -1;
14
15  // Binary search to find the first index where letters[mid] > target
16  while (left <= right) {
17    const mid = Math.floor((left + right) / 2);
18
19    // Feasible condition: is this character greater than target?
20    if (letters[mid] > target) {
21      firstTrueIndex = mid; // Record potential answer
22      right = mid - 1; // Search left for smaller valid index
23    } else {
24      left = mid + 1; // Search right
25    }
26  }
27
28  // Handle wrap-around: if no character is greater, return first character
29  if (firstTrueIndex === -1) {
30    return letters[0];
31  }
32  return letters[firstTrueIndex];
33}
34

Time and Space Complexity

The time complexity is O(log n), where n is the length of the letters array. Binary search divides the search space in half with each iteration, resulting in logarithmic time.

The space complexity is O(1). The algorithm only uses a constant number of variables (left, right, mid, first_true_index) regardless of input size.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Mixing Up Two Binary Search Variants

The half-open variant below, with right = len(letters), while left < right, and right = mid, is also correct: it ends with left at the first index greater than target (or at len(letters)), and % len(letters) handles the wrap-around. Problems arise when parts of the two variants are mixed, for example while left <= right with right = mid, which loops forever once left == right and the condition is true.

Half-open variant (also correct):

left, right = 0, len(letters)
while left < right:
    mid = (left + right) // 2
    if letters[mid] > target:
        right = mid  # Different from template
    else:
        left = mid + 1
return letters[left % len(letters)]

Closed-interval template (used in the solution):

left, right = 0, len(letters) - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if letters[mid] > target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return letters[0] if first_true_index == -1 else letters[first_true_index]

2. Forgetting the Wrap-Around Case

Without handling the case where no character is greater than target, the code returns an incorrect result. In Python, letters[-1] does not raise an error; it silently returns the last character.

Incorrect approach:

# Assumes first_true_index will always be found
return letters[first_true_index]  # Returns the last character when first_true_index == -1

Solution: Check for -1 and wrap to first character:

if first_true_index == -1:
    return letters[0]
return letters[first_true_index]

3. Wrong Feasible Condition

Using >= instead of > will return the target itself if it exists, instead of the next greater character.

Incorrect:

if letters[mid] >= target:  # Wrong: includes target itself
    first_true_index = mid
    right = mid - 1

Correct:

if letters[mid] > target:  # Correct: strictly greater
    first_true_index = mid
    right = mid - 1

4. Not Understanding "Smallest Greater"

Some might return any character greater than target. The problem asks for the smallest such character.

Example: If letters = ['a', 'c', 'f', 'j'] and target = 'b', returning 'f' or 'j' is wrong. The correct answer is 'c' as it's the smallest character greater than 'b'.

The binary search template naturally handles this by searching left (right = mid - 1) when we find a valid answer, ensuring we find the leftmost (smallest) valid index.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointers

Two pointers moving in opposite direction

Sliding window

Prefix sum

I don't know