Next Letter (Smallest Letter Strictly Greater Than the Key, Wrapping Around)

• Next Letter is a modified binary search that finds the smallest element strictly greater than a given key in a sorted array of letters.
• Strictly greater means elements equal to the key are skipped, unlike the ceiling problem which accepts equal elements.
• Wrap-around means that if the key is greater than or equal to the last letter, the answer wraps back to the first letter in the array.
• The start pointer lands on the answer when the loop ends, and taking start % n handles the wrap-around in a single expression.
• Time and space are O(log n) and O(1), identical to standard binary search.

What is the Next Letter problem?

The Next Letter problem gives you a sorted array of lowercase letters and a target letter. You must find the smallest letter in the array that is strictly greater than the target. If the target is greater than or equal to every letter in the array, you wrap around and return the first letter.

For example, given letters ['a', 'c', 'f', 'h'] and target f, the answer is h because h is the smallest letter strictly greater than f. If the target were h or z, the answer wraps to a.

This is a classic modified binary search problem that tests whether you understand the difference between strictly greater and greater-than-or-equal comparisons.

package com.bank.coding;

/**
 * Next Letter: find the smallest letter strictly greater than the key,
 * with cyclic wrap-around.
 */
public class NextLetterFinder {

    public static char findNextLetter(char[] letters, char key) {
        int n = letters.length;
        int start = 0;
        int end = n - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (key >= letters[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        // Modulo wraps around when start == n
        return letters[start % n];
    }
}

Why does this problem exist?

This problem tests three skills in a single question. First, it tests whether you can write a correct binary search without off-by-one errors. Second, it tests whether you understand the subtle difference between strictly greater and greater-than-or-equal. Third, it tests whether you can handle cyclic boundaries cleanly.

In banking systems, cyclic lookups appear whenever identifiers rotate. Batch codes, sequence numbers, and scheduling slots all wrap around. A system that processes cheque batches labelled a through z needs to find the next batch code after the current one, wrapping from z back to a.

// Banking use case: find the next batch code after the current one
char[] batchCodes = {'a', 'c', 'f', 'h', 'k', 'p', 'z'};
char currentCode = 'p';
char nextCode = NextLetterFinder.findNextLetter(batchCodes, currentCode);
// nextCode is 'z'

char wrapCode = NextLetterFinder.findNextLetter(batchCodes, 'z');
// wrapCode is 'a' (wraps around)

How does the binary search work internally?

The search uses the standard binary search template with start = 0 and end = n - 1. In each iteration, we compute mid = start + (end - start) / 2 to avoid integer overflow.

The critical rule is the comparison: if key >= letters[mid], we move start = mid + 1. If key < letters[mid], we move end = mid - 1. The use of >= on the move-right branch is what makes this strictly greater. When the key equals letters[mid], we still move right, skipping that equal element.

When the loop ends, start points to the first element that is strictly greater than the key. If the key is greater than or equal to every element, start equals n, meaning it has moved past the end of the array. The modulo expression start % n wraps this back to index 0.

// Trace for letters = ['a', 'c', 'f', 'h'], key = 'f'
// Iteration 1: start=0, end=3, mid=1, letters[1]='c', 'f'>='c' -> start=2
// Iteration 2: start=2, end=3, mid=2, letters[2]='f', 'f'>='f' -> start=3
// Iteration 3: start=3, end=3, mid=3, letters[3]='h', 'f'<'h'  -> end=2
// Loop ends: start=3, letters[3 % 4] = letters[3] = 'h'

How is this different from the ceiling problem?

The ceiling problem finds the smallest element greater than or equal to the key. The Next Letter problem finds the smallest element strictly greater than the key. The difference is one comparison operator.

| Aspect | Ceiling | Next Letter |
|---|---|---|
| Goal | Smallest >= key | Smallest > key |
| Equal elements | Kept (answer can equal key) | Skipped (answer must exceed key) |
| Move-right condition | key > letters[mid] | key >= letters[mid] |
| Wrap-around | Not required | Required |
| Final answer | letters[start] if in bounds | letters[start % n] |

package com.bank.coding;

public class CeilingVsNextLetter {

    // Ceiling: smallest element >= key
    public static char findCeiling(char[] letters, char key) {
        int start = 0, end = letters.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (key > letters[mid]) {
                start = mid + 1;  // strictly greater moves right
            } else {
                end = mid - 1;    // equal or less moves left
            }
        }
        return start < letters.length ? letters[start] : '\0';
    }

    // Next Letter: smallest element strictly > key, with wrap
    public static char findNextLetter(char[] letters, char key) {
        int start = 0, end = letters.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (key >= letters[mid]) {
                start = mid + 1;  // >= moves right, skipping equals
            } else {
                end = mid - 1;
            }
        }
        return letters[start % letters.length];
    }

    public static void main(String[] args) {
        char[] codes = {'a', 'c', 'f', 'h'};
        System.out.println("Ceiling of 'f': " + findCeiling(codes, 'f'));    // f
        System.out.println("Next letter after 'f': " + findNextLetter(codes, 'f')); // h
    }
}

Ceiling of 'f': f
Next letter after 'f': h

What are the edge cases?

The most important edge case is the wrap-around. When the key is greater than or equal to the last element, the start pointer moves past the end of the array, and the modulo wraps it back to zero.

