We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Smallest Letter Greater Than Target

Number: 745

Difficulty: Easy

Paid? No

Companies: LinkedIn, Amazon, Google

Problem Description

Given a sorted array of characters and a target character, return the smallest character in the array that is lexicographically greater than the target. If no such character exists, return the first character in the array.

Key Insights

  • The array is sorted in non-decreasing order, which enables an efficient binary search solution.
  • The binary search is used to identify the first character greater than the target.
  • Account for the wrap-around scenario by returning the first character when the target is greater than or equal to all elements in the array.

Space and Time Complexity

Time Complexity: O(log n) where n is the length of the letters array
Space Complexity: O(1)

Solution

We can solve this problem using binary search. Initialize two pointers, left and right, to define the search boundaries. Compute the middle index and compare the character at that index with the target. If the current character is less than or equal to the target, move the left pointer to mid + 1; otherwise, move the right pointer to mid - 1. After the loop, use left % n (where n is the size of the array) to handle the wrap-around case and return the correct character.

Code Solutions

# Function to find the smallest letter greater than target using binary search.
def nextGreatestLetter(letters, target):
    # Initialize left and right pointers.
    left, right = 0, len(letters) - 1

    # Perform binary search.
    while left <= right:
        # Calculate the middle index.
        mid = left + (right - left) // 2

        # If the middle element is less than or equal to target, search in the right half.
        if letters[mid] <= target:
            left = mid + 1
        else:
            # Otherwise, search in the left half.
            right = mid - 1

    # Use modulo to handle wrap-around and return the next greatest letter.
    return letters[left % len(letters)]

# Example usage:
# letters = ['c', 'f', 'j']
# target = 'a'
# print(nextGreatestLetter(letters, target))  # Output: 'c'
← Back to All Questions