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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Smallest Letter Greater Than Target

Difficulty: Easy

Problem Description

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters. Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

Key Insights

  • The array letters is sorted, allowing for efficient searching.
  • The problem can be solved using binary search to find the smallest character greater than target.
  • If no character is found that is greater than target, the first character of the array should be returned.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution utilizes a binary search approach to efficiently find the smallest character in a sorted array that is greater than the given target. By comparing the middle character of the array to the target, we can decide whether to search the left or right half of the array. If we exhaust the search without finding a greater character, we return the first character of the array.

Code Solutions

def nextGreatestLetter(letters, target):
    left, right = 0, len(letters) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if letters[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    return letters[left % len(letters)]
← Back to All Questions