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

Source: Dev.to

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 target.
• If no such character exists (i.e., target is larger than or equal to every element), return the first character in the list.

Intuition

Because the array is already sorted, we can avoid a linear scan ( O(n) ) and instead apply binary search ( O(log n) ).

The algorithm follows a “search and discard” approach:

1. Examine the middle element.
2. If letters[mid] > target – this could be the answer. Record the index and continue searching the left half for an even smaller qualifying character.
3. If letters[mid] ≤ target – the middle element and everything to its left are too small. Discard them and search the right half.

If the search finishes without finding a greater character, we “wrap around” and return letters[0].

Walkthrough: Understanding the Examples

Example 1

letters = ["c", "f", "j"], target = "a"

The first character greater than 'a' is 'c'.

Result: "c"

Example 2

letters = ["c", "f", "j"], target = "c"

'c' is not allowed because we need a strictly greater character. The next one is 'f'.

Result: "f"

Example 3

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

No character is greater than 'z'; we wrap around to the first element.

Result: "x"

Code Implementation

C++

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

        while (left  target) {
                firstTrueIndex = mid;
                right = mid - 1;          // look for a smaller qualifying character
            } else {
                left = mid + 1;           // discard left half
            }
        }

        return firstTrueIndex == -1 ? letters[0] : 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  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]

JavaScript

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

    while (left  target) {
            firstTrueIndex = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

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

Key Takeaways

• Binary Search Efficiency: Reduces the search space by half each iteration, achieving O(log n) time instead of O(n).
• Upper Bound Pattern: This problem is a classic “upper bound” search—finding the first element strictly greater than a given value.
• Wrap‑Around Handling: Using a sentinel value (e.g., firstTrueIndex = -1) or modulo arithmetic provides a clean way to implement circular array logic.

Final Thoughts

This problem is an excellent introduction to optimizing search functionality. Real‑world systems such as file explorers or contact lists often need to jump to the “next greatest” entry when a user types a character. Mastering binary search not only prepares you for technical interviews at top tech companies but also equips you to write performant code that scales to millions of entries.