Other edge cases include a single-element array where the answer is always that element (it wraps to itself), duplicate letters in the array, and the key being smaller than every element.

package com.bank.coding;

public class NextLetterEdgeCases {

    public static void main(String[] args) {
        // Edge case 1: key >= last element, wrap around
        char[] codes = {'a', 'c', 'f', 'h'};
        System.out.println(NextLetterFinder.findNextLetter(codes, 'h')); // a (wrap)
        System.out.println(NextLetterFinder.findNextLetter(codes, 'z')); // a (wrap)

        // Edge case 2: single element
        char[] single = {'m'};
        System.out.println(NextLetterFinder.findNextLetter(single, 'a')); // m
        System.out.println(NextLetterFinder.findNextLetter(single, 'm')); // m (wrap)

        // Edge case 3: key smaller than all elements
        System.out.println(NextLetterFinder.findNextLetter(codes, 'A')); // a

        // Edge case 4: duplicates
        char[] dupes = {'a', 'a', 'c', 'c', 'f'};
        System.out.println(NextLetterFinder.findNextLetter(dupes, 'a')); // c
    }
}

a
a
m
m
a
c

What are common mistakes?

The most common mistake is using > instead of >= in the comparison, which makes the search find the ceiling instead of the strictly-greater element. When the key exists in the array, this wrong version returns the key itself instead of the next letter.

// WRONG: uses > instead of >=
public static char findNextLetterWrong(char[] letters, char key) {
    int start = 0, end = letters.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (key > letters[mid]) {  // BUG: should be >=
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return letters[start % letters.length];
}
// findNextLetterWrong({'a','c','f','h'}, 'f') returns 'f', not 'h'

// CORRECT: uses >= to skip equal elements
public static char findNextLetterCorrect(char[] letters, char key) {
    int start = 0, end = letters.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (key >= letters[mid]) {  // >= skips equals
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return letters[start % letters.length];
}
// findNextLetterCorrect({'a','c','f','h'}, 'f') returns 'h'

Another common mistake is forgetting the modulo for wrap-around, which causes an ArrayIndexOutOfBoundsException when the key is greater than or equal to the last element.

What is the time and space complexity?

The time complexity is O(log n) because each iteration of the binary search halves the search space. The space complexity is O(1) because only three integer variables are used.

This matches standard binary search exactly. The only additional cost is the single modulo operation at the end, which is O(1).

// Performance test with a large sorted letter array
char[] largeCodes = new char[26];
for (int i = 0; i < 26; i++) {
    largeCodes[i] = (char) ('a' + i);
}
// Binary search examines at most ceil(log2(26)) = 5 elements
char result = NextLetterFinder.findNextLetter(largeCodes, 'r');
// result is 's', found in at most 5 comparisons

How does the wrap-around work with modulo?

The wrap-around is the elegant part of this solution. When the key is greater than or equal to every element in the array, the start pointer advances past index n - 1 and reaches n. The expression start % n evaluates to 0, which is the first element.

When the key is not greater than or equal to every element, start stays within bounds and start % n equals start, so the modulo has no effect.

This single modulo replaces what would otherwise be an if-else branch at the end.

// Without modulo (verbose and error-prone)
public static char findNextLetterVerbose(char[] letters, char key) {
    int start = 0, end = letters.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (key >= letters[mid]) start = mid + 1;
        else end = mid - 1;
    }
    if (start >= letters.length) {
        return letters[0]; // wrap around
    }
    return letters[start];
}

// With modulo (clean, one line)
public static char findNextLetterClean(char[] letters, char key) {
    int start = 0, end = letters.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (key >= letters[mid]) start = mid + 1;
        else end = mid - 1;
    }
    return letters[start % letters.length]; // one line handles both cases
}

What about a linear scan alternative?

A linear scan walks through the array and returns the first letter strictly greater than the key. This is simpler to write but runs in O(n) time, which is worse than O(log n) for large arrays.

// Linear scan: O(n) time
public static char findNextLetterLinear(char[] letters, char key) {
    for (char letter : letters) {
        if (letter > key) {
            return letter;
        }
    }
    return letters[0]; // wrap around
}

The linear scan is acceptable for small arrays, but the binary search is the expected answer in an interview because it demonstrates mastery of the binary search template.

What should a senior engineer know?

A senior engineer should recognize that the Next Letter problem is one instance of a family of binary search variants. The ceiling, floor, first occurrence, last occurrence, and next letter problems all use the same template with different comparison operators.

The strictly-greater comparison using >= on the move-right branch is the distinguishing detail. This single operator change is what separates someone who memorized the pattern from someone who understands the mechanics.

The modulo trick for cyclic wrap-around generalizes to any problem where a sorted array represents a circular sequence. Scheduling systems, round-robin dispatchers, and rotating token assignments all use the same technique.

What are common interview follow-up questions?

Interviewers often ask these follow-ups after the Next Letter problem:

• What if you need the largest letter strictly less than the key (the floor variant)? Flip the comparison operator.
• What if the array is not sorted? You must sort it first or use a linear scan.
• What if there are duplicate letters? The >= comparison already handles duplicates correctly because it skips all copies of the key.
• Can you do this with Java's Arrays.binarySearch? Yes, but the insertion point returned by Arrays.binarySearch requires careful handling for the wrap-around.