Find Smallest Letter Greater Than Target — Circular Binary Search [LC 744]

Problem Statement#

Given a sorted array of characters letters (with duplicates allowed) and a target character, return the smallest character in letters that is strictly greater than target. The array wraps around: if no letter is greater, return letters[0].

Constraints:

• 2 <= letters.length <= 10^4
• 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

Input:  letters = ['c','f','j'], target = 'a'
Output: 'c'

Input:  letters = ['c','f','j'], target = 'c'
Output: 'f'

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

Why This Problem Matters#

LC 744 is a clean variant of left-boundary binary search with a circular wrap-around. It is asked by Google and Microsoft to verify that candidates can adapt the standard template to a slightly different condition (strict greater-than instead of greater-than-or-equal) and handle the edge case where no letter is greater.

The circular wrap using the modulo operator (lo % len(letters)) is a compact and elegant pattern that appears in many interview problems involving circular arrays, ring buffers, and modular indexing.

The Core Insight#

Left-boundary binary search finds the first index where letters[mid] > target (strict greater-than). The search range is [0, n] (open-ended), so if lo lands at n, there is no letter greater than target in the array. The circular wrap: return letters[lo % n]. If lo < n, this returns letters[lo]; if lo == n, it returns letters[0].

The comparison: when letters[mid] <= target (current letter is not greater), move lo = mid + 1. When letters[mid] > target, this could be the answer — set hi = mid.

Visual Dry Run#

Input: letters = ['c','f','j'], target = 'c'

Input: letters = ['x','x','y','y'], target = 'z'

Solution (Optimal)#

class Solution:
    def nextGreatestLetter(self, letters: list[str], target: str) -> str:
        n = len(letters)
        lo, hi = 0, n  # open-ended right bound to allow lo to reach n
 
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if letters[mid] <= target:
                lo = mid + 1  # not strictly greater; move right
            else:
                hi = mid       # could be the answer; keep mid in range
 
        # Circular wrap: if lo == n, no letter greater than target exists
        return letters[lo % n]

var nextGreatestLetter = function(letters, target) {
    const n = letters.length;
    let lo = 0, hi = n;  // open-ended right bound
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (letters[mid] <= target) {
            lo = mid + 1;  // not strictly greater; continue right
        } else {
            hi = mid;      // possible answer; narrow to left half including mid
        }
    }
 
    // lo % n gives letters[0] when lo == n (wrap around)
    return letters[lo % n];
};

Time: O(log n) — left-boundary binary search Space: O(1) — only pointer variables

Common Mistakes#

• Using letters[mid] < target instead of letters[mid] <= target — this finds the first letter >= target (not strictly greater), which is wrong when target exists in letters.
• Setting hi = n - 1 instead of hi = n — this prevents lo from reaching n, breaking the circular wrap for the case where all letters are <= target.
• Returning letters[lo] without the modulo when lo can equal n — causes an index-out-of-bounds error.
• Using the inclusive while lo <= hi template — this template requires a different return value logic and can cause off-by-one errors when combined with the open-ended hi = n.

Interview Tips#

• State the circular wrap-around case explicitly: "if all letters are <= target, return letters[0]."
• The modulo lo % n is the clean one-liner that handles both the normal case and the wrap-around case.
• Distinguish this from LC 35 (Search Insert Position): that problem finds where a value belongs, this finds the first value strictly greater. The difference is <= vs < in the comparison.
• This is a strict left-boundary search (first strictly-greater element), while LC 34 part 2 finds the first >= element.

Follow-up Questions#

• What if you want the largest letter strictly less than target? This is a right-boundary search on letters. Find the last index where letters[mid] < target.
• LC 35 (Search Insert Position): Find the position where a value would be inserted (first index >= target). Similar template with letters[mid] < target as the move-right condition.
• What if the array is not sorted? Sort first in O(n log n), then apply this search.
• What if multiple different letters can be the answer? The left-boundary search naturally returns the first (lexicographically smallest) one.
• Can this use bisect in Python? Yes — letters[bisect.bisect_right(letters, target) % n] gives the same result.

Key Takeaways#

• LC 744 is left-boundary binary search with strict inequality (letters[mid] <= target moves right) and a circular wrap-around at the end.
• Use open-ended hi = n so lo can reach n when all letters are <= target, then return letters[lo % n] to handle the wrap.
• The modulo lo % n elegantly handles both cases: when lo < n, it returns letters[lo]; when lo == n, it wraps to letters[0].
• The comparison letters[mid] <= target (not <) is the key to finding the strictly-greater boundary rather than the greater-or-equal boundary.
• This same circular wrap pattern appears in many ring buffer, circular array, and modular indexing problems.
• Google and Microsoft ask this problem to verify clean left-boundary template implementation and edge-case handling.
• The while lo < hi with hi = mid template is essential here — while lo <= hi requires a different structure that is more error-prone for this boundary-finding variant.