🔍 Beginner-Friendly Guide 'Find Smallest Letter Greater Than Target' - Problem 744 (C++, Python, JavaScript)

Finding the next item in a sorted list is a fundamental skill in software development. Whether you are navigating a database or building an autocomplete feature, knowing how to efficiently locate the next specific value is essential. This guide will teach you how to use Binary Search to solve this problem with optimal speed.

---

Problem Summary

You're given:

• A sorted list of characters called letters.
• A specific character called target.

Your goal:

• Find the smallest character in the list that is strictly "greater" than the target.
• If no such character exists (meaning the target is larger than or equal to everything in the list), return the very first character in the list.

---

Intuition

Since the input array is already sorted, we do not need to check every single letter one by one. Checking every element would take time. Instead, we can use Binary Search to find our answer in time.

The logic follows a "search and discard" approach. We look at the middle element:

1. Is the middle letter greater than our target? If yes, this could be our answer. We save this index and then look at the left half to see if there is an even smaller letter that still beats the target.
2. Is the middle letter less than or equal to our target? If so, the middle letter and everything to its left are too small. We discard them and move our search to the right half.

Finally, we handle the "wrap-around" condition. If our search finishes and we never found a letter greater than the target, we simply return the first element of the array.

---

Walkthrough: Understanding the Examples

Example 1: letters = ["c", "f", "j"], target = "a"

• Binary search looks for the first character greater than 'a'.
• 'c' is the first one it encounters that fits the criteria.
• Result: "c"

Example 2: letters = ["c", "f", "j"], target = "c"

• Binary search ignores 'c' because we need something strictly greater.
• The next available character is 'f'.
• Result: "f"

Example 3: letters = ["x", "x", "y", "y"], target = "z"

• Binary search looks for anything greater than 'z'.
• Nothing in the list is greater than 'z'.
• Since no valid character is found, we wrap around to the start.
• Result: "x"

---

Code Implementation

C++

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int n = letters.size();
        int left = 0;
        int right = n - 1;
        int firstTrueIndex = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (letters[mid] > target) {
                firstTrueIndex = mid; 
                right = mid - 1; 
            } else {
                left = mid + 1;
            }
        }

        if (firstTrueIndex == -1) {
            return letters[0];
        }
        return letters[firstTrueIndex];
    }
};

Python

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left, right = 0, n - 1
        first_true_index = -1

        while left <= right:
            mid = left + (right - left) // 2

            # Check if the current letter is greater than the target
            if letters[mid] > target:
                first_true_index = mid
                right = mid - 1
            else:
                left = mid + 1

        # If no character was greater, wrap around to the first index
        if first_true_index == -1:
            return letters[0]

        return letters[first_true_index]

JavaScript

/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function(letters, target) {
    let n = letters.length;
    let left = 0;
    let right = n - 1;
    let firstTrueIndex = -1;

    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);

        if (letters[mid] > target) {
            firstTrueIndex = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return firstTrueIndex === -1 ? letters[0] : letters[firstTrueIndex];
};

---

Key Takeaways

• Binary Search Efficiency: By cutting the search space in half each time, we achieve a time complexity of instead of .
• Lower Bound vs. Upper Bound: This problem is a classic variation of finding the "Upper Bound," where we look for the first element strictly greater than a value.
• The Wrap-Around Pattern: Using a flag (like firstTrueIndex = -1) or modulo arithmetic is a standard way to handle "circular" array logic in algorithms.

---

Final Thoughts

This problem is a fantastic introduction to how engineers optimize search functionality. In real-world systems like a File Explorer or a Contact List, typing a letter often jumps you to the "next greatest" entry. Mastering Binary Search is one of the most important milestones for technical interviews at companies like Google or Amazon, as it demonstrates your ability to write code that performs well even as data scales to millions of entries.