Solution Approach

The solution uses binary search with the standard boundary-finding template to find the smallest character that is larger than target.

Defining the Feasible Function

For this problem, we define feasible(mid) as: "Is letters[mid] greater than target?"

This creates a boolean array pattern across indices:

letters:  ['c', 'f', 'j']
target:   'd'
feasible: [false, true, true]

We want to find the first true index - the smallest index where letters[mid] > target.

Binary Search Template

We use the standard template with first_true_index tracking:

1. Initialize left = 0, right = n - 1 (last valid index), and first_true_index = -1
2. While left <= right:
   • Calculate mid = (left + right) // 2
   • If letters[mid] > target (feasible):
     • Record first_true_index = mid as a potential answer
     • Search left half: right = mid - 1 (look for smaller valid index)
   • Else:
     • Search right half: left = mid + 1
3. After the loop, first_true_index contains the index of the smallest character greater than target, or -1 if none exists

Handling the Wrap-Around

The problem requires wrapping to the first character if no greater character exists. We handle this by checking first_true_index:

• If first_true_index != -1: return letters[first_true_index]
• If first_true_index == -1: return letters[0] (wrap around)

This explicit handling is cleaner than using modulo arithmetic because it makes the wrap-around logic visible and intentional.

Example Walkthrough

Let's walk through an example with letters = ['c', 'f', 'j'] and target = 'd'.

Step 1: Initialize

• Array: ['c', 'f', 'j']
• left = 0, right = 2 (last valid index)
• first_true_index = -1

Step 2: First iteration (left=0, right=2)

• Calculate mid = (0 + 2) // 2 = 1
• Check letters[1] which is 'f'
• Is 'f' > 'd'? Yes! (feasible)
• Record first_true_index = 1
• Search left: right = mid - 1 = 0

Step 3: Second iteration (left=0, right=0)

• Calculate mid = (0 + 0) // 2 = 0
• Check letters[0] which is 'c'
• Is 'c' > 'd'? No! (not feasible)
• Search right: left = mid + 1 = 1

Step 4: Loop ends (left=1 > right=0)

• first_true_index = 1 (found a valid answer)
• Return letters[1] which is 'f'

The answer is 'f', which is correct as it's the smallest character greater than 'd'.

Wrap-around example: letters = ['c', 'f', 'j'], target = 'j'

Step 1: Initialize

• left = 0, right = 2, first_true_index = -1

Step 2: First iteration (left=0, right=2)

• mid = 1, letters[1] = 'f'
• Is 'f' > 'j'? No!
• Search right: left = 2

Step 3: Second iteration (left=2, right=2)

• mid = 2, letters[2] = 'j'
• Is 'j' > 'j'? No!
• Search right: left = 3

Step 4: Loop ends (left=3 > right=2)

• first_true_index = -1 (no character greater than target found)
• Wrap around: return letters[0] which is 'c'

This demonstrates how tracking first_true_index explicitly handles the wrap-around case when no character is greater than the target.

Time and Space Complexity

The time complexity is O(log n), where n is the length of the letters array. Binary search divides the search space in half with each iteration, resulting in logarithmic time.

The space complexity is O(1). The algorithm only uses a constant number of variables (left, right, mid, first_true_index) regardless of input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the standard template. This variant works but is harder to reason about and inconsistent with the boundary-finding pattern.

Incorrect variant:

left, right = 0, len(letters)
while left < right:
    mid = (left + right) // 2
    if letters[mid] > target:
        right = mid  # Different from template
    else:
        left = mid + 1
return letters[left % len(letters)]

Correct template:

left, right = 0, len(letters) - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if letters[mid] > target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return letters[0] if first_true_index == -1 else letters[first_true_index]

2. Forgetting the Wrap-Around Case

Without handling the case where no character is greater than target, you'll get an index out of bounds error or incorrect result.

Incorrect approach:

# Assumes first_true_index will always be found
return letters[first_true_index]  # Error when first_true_index == -1

Solution: Check for -1 and wrap to first character:

if first_true_index == -1:
    return letters[0]
return letters[first_true_index]

3. Wrong Feasible Condition

Using >= instead of > will return the target itself if it exists, instead of the next greater character.

Incorrect:

if letters[mid] >= target:  # Wrong: includes target itself
    first_true_index = mid
    right = mid - 1

Correct:

if letters[mid] > target:  # Correct: strictly greater
    first_true_index = mid
    right = mid - 1

4. Not Understanding "Smallest Greater"

Some might return any character greater than target. The problem asks for the smallest such character.

Example: If letters = ['a', 'c', 'f', 'j'] and target = 'b', returning 'f' or 'j' is wrong. The correct answer is 'c' as it's the smallest character greater than 'b'.

The binary search template naturally handles this by searching left (right = mid - 1) when we find a valid answer, ensuring we find the leftmost (smallest) valid index.