0608EasyArrayBinary Search

Next Divider Label Round the Drawer

Tracked in this browser only

Trains the technique from

LeetCode 744Find Smallest Letter Greater Than Target

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A filing drawer holds card dividers standing front to back. Each divider carries a single lowercase letter as its label, and letters lists those labels from front to back in non-decreasing order. Two dividers may carry the same label, but the drawer always shows at least two different labels.

You are also given a single lowercase letter target. Return the smallest label in the drawer that comes strictly after target in the alphabet.

If no label in the drawer comes after target, the search runs off the back of the drawer and continues from the front, so return the smallest label in the drawer instead. Return the label itself, not where it sits.

Examples

Example 1

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

Both `f` and `j` come after `d` in the alphabet, and `f` is the smaller of the two.

Example 2

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

No label in the drawer comes after `j`, so the search wraps to the front and gives the smallest label, which is `c`.

Example 3

Input: letters = ["b", "b", "d", "d", "f"], target = "b"
Output: "d"

The two `b` labels do not count, since the answer must come strictly after `b`. The smallest label that does is `d`.

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 letters.
target is a lowercase English letter.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def next_greatest_letter(letters: list[str], target: str) -> str:

Java

public char nextGreatestLetter(char[] letters, char target)

The intended approach

Time O(log n) for the bisection.Space O(1).

Because the labels rise from front to back, every label that is at most `target` sits in one unbroken block at the front of the drawer, and the answer is whatever sits directly behind that block. Bisect for the boundary: keep a window and, at each step, move the left edge past the midpoint when its label is at most `target`, otherwise pull the right edge down to the midpoint. If the boundary lands one past the last divider then nothing beats `target`, and reducing the boundary modulo the drawer size wraps it to the front divider, which holds the smallest label.

Pythonentry point: next_greatest_letter

def next_greatest_letter(letters, target):
    # O(log n) time, O(1) space. The labels are already in non-decreasing order,
    # so the ones at or before target form a block at the front. Bisect for the
    # first position past that block; when the block is the whole drawer that
    # position is one off the end, and wrapping it round lands on the front.
    low = 0
    high = len(letters)
    while low < high:
        mid = (low + high) // 2
        if letters[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return letters[low % len(letters)]

The obvious version

Look at every label in turn and remember the smallest one that comes after `target`. If no label qualifies, scan again for the smallest label in the drawer and return that instead.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_next_greatest_letter(letters, target):
    above = None
    for label in letters:
        if label > target:
            if above is None or label < above:
                above = label
    if above is not None:
        return above
    smallest = letters[0]
    for label in letters:
        if label < smallest:
            smallest = label
    return smallest

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in