algoadvance

Given an array of characters letters that is sorted in non-decreasing order and a character target, your task is to find the smallest character in the array that is lexicographically greater than target. If such a character does not exist, return the first character in the array.

You can assume that:

• letters has at least 2 characters.
• All the characters in letters are in lowercase and are sorted in non-decreasing order.
• target is a lowercase letter.

Clarifying Questions

1. Can the target character be in the letters array?
   • Yes, it can be in the array.
2. What should be returned if all characters in letters are less than or equal to target?
   • If all characters in the letters array are less than or equal to target, return the first character in the array.
3. Are there any constraints on the size of the letters array?
   • The problem does not specify an explicit constraint, but it can be assumed to handle typical input sizes efficiently.

Strategy

1. Binary Search: To efficiently find the smallest character greater than target, a binary search algorithm can be employed because the letters array is sorted.
2. Circular Array Concept: If the target is greater than or equal to the last character in the array, the function should wrap around to the beginning of the array and return the first character because it is the smallest character greater than target by circular array logic.

Code

def nextGreatestLetter(letters, target):
    left, right = 0, len(letters) - 1
    
    # Check if all characters are less than or equal to target
    if target >= letters[-1]:
        return letters[0]
    
    while left < right:
        mid = (left + right) // 2
        if letters[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return letters[left]

# Example usage
letters = ["c", "f", "j"]
target = "a"
print(nextGreatestLetter(letters, target))  # Output: "c"

Explanation

1. Initial Check: If target is greater than or equal to the last character in letters, return the first character in letters.
2. Binary Search Logic:
   • Initialize left and right pointers to the start and end of the array.
   • Use binary search to narrow down the indices:
     • If letters[mid] is less than or equal to target, search in the right half by setting left = mid + 1.
     • Else, search in the left half by setting right = mid.
   • The loop exits when left and right point to the same index, which will be the smallest character greater than target.

Time Complexity

• The time complexity of this approach is O(log n) because it uses binary search.
• The space complexity is O(1) as no additional space is required apart from the input and variables.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?