744. Find Smallest Letter Greater Than Target - Solution

The problem

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 <= 10⁴
letters[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.

Approach overview

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 1: Brute Force Linear Scan

The simplest way to solve the problem is to iterate over the array and find the first character that is greater than the target character. If such a character is not found by the end of the array, the function should return the first character of the array. This approach simply checks each character in order from left to right, comparing it with the target.

Python

def nextGreatestLetter(letters, target):
    for letter in letters:
        if letter > target:
            return letter
    return letters[0]

Java

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for (char letter : letters) {
            if (letter > target) {
                return letter;
            }
        }
        return letters[0];
    }
}

C++

#include <vector>
using namespace std;

char nextGreatestLetter(vector<char>& letters, char target) {
    for (char letter : letters) {
        if (letter > target) {
            return letter;
        }
    }
    return letters[0];
}

JavaScript

function nextGreatestLetter(letters, target) {
    for (let letter of letters) {
        if (letter > target) {
            return letter;
        }
    }
    return letters[0];
}

#include <stdio.h>

char nextGreatestLetter(char* letters, int lettersSize, char target) {
    for (int i = 0; i < lettersSize; i++) {
        if (letters[i] > target) {
            return letters[i];
        }
    }
    return letters[0];
}

public class Solution {
    public char NextGreatestLetter(char[] letters, char target) {
        foreach (char letter in letters) {
            if (letter > target) {
                return letter;
            }
        }
        return letters[0];
    }
}

This function straightforwardly checks each letter in the letters array to see if it exceeds target. If it finds such a letter, it returns it; otherwise, it defaults to the first letter.

Complexity

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

Try this approach in the editor

Approach 2: Binary Search

Utilizing the sorted nature of the array, we can employ a binary search technique to pinpoint the smallest character that exceeds the target. By continually narrowing the search range, we can efficiently determine the desired character. If the binary search concludes without finding a suitable character, the array's initial character is returned.

Python

def nextGreatestLetter(letters, target):
    low, high = 0, len(letters) - 1
    while low <= high:
        mid = (low + high) // 2
        if letters[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1
    return letters[low % len(letters)]

Java

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int low = 0, high = letters.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return letters[low % letters.length];
    }
}

C++

#include <vector>
using namespace std;

char nextGreatestLetter(vector<char>& letters, char target) {
    int low = 0, high = letters.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (letters[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return letters[low % letters.size()];
}

JavaScript

function nextGreatestLetter(letters, target) {
    let low = 0, high = letters.length - 1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (letters[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return letters[low % letters.length];
}

#include <stdio.h>

char nextGreatestLetter(char* letters, int lettersSize, char target) {
    int low = 0, high = lettersSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (letters[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return letters[low % lettersSize];
}

public class Solution {
    public char NextGreatestLetter(char[] letters, char target) {
        int low = 0, high = letters.Length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return letters[low % letters.Length];
    }
}

Binary search tackles the array by targeting a middle point, adjusting range based on target comparison, and provides a direct return through the modulus of low size, ensuring appropriate array wrapping if necessary.

Complexity

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

Try this approach in the editor

Approach 3: Binary Search

Since letters is sorted in non-decreasing order, we can use binary search to find the smallest character that is larger than target.

We define the left boundary of the binary search as l = 0, and the right boundary as r = n. For each binary search, we calculate the middle position mid = (l + r) / 2. If letters[mid] > target, it means we need to continue searching in the left half, so we set r = mid. Otherwise, we need to continue searching in the right half, so we set l = mid + 1.

Finally, we return letters[l \mod n].

The time complexity is O(log n), where n is the length of letters. The space complexity is O(1).

TypeScript

function nextGreatestLetter(letters: string[], target: string): string {
    const idx = _.sortedIndex(letters, target + '\0');
    return letters[idx % letters.length];
}

func nextGreatestLetter(letters []byte, target byte) byte {
	i := sort.Search(len(letters), func(i int) bool { return letters[i] > target })
	return letters[i%len(letters)]
}

Rust

impl Solution {
    pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char {
        let mut l = 0;
        let mut r = letters.len();
        while l < r {
            let mid = l + (r - l) / 2;
            if letters[mid] > target {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        letters[l % letters.len()]
    }
}

PHP

class Solution {
    /**
     * @param String[] $letters
     * @param String $target
     * @return String
     */
    function nextGreatestLetter($letters, $target) {
        $l = 0;
        $r = count($letters);
        while ($l < $r) {
            $mid = $l + $r >> 1;
            if ($letters[$mid] > $target) {
                $r = $mid;
            } else {
                $l = $mid + 1;
            }
        }
        return $letters[$l % count($letters)];
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Linear Scan	Time Complexity: O(n). Space Complexity: O(1).
Binary Search	Time Complexity: O(log n). Space Complexity: O(1).
Binary Search	–

Complexity analysis

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

Frequently asked questions

Is Find Smallest Letter Greater Than Target easy or hard?

LeetCode classifies this problem as Easy. The main challenge is recognizing that the array is sorted and that the answer may wrap around to the first element, which makes binary search the optimal approach.

Find Smallest Letter Greater Than Target Python/Java solution

Most implementations use a binary search loop with two pointers. The logic is identical across Python, Java, C++, and other languages: adjust the search range based on comparisons and return letters[left % n] after the search completes.

How to solve Find Smallest Letter Greater Than Target in O(log n)?

Use binary search on the sorted letters array. Move the left pointer when the mid character is less than or equal to the target, and move the right pointer otherwise. After the loop, return letters[left % n] to support the wrap‑around case.

What is the best approach for Find Smallest Letter Greater Than Target?

Binary search is the best approach because the letters array is already sorted. By searching for the first element strictly greater than the target, you can find the answer in O(log n) time and O(1) space. The final index is taken modulo the array length to handle the circular condition.

Is Find Smallest Letter Greater Than Target asked at Google/Amazon/Meta?

Binary search pattern problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants that ask for the first element greater than a target or the next alphabetical character are common in technical screens.

What data structure is used in Find Smallest Letter Greater Than Target?

The problem uses a sorted array of characters. The key algorithmic technique applied on top of the array is binary search to efficiently locate the smallest element greater than the target.

What is the time complexity of Find Smallest Letter Greater Than Target?

The optimal binary search solution runs in O(log n) time because the search space halves every iteration. A simple linear scan solution exists with O(n) time complexity. Both approaches use O(1) additional space.

Find Smallest Letter Greater Than Target solution and explanation

The problem

Approach overview

Approach 1: Brute Force Linear Scan

Approach 2: Binary Search

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Smallest Letter Greater Than Target solution and explanation

The problem

Approach overview

Approach 1: Brute Force Linear Scan

Approach 2: Binary Search

Approach 3: Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems