LeetCode 744 - Find Smallest Letter Greater Than Target

LeetCode Problem 744

Difficulty: 🟢 Easy
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a sorted array of lowercase English letters and a target character. Our task is to find the smallest character in the array that is strictly greater than the target character in lexicographical order.

Lexicographical order for characters is simply alphabetical order. For example, 'f' is greater than 'c', and 'x' is greater than 'm'.

An important detail is the wrap-around behavior. If the target is greater than or equal to every character in the array, we do not return nothing or an invalid value. Instead, we return the first character in the array. This effectively treats the array as circular.

For example:

• If letters = ["c","f","j"] and target = "c", the answer is "f" because it is the smallest letter strictly greater than "c".
• If letters = ["x","x","y","y"] and target = "z", there is no character greater than "z", so we wrap around and return "x".

The constraints tell us several important things:

• The array is already sorted in non-decreasing order.
• The array length can be as large as 10^4.
• The characters are only lowercase English letters.
• There are at least two distinct characters.

The sorted property is the key observation. Whenever we have a sorted array and need to find the first element satisfying some condition, binary search becomes a strong candidate.

There are several edge cases that can cause mistakes in a naive implementation:

• The target may be smaller than every character.
• The target may be larger than every character.
• The target may appear multiple times in the array.
• The array may contain many duplicate letters.
• The answer may require wrap-around to index 0.

The problem guarantees that a valid answer always exists because of the wrap-around rule.

Approaches

Brute Force Approach

The simplest solution is to scan the array from left to right and return the first character greater than the target.

Because the array is sorted, the first matching character is automatically the smallest valid answer.

If we finish scanning the array and never find a character greater than the target, we return letters[0].

This approach is correct because it explicitly checks every character in increasing order. The first character satisfying the condition must be the correct answer.

However, the worst-case time complexity is linear, O(n), because we may need to examine the entire array.

Optimal Approach, Binary Search

The important observation is that the array is sorted.

We are looking for the first position where:

letters[i] > target

This is exactly the type of condition binary search is designed for.

Instead of checking every element one by one, binary search repeatedly cuts the search space in half. At each step:

• If letters[mid] <= target, then the answer must be to the right.
• Otherwise, letters[mid] > target, so this position could be the answer, but there might be a smaller valid character on the left.

After the search finishes:

• If we found a valid position, return it.
• If the search moves past the end of the array, wrap around and return letters[0].

