# LeetCode 744: Find Smallest Letter Greater Than Target

## Problem Restatement

We are given a sorted list of lowercase letters:

```python
letters
```

and a target character:

```python
target
```

We must return the smallest character in `letters` that is strictly greater than `target`.

The letters wrap around.

This means:

```text
if no character is greater than target,
return the first character in the array
```

The official problem states that `letters` is sorted in non-decreasing order and contains at least two different characters. ([leetcode.com](https://leetcode.com/problems/find-smallest-letter-greater-than-target/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Sorted character list `letters` and character `target` |
| Output | Smallest character strictly greater than `target` |
| Wraparound | If no larger character exists, return `letters[0]` |

Example function shape:

```python
def nextGreatestLetter(
    letters: list[str],
    target: str,
) -> str:
    ...
```

## Examples

### Example 1

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

The smallest character greater than `"a"` is:

```python
"c"
```

So the answer is:

```python
"c"
```

### Example 2

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

We need a character strictly greater than `"c"`.

The answer is:

```python
"f"
```

### Example 3

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

No character is greater than `"z"`.

So we wrap around and return:

```python
"x"
```

## First Thought: Linear Scan

Since the array is sorted, we could scan from left to right.

The first character satisfying:

```python
letter > target
```

is the answer.

If no such character exists, return the first character.

This works in `O(n)` time.

But the array is already sorted, so binary search is a better fit.

## Key Insight

We want the first element satisfying:

```python
letters[i] > target
```

This is a standard binary search pattern:

```text
find first valid position
```

If no valid position exists, wrap around to index `0`.

## Algorithm

Use binary search on the sorted array.

Maintain:

```python
left = 0
right = len(letters)
```

While:

```python
left < right
```

compute:

```python
mid = (left + right) // 2
```

If:

```python
letters[mid] <= target
```

then the answer must be to the right:

```python
left = mid + 1
```

Otherwise:

```python
right = mid
```

At the end:

- If `left == len(letters)`, wrap around.
- Otherwise return `letters[left]`.

A compact way is:

```python
letters[left % len(letters)]
```

## Correctness

The array is sorted in non-decreasing order.

The binary search maintains the invariant that every index before `left` contains a character less than or equal to `target`, and every index at or after `right` is still a possible answer.

When:

```python
letters[mid] <= target
```

the character at `mid` cannot be the answer because the answer must be strictly greater than `target`. Therefore all indices up to `mid` can be discarded, and setting:

```python
left = mid + 1
```

is correct.

When:

```python
letters[mid] > target
```

the position `mid` could be the answer, so we keep it in the search range by setting:

```python
right = mid
```

The loop stops when `left == right`. At that point, `left` is the first index whose character is strictly greater than `target`.

If `left` equals the array length, then no character is greater than `target`. By the wraparound rule, the correct answer is the first character in the array.

Therefore the algorithm always returns the required character.

## Complexity

Let `n = len(letters)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n)` | Binary search halves the search range each step |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def nextGreatestLetter(
        self,
        letters: list[str],
        target: str,
    ) -> str:
        left = 0
        right = len(letters)

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

            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid

        return letters[left % len(letters)]
```

## Code Explanation

We search over the full array:

```python
left = 0
right = len(letters)
```

Notice that `right` is exclusive.

Inside the loop:

```python
mid = (left + right) // 2
```

If the middle character is too small or equal to the target:

```python
if letters[mid] <= target:
```

then the answer must be further right:

```python
left = mid + 1
```

Otherwise, the middle position may already be the first valid answer:

```python
right = mid
```

At the end, `left` points to the first character greater than `target`.

If no such character exists, `left` becomes:

```python
len(letters)
```

The modulo operation wraps it back to index `0`:

```python
letters[left % len(letters)]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.nextGreatestLetter(
        ["c", "f", "j"],
        "a",
    ) == "c"

    assert s.nextGreatestLetter(
        ["c", "f", "j"],
        "c",
    ) == "f"

    assert s.nextGreatestLetter(
        ["x", "x", "y", "y"],
        "z",
    ) == "x"

    assert s.nextGreatestLetter(
        ["a", "b"],
        "z",
    ) == "a"

    assert s.nextGreatestLetter(
        ["a", "b"],
        "a",
    ) == "b"

    assert s.nextGreatestLetter(
        ["e", "e", "e", "k", "q", "q"],
        "e",
    ) == "k"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Target smaller than all letters | Returns first valid character |
| Exact match | Must return strictly greater character |
| Wraparound case | No larger character exists |
| Small array | Basic boundary handling |
| Two-element array | Checks exact comparison |
| Duplicate letters | Finds first greater character after duplicates |