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.
Example 1:
Input: letters = ["c","f","j"], target = "a" Output: "c" Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.
Example 2:
Input: letters = ["c","f","j"], target = "c" Output: "f" Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.
Example 3:
Input: letters = ["x","x","y","y"], target = "z" Output: "x" Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
Constraints:
2 <= letters.length <= 104letters[i] is a lowercase English letter.letters is sorted in non-decreasing order.letters contains at least two different characters.target is a lowercase English letter.The simplest way to solve the problem is to iterate over the array and find the first character that is greater than the target character. If such a character is not found by the end of the array, the function should return the first character of the array. This approach simply checks each character in order from left to right, comparing it with the target.
The function iterates through each element in the letters array. As soon as it finds a letter that is greater than target, it returns that letter. If no such letter is found, it returns the first element of the array since the array is viewed in a circular manner.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the size of the array since each element may be checked in the worst case.
Space Complexity: O(1) as only a constant amount of space is used.
Utilizing the sorted nature of the array, we can employ a binary search technique to pinpoint the smallest character that exceeds the target. By continually narrowing the search range, we can efficiently determine the desired character. If the binary search concludes without finding a suitable character, the array's initial character is returned.
This function relies on the binary search algorithm. The search confines focus to the mid-value, adjusting based on its comparison to target. If mid is greater, the search shifts left; otherwise, right. Upon termination, the remainder of low mod lettersSize returns the correct character for the circular case.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n), hinging on halving the array.
Space Complexity: O(1), processing is constant-space.
| Approach | Complexity |
|---|---|
| Brute Force Linear Scan | Time Complexity: O(n) where n is the size of the array since each element may be checked in the worst case. |
| Binary Search | Time Complexity: O(log n), hinging on halving the array. |
[Java] Leetcode 744. Find Smallest Letter Greater Than Target [Binary Search #3] • Eric Programming • 7,957 views views
Watch 9 more video solutions →Practice Find Smallest Letter Greater Than Target with our built-in code editor and test cases.
Practice on FleetCode