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.In #744 Find Smallest Letter Greater Than Target, you are given a sorted array of lowercase characters and a target character. The task is to return the smallest letter strictly greater than the target. The array is circular, meaning if no character is greater than the target, the answer wraps around to the first element.
A straightforward idea is to scan the array linearly and track the first character greater than the target. While simple, this takes O(n) time.
Since the array is already sorted, a more efficient strategy is to apply binary search. The goal is to locate the first index where the character is strictly greater than the target. If the search moves past the last element, you return the first character due to the circular condition. This approach significantly improves efficiency.
The binary search technique reduces the search space each step, giving a time complexity of O(log n) while using constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan | O(n) | O(1) |
| Binary Search | O(log n) | O(1) |
Eric Programming
Use these hints if you're stuck. Try solving on your own first.
Try to find whether each of 26 next letters are in the given string array.
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.
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.
1#include <stdio.h>
2
3char nextGreatestLetter(char* letters, int lettersSize, char target) {
4 for (int i = 0;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.
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.
Time Complexity: O(log n), hinging on halving the array.
Space Complexity: O(1), processing is constant-space.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem states that the letters wrap around. This means if no character in the array is greater than the target, the answer should be the first character in the array. This ensures a valid result always exists.
Yes, this type of problem is common in coding interviews because it tests understanding of binary search variations. Many companies ask similar questions to evaluate search optimization and boundary handling.
The main data structure used is a sorted array of characters. The binary search algorithm operates on this array to efficiently locate the smallest character greater than the target.
The optimal approach uses binary search because the array of characters is already sorted. By finding the first element strictly greater than the target, we can reduce the time complexity to O(log n) instead of scanning the entire array.
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.