Find Smallest Letter Greater Than Target | Binary Search | Coding Interview
For the last few months, I have been writing articles on system design, and I thought, let’s take a little break and write an article on a coding problem. This problem will come under the category of binary search.
Description
In computer science, lexicographic order, also known as lexical or alphabetic order, is how words are arranged in a dictionary or a list. It is based on the alphabetical order of the characters that make up the word.
Given an array of characters, and letters, that are sorted in non-decreasing order and a character target, the task is to find the most minor character in letters that is lexicographically greater than the target. If such a character does not exist, the first character in letters should be returned.
Examples:
Example: [a, g,i, k]
Target: j
Output: k
Explanation: The target character is j so the lowest (lexicographically)
character after j is k.Approach 1 (binary search)
One way to approach this problem is to use a binary search algorithm to find the target character in the array. Once the target character is found, we can check the next character in the array to see if it is lexicographically greater than the target. If it is, we return that character as a result. If not, we continue searching the array until we find a character that is greater than the target or until we reach the end of the array.
Approach 2 (Simple iteration)
Another way to solve this problem is to iterate through the array, comparing each character to the target. When a character that is lexicographically greater than the target is found, it is returned as the result. If the end of the array is reached and no such character is found, the first character in the array is returned.
Implementation
To implement this, we can define a function that takes in two parameters: an array of characters, letters, and a character, target. We can use a for loop inside the function to iterate through the array. Within the loop, we can use an if statement to check if the current character is lexicographically greater than the target. If it is, we return that character as a result. If the end of the array is reached and no such character is found, the first character in the array is returned.
def smallest_char(letters, target):
for char in letters:
if char > target:
return char
return letters[0]It is important to note that this solution assumes that the input array is sorted in non-decreasing order and that there are at least two different characters in the array. If the input array is not sorted or if there is only one character in the array, the result of this function may not be as expected.
In conclusion, finding the smallest character in a given array of characters that is lexicographically greater than a target character can be accomplished by using a binary search algorithm or by iterating through the array and comparing each character to the target. The solution provided here is a simple and efficient way to solve this problem, assuming that the input array is sorted in non-decreasing order and that there are at least two different characters in the array.
That’s all 👍🏼.
Thanks 🤗.
Want to Hire/Connect? LinkedIn
P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and helps all the writers.
A clap would be highly appreciated if you liked what you just read. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do comment😋!
