Problem Description

You have an array of characters letters that is sorted in non-decreasing order (alphabetically), and you're given a character target. The array contains at least two different characters.

Your task is to find the smallest character in letters that comes after target in alphabetical order (lexicographically greater). If no such character exists in the array, you should wrap around and return the first character in letters.

For example:

• If letters = ['c', 'f', 'j'] and target = 'a', the answer is 'c' because it's the smallest character greater than 'a'.
• If letters = ['c', 'f', 'j'] and target = 'd', the answer is 'f' because it's the smallest character greater than 'd'.
• If letters = ['c', 'f', 'j'] and target = 'j', the answer is 'c' because no character in the array is greater than 'j', so we wrap around to the beginning.

The solution uses binary search with bisect_right to efficiently find the insertion point where target would go in the sorted array. The function returns the index of the first element greater than target. By taking this index modulo the array length (i % len(letters)), we handle the wrap-around case when no greater character exists.

Intuition

Since the array is already sorted, we can leverage this property to find our answer efficiently. Think of it like looking up a word in a dictionary - you don't need to check every single word; you can jump to approximately where you expect the word to be and then narrow down your search.

The key insight is that we need to find the first character that is strictly greater than our target. In a sorted array, all characters greater than target will be grouped together on the right side, and all characters less than or equal to target will be on the left side. This naturally forms a boundary that we can search for.

Binary search is perfect for this because it repeatedly divides the search space in half. We're essentially asking: "Where would target be inserted if we wanted to maintain the sorted order?" The answer to this question gives us the index of the first character greater than target.

The clever part about using bisect_right is that it finds the rightmost position where target could be inserted. This means it automatically gives us the index of the first element that is strictly greater than target. If target is 'd' and we have ['a', 'c', 'f', 'j'], bisect_right would return index 2 (pointing to 'f').

The wrap-around behavior is elegantly handled with the modulo operator (%). If all characters in the array are less than or equal to target, bisect_right returns the length of the array. Taking this modulo the array length gives us 0, which correctly points back to the first character - exactly what the problem asks for when no greater character exists.

Learn more about Binary Search patterns.

Solution Approach

The solution uses binary search to find the smallest character that is larger than target. Let's walk through the implementation step by step.

We define the binary search boundaries with l = 0 as the left boundary and r = n as the right boundary, where n is the length of the array. The right boundary is set to n (not n-1) because we want to handle the case where all elements are less than or equal to target.

During each iteration of binary search, we calculate the middle position as mid = (l + r) / 2. We then compare letters[mid] with target:

• If letters[mid] > target, we've found a character greater than target, but we need to check if there's an even smaller valid character in the left half. So we set r = mid to continue searching in the left portion.

• If letters[mid] <= target, the character at mid is not what we want, so we need to search in the right half. We set l = mid + 1 to exclude the current element and everything to its left.

The binary search continues until l equals r, at which point l will be pointing to:

• The index of the smallest character greater than target, if such a character exists
• The value n (length of the array), if all characters are less than or equal to target

Finally, we return letters[l % n]. The modulo operation handles the wrap-around case beautifully:

• If l < n, then l % n = l, and we return the character at index l
• If l = n (meaning no character is greater than target), then l % n = 0, and we return the first character in the array

The Python implementation uses bisect_right which internally performs this exact binary search logic. It finds the rightmost position where target could be inserted while maintaining sorted order, which is equivalent to finding the first element strictly greater than target. The key=lambda c: ord(c) ensures we're comparing the ASCII values of characters for proper lexicographic comparison.

Example Walkthrough

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

Step 1: Initialize boundaries

• Array: ['c', 'f', 'j']
• n = 3 (length of array)
• l = 0 (left boundary)
• r = 3 (right boundary - note it's the length, not the last index)

Step 2: First iteration of binary search

• Calculate middle: mid = (0 + 3) // 2 = 1
• Check letters[1] which is 'f'
• Compare: 'f' > 'd'? Yes!
• Since we found a character greater than target, but need to check if there's a smaller valid one, set r = mid = 1
• New boundaries: l = 0, r = 1

Step 3: Second iteration

• Calculate middle: mid = (0 + 1) // 2 = 0
• Check letters[0] which is 'c'
• Compare: 'c' > 'd'? No!
• Since 'c' <= 'd', we need to search right, set l = mid + 1 = 1
• New boundaries: l = 1, r = 1

Step 4: Search complete

• l == r, so binary search ends
• l = 1 points to index 1

Step 5: Return result

• Calculate l % n = 1 % 3 = 1
• 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: If target = 'j' with the same array ['c', 'f', 'j']:

• Binary search would end with l = 3 (pointing past the array)
• Calculate l % n = 3 % 3 = 0
• Return letters[0] which is 'c'

This demonstrates how the modulo operation elegantly handles the wrap-around case when no character is greater than the target.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the length of the letters array. This is because bisect_right performs a binary search on the sorted array, which divides the search space in half with each iteration.

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the index i and perform the modulo operation. The key parameter in bisect_right creates a lambda function, but this doesn't scale with the input size and is considered constant space.

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

Common Pitfalls

1. Forgetting the Wrap-Around Case

One of the most common mistakes is forgetting to handle the case where all characters in the array are less than or equal to the target. Without proper handling, this would result in an index out of bounds error.

Incorrect approach:

def nextGreatestLetter(self, letters: List[str], target: str) -> str:
    insertion_index = bisect_right(letters, target)
    return letters[insertion_index]  # IndexError when insertion_index == len(letters)

Solution: Always use modulo operation to wrap around:

return letters[insertion_index % len(letters)]

2. Using bisect_left Instead of bisect_right

Another pitfall is using bisect_left instead of bisect_right. This causes incorrect results when the target character exists in the array.

Example of the issue:

# If letters = ['a', 'c', 'c', 'f'] and target = 'c'
# bisect_left would return index 1 (first 'c')
# letters[1 % 4] = 'c' (wrong - returns the same character)
# bisect_right would return index 3 (after last 'c')  
# letters[3 % 4] = 'f' (correct - returns next greater character)

Solution: Always use bisect_right to find the position after all occurrences of the target.

3. Manual Binary Search Off-by-One Errors

When implementing binary search manually, it's easy to make off-by-one errors with the boundaries.

Common mistakes:

# Wrong: Setting right boundary to n-1
l, r = 0, len(letters) - 1
# This fails to handle the case where all elements <= target

# Wrong: Incorrect update logic
if letters[mid] > target:
    r = mid - 1  # Should be r = mid to keep the valid answer in range

Solution: Set the right boundary to n (not n-1) and use r = mid when letters[mid] > target:

l, r = 0, len(letters)
while l < r:
    mid = (l + r) // 2
    if letters[mid] > target:
        r = mid  # Keep mid as potential answer
    else:
        l = mid + 1
return letters[l % len(letters)]

4. Not Understanding the Problem's Definition of "Next Greatest"

Some might misinterpret the problem and think they need to find any character greater than target, not necessarily the smallest one.

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

Solution: Always remember you're looking for the smallest character that is strictly greater than the target, not just any greater character.