Classical Binary Search
Latest LeetCode problem deals with classical binary search, here it is: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/
It is easy to read the hints here: ordered list, looking for a specific element in that list. Don't worry too much about the statement "it also wraps around". To handle this case add a simple check in the very beginning of the code checking whether the target is greater than or equal to the last element in "letters". If so, return the first element. Other than that, the rest of the code is a traditional, no-catches, binary search program. Hope you enjoy, Marcelo.
public class Solution
{
public char NextGreatestLetter(char[] letters, char target)
{
if (target >= letters[letters.Length - 1]) return letters[0];
int left = 0;
int right = letters.Length - 1;
while (left < right)
{
int mid = (left + right) / 2;
if (target >= letters[mid]) left = mid + 1;
else right = mid;
}
return letters[left];
}
}
Given a list of sorted characters
letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.
Letters also wrap around. For example, if the target is
target = 'z' and letters = ['a', 'b'], the answer is 'a'.
Examples:
Input: letters = ["c", "f", "j"] target = "a" Output: "c" Input: letters = ["c", "f", "j"] target = "c" Output: "f" Input: letters = ["c", "f", "j"] target = "d" Output: "f" Input: letters = ["c", "f", "j"] target = "g" Output: "j" Input: letters = ["c", "f", "j"] target = "j" Output: "c" Input: letters = ["c", "f", "j"] target = "k" Output: "c"
It is easy to read the hints here: ordered list, looking for a specific element in that list. Don't worry too much about the statement "it also wraps around". To handle this case add a simple check in the very beginning of the code checking whether the target is greater than or equal to the last element in "letters". If so, return the first element. Other than that, the rest of the code is a traditional, no-catches, binary search program. Hope you enjoy, Marcelo.
public class Solution
{
public char NextGreatestLetter(char[] letters, char target)
{
if (target >= letters[letters.Length - 1]) return letters[0];
int left = 0;
int right = letters.Length - 1;
while (left < right)
{
int mid = (left + right) / 2;
if (target >= letters[mid]) left = mid + 1;
else right = mid;
}
return letters[left];
}
}
Beautiful solution, Marcelo! There are 2 things that I'm usually trying to avoid though - (left + right) can lead to overflows (not relevant for this problem though, because the range is so limited) and right = mid makes it slightly less obvious that at every step we are shrinking the range. My ugly solution is below:
ReplyDeleteclass Solution {
public:
char nextGreatestLetter(const vector& letters, char target) {
int left = 0;
int right = letters.size() - 1;
char candidate = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (letters[mid] <= target) {
left = mid + 1;
} else {
candidate = letters[mid];
right = mid - 1;
}
}
return candidate == 0 ? letters.front() : candidate;
}
};
Cheers,
Taras
Love it! Your attention to details is nothing short of spectacular!!!
ReplyDeletehaha, I wish it was :) Btw, if you like binary search, you may also like https://leetcode.com/problems/search-a-2d-matrix ;)
Delete