Find Smallest Letter Greater Than Target

Easy
809.

Find Smallest Letter Greater Than Target

Find Smallest Letter Greater Than Target is an easy coding problem on arrays and binary search, asked in Amazon, Microsoft and TCS interviews.

letters is sorted in non-decreasing order and contains at least two different characters.

Return the smallest character in letters that is strictly greater than target. If no such character exists, wrap around and return the first character of letters.

Example 1

Input
letters = ["c","d","e","k"], target = "e"
Output
k
Explanation
The next letter after e in the list is k.

Example 2

Input
letters = ["c","f","j"], target = "j"
Output
c
Explanation
Nothing is greater than j, so it wraps to the front.

Example 3

Input
letters = ["x","x","y","y"], target = "z"
Output
x

Constraints

  • 2 <= letters.length <= 10000
  • 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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} letters
 * @param {string} target
 * @return {string}
 */
var nextGreatestLetter = function(letters, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Smallest Letter Greater Than Target — Solution

Find Smallest Letter Greater Than Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Smallest Letter Greater Than Target is an easy coding problem on arrays and binary search, asked in Amazon, Microsoft and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Microsoft, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

letters is sorted in non-decreasing order and contains at least two different characters.

Return the smallest character in letters that is strictly greater than target. If no such character exists, wrap around and return the first character of letters.

Example 1

Input: letters = ["c","d","e","k"], target = "e"
Output: k
Explanation: The next letter after e in the list is k.

Example 2

Input: letters = ["c","f","j"], target = "j"
Output: c
Explanation: Nothing is greater than j, so it wraps to the front.

Example 3

Input: letters = ["x","x","y","y"], target = "z"
Output: x

Constraints

  • 2 <= letters.length <= 10000
  • 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.

Hints for Find Smallest Letter Greater Than Target

  1. Hint 1

    The array is sorted, so the answer is the first position whose letter exceeds target.

  2. Hint 2

    That is an upper-bound binary search.

  3. Hint 3

    If the search falls off the end, the answer wraps to index 0.

How to solve Find Smallest Letter Greater Than Target

This is an upper bound: find the leftmost index whose letter is strictly greater than target. Binary search locates it, and running past the end means every letter is at most target, so the wrap takes over.

Approach

  1. Search over [0, n] for the first index with letters[mid] > target.
  2. Move hi to mid when the letter is greater, otherwise lo past mid.
  3. Return letters[lo], or letters[0] when lo == n.

Why it works

Because the array is sorted, the predicate letters[i] > target is false for a prefix and true for the rest, so the boundary is unique and binary search converges on it. The guarantee that two different characters exist means the wrap never returns something equal to target in a way that breaks the 'strictly greater' promise — the wrapped answer is deliberately smaller.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • Using >= finds an equal letter, which the problem excludes.
  • Forgetting the wrap-around returns out of bounds for a target at or above every letter.
  • A linear scan works at this size but misses the point of the exercise.

Reference solution

Python

from typing import List

def nextGreatestLetter(letters: List[str], target: str) -> str:
    lo, hi = 0, len(letters)
    while lo < hi:
        mid = (lo + hi) // 2
        if letters[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    return letters[0] if lo == len(letters) else letters[lo]

Java

public static String nextGreatestLetter(String[] letters, String target) {
    int lo = 0, hi = letters.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (letters[mid].compareTo(target) > 0) hi = mid; else lo = mid + 1;
    }
    return lo == letters.length ? letters[0] : letters[lo];
}

C++

string nextGreatestLetter(vector<string>& letters, string target) {
    int lo = 0, hi = (int) letters.size();
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (letters[mid] > target) hi = mid; else lo = mid + 1;
    }
    return lo == (int) letters.size() ? letters[0] : letters[lo];
}

JavaScript

var nextGreatestLetter = function(letters, target) {
    var lo = 0, hi = letters.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (letters[mid] > target) hi = mid; else lo = mid + 1;
    }
    return lo === letters.length ? letters[0] : letters[lo];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search