This reduces the time complexity from O(n) to O(log n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scan linearly until finding a character greater than target
Optimal	O(log n)	O(1)	Use binary search to locate the first valid character

Algorithm Walkthrough

1. Initialize two pointers, left and right.

left starts at 0, and right starts at len(letters) - 1. These pointers define the current search range. 2. Perform binary search while left <= right.

At every iteration, calculate:

mid = (left + right) // 2

This gives the middle index of the current search space. 3. Compare letters[mid] with the target.

If:

letters[mid] <= target

then this character cannot be the answer because we need a strictly greater character.

Since the array is sorted, everything at or before mid is also not useful, so move:

left = mid + 1

4. Otherwise, letters[mid] > target.

This means the current character is a valid candidate answer.

However, there might be an even smaller valid character on the left side, so continue searching:

right = mid - 1

5. Continue until the search space becomes empty.

At this point, left represents the insertion position where a character greater than the target should appear. 6. Handle wrap-around.

If left == len(letters), it means every character in the array is less than or equal to the target.

In that case, return:

letters[0]

7. Otherwise, return letters[left].

This is the smallest character strictly greater than the target.

Why it works

Binary search maintains the invariant that every index before left contains characters less than or equal to the target, while any potential answer must lie at or after left.

When the search terminates, left is exactly the first position containing a character greater than the target. If such a position does not exist, the wrap-around rule requires returning the first character in the array.

Python Solution

from typing import List

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

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

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

        return letters[left % len(letters)]

The implementation starts by setting up the binary search boundaries using left and right.

Inside the loop, we compute the middle index and compare letters[mid] against the target.

When the middle character is less than or equal to the target, we know it cannot be the answer because the problem requires a strictly greater character. Therefore, we discard the left half including mid.

When the middle character is greater than the target, it becomes a potential answer. However, there could still be a smaller valid character earlier in the array, so we continue searching the left half.

After the loop finishes, left points to the first valid position. The expression:

left % len(letters)

handles wrap-around automatically. If left equals the array length, modulo converts it back to 0.

Go Solution

func nextGreatestLetter(letters []byte, target byte) byte {
    left := 0
    right := len(letters) - 1

    for left <= right {
        mid := left + (right-left)/2

        if letters[mid] <= target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return letters[left%len(letters)]
}

The Go implementation follows the exact same binary search logic as the Python version.

One small difference is the calculation of mid:

mid := left + (right-left)/2

This form avoids integer overflow in languages where integer sizes are fixed. While overflow is not an issue for this problem size, it is considered good binary search practice in Go and other systems languages.

The modulo operation is also used in Go to handle the wrap-around case cleanly.

Worked Examples

Example 1

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

We want the smallest letter greater than "a".

Step	left	right	mid	letters[mid]	Action
1	0	2	1	"f"	"f" > "a", move right
2	0	0	0	"c"	"c" > "a", move right
End	0	-1	-	-	return letters[0]

Result:

"c"

Example 2

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

Step	left	right	mid	letters[mid]	Action
1	0	2	1	"f"	"f" > "c", move right
2	0	0	0	"c"	"c" <= "c", move left
End	1	0	-	-	return letters[1]

Result:

"f"

Example 3

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

Step	left	right	mid	letters[mid]	Action
1	0	3	1	"x"	"x" <= "z", move left
2	2	3	2	"y"	"y" <= "z", move left
3	3	3	3	"y"	"y" <= "z", move left
End	4	3	-	-	wrap around

Since left == len(letters), we return:

letters[0] = "x"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space each iteration
Space	O(1)	Only a few pointer variables are used

The algorithm is highly efficient because each iteration removes half of the remaining search space. With at most log2(n) iterations, the runtime grows very slowly even for large inputs.

The space usage remains constant because no additional data structures are allocated.

Test Cases

sol = Solution()

# Provided examples
assert sol.nextGreatestLetter(["c", "f", "j"], "a") == "c"  # target smaller than all
assert sol.nextGreatestLetter(["c", "f", "j"], "c") == "f"  # exact match
assert sol.nextGreatestLetter(["x", "x", "y", "y"], "z") == "x"  # wrap around

# Target larger than all letters
assert sol.nextGreatestLetter(["a", "b"], "z") == "a"  # circular behavior

# Target equal to largest letter
assert sol.nextGreatestLetter(["a", "d", "f"], "f") == "a"  # wrap around after exact match

# Duplicate letters
assert sol.nextGreatestLetter(["c", "c", "f", "j"], "c") == "f"  # skip duplicates

# Minimum valid input size
assert sol.nextGreatestLetter(["a", "z"], "a") == "z"  # size 2 array

# Target between two letters
assert sol.nextGreatestLetter(["a", "d", "f"], "b") == "d"  # middle insertion point

# All early duplicates
assert sol.nextGreatestLetter(["a", "a", "b"], "a") == "b"  # move past repeated values

# Target smaller than first element
assert sol.nextGreatestLetter(["d", "e", "f"], "a") == "d"  # immediate answer

# Multiple duplicates with wrap around
assert sol.nextGreatestLetter(["e", "e", "e", "n", "n"], "z") == "e"  # wrap after duplicates

Test	Why
["c","f","j"], "a"	Validates normal search
["c","f","j"], "c"	Validates strict greater-than logic
["x","x","y","y"], "z"	Validates wrap-around behavior
["a","b"], "z"	Tests target larger than all letters
["a","d","f"], "f"	Tests exact match at largest element
["c","c","f","j"], "c"	Ensures duplicates are skipped correctly
["a","z"], "a"	Tests minimum array size
["a","d","f"], "b"	Tests insertion between letters
["a","a","b"], "a"	Tests repeated starting values
["d","e","f"], "a"	Tests target smaller than all letters
["e","e","e","n","n"], "z"	Tests wrap-around with duplicates

Edge Cases

Target Greater Than Every Character

A common mistake is forgetting the wrap-around behavior.

For example:

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

There is no character greater than "z", so the correct answer is "c".

The implementation handles this cleanly using:

letters[left % len(letters)]

When left becomes equal to the array length, modulo converts it back to index 0.

Duplicate Characters

The array may contain repeated values:

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

A buggy implementation might incorrectly return "c" itself.

The condition:

letters[mid] <= target

ensures that all characters equal to the target are skipped, guaranteeing we only return a strictly greater character.

Target Smaller Than All Characters

Consider:

letters = ["d","e","f"]
target = "a"

The answer should immediately be "d".

Binary search naturally handles this because every comparison will move the search toward the left side, eventually leaving left at index 0.

Very Small Arrays

The minimum array size is 2.

For example:

letters = ["a","z"]
target = "a"

Some implementations fail on tiny arrays because of incorrect loop conditions or pointer updates.

Using the standard binary search condition:

while left <= right

ensures that every valid index is examined correctly, even in the smallest allowed input sizes.