744. Find Smallest Letter Greater Than Target
Problem Description
The problem presents an array letters
of sorted characters in non-decreasing order and a target
character. The task is to find the smallest character in the array that is lexicographically greater than the target character. If no such character exists in the array, the requirement is to return the first character in letters
. Lexicographically greater means the character should come after the target character in the alphabet. It is guaranteed that the array contains at least two different characters.
Intuition
The intuitive approach to solving this problem is to use a binary search because the characters are sorted, which makes it possible to quickly eliminate half of the search space at each step. We search for the point where we can find the first character in letters
that is greater than target
. Here's a step-by-step intuition:
- Initialize two pointers,
left
andright
, at the beginning and at the end (plus one) of the array respectively. - While the
left
pointer is less than theright
pointer, we repeatedly divide the search space in half. We calculate a middle indexmid
by averagingleft
andright
. - We compare the character at the middle index with the
target
using their ASCII values (through theord
function). - If the character at the middle index is greater than the
target
character, we have to keep searching in the left part of the array to find the smallest character larger thantarget
, so we move theright
pointer tomid
. - If the character in the middle is less than or equal to
target
, we have to search in the right part of the array, so we increment theleft
pointer tomid + 1
. - When the
left
andright
pointers meet, they point at the smallest character greater than the target if such a character exists in the array. If such character does not exist,left
will be equal tolen(letters)
, meaning we need to wrap around to the start of the array. - To address the wrapping, we use modulus operation
left % len(letters)
. This ensures that ifleft
is beyond the last index, we return the first character in the array.
This approach efficiently narrows down the search space using the properties of sorted arrays and direct character comparisons, allowing us to find the answer in logarithmic time complexity, which is much faster than linearly scanning through the array.
Learn more about Binary Search patterns.
Solution Approach
The implementation uses a binary search algorithm, which is efficient for sorted arrays. The binary search algorithm repeatedly divides the search space in half, gradually narrowing down the section of the array where the answer could be, thereby reducing the number of comparisons that need to be made. Here's how the provided code works:
-
Initialization:
left
is set to 0 (the start of the array), andright
is set tolen(letters)
, which is one past the end of the array. -
Binary Search Loop:
- The condition
while left < right
ensures that the loop runs untilleft
andright
meet. mid = (left + right) >> 1
finds the middle index. The>> 1
is a bit shift to the right by one position, effectively dividing the sum by 2, but faster.
- The condition
-
Character Comparison:
if ord(letters[mid]) > ord(target)
: If the character at themid
index inletters
is lexicographically greater thantarget
, search to the left by updatingright = mid
.else:
statement means the mid character is not greater thantarget
, so we search to the right by updatingleft = mid + 1
.
-
Finding the Answer:
- After the loop exits,
left
is the index of the smallest character that is lexicographically greater than the target. If such a character doesn't exist,left
will be equal tolen(letters)
, indicating that we have searched the entire array without finding a character greater thantarget
.
- After the loop exits,
-
Return Statement:
return letters[left % len(letters)]
ensures we return the correct character:- If
left
is less thanlen(letters)
, it means we've found a character that is greater thantarget
, and we return that character. - If
left
is equal tolen(letters)
, the modulus operation causes it to wrap around to 0, returning the first character of the array, which is the required behavior when a greater character isn't found.
- If
In terms of data structures, only the input array letters
is used, and pointers (indices) are manipulated to traverse the array. No additional data structures are required for this algorithm, which keeps the space complexity low.
By implementing the binary search pattern, the time complexity is O(log n)
, where n
is the length of the input array. This is significantly more efficient than a linear search, which would have a time complexity of O(n)
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example:
Assume we have the sorted array letters = ["c", "f", "j"]
and the target character target = "a"
.
Now, let's walk through the binary search algorithm step by step:
-
Initialization: We set
left
to 0 andright
to 3 (the length ofletters
is 3). -
Binary Search Loop:
- Begin the loop since
left < right
(0 < 3). - Calculate
mid
which is(0 + 3) >> 1
, yielding 1.
- Begin the loop since
-
Character Comparison:
- At index 1, the character is
"f"
. We compare"f"
withtarget
which is"a"
.- Since
ord("f")
(102) is greater thanord("a")
(97), we setright
tomid
, which is now 1.
- Since
- At index 1, the character is
-
Continue Binary Search Loop:
- The loop condition still holds as
left < right
(0 < 1). - Calculate
mid
again, which is(0 + 1) >> 1
, yielding 0. - Compare character at index 0,
"c"
, withtarget
.- Since
ord("c")
(99) is greater thanord("a")
(97), we setright
tomid
, which is now 0.
- Since
- The loop condition still holds as
-
Loop Ends: The loop now terminates since
left
is not less thanright
(both are 0). -
Finding the Answer: The
left
is 0, andleft
is less thanlen(letters)
. -
Return Statement: We return
letters[left % len(letters)]
, which isletters[0]
. The character at index 0 is"c"
, so"c"
is returned as the smallest lexicographically greater character thantarget
.
In this example, the desired character is found within two iterations of the binary search loop, demonstrating the efficiency of the binary search algorithm in quickly locating the answer. The result, "c"
, is indeed the smallest character in the array that is lexicographically greater than the target "a"
. If the target
had been "k"
, the search would conclude with left
being 3, and the modulus operation would wrap around to return the first element in the array, "c"
.
Solution Implementation
1class Solution:
2 def nextGreatestLetter(self, letters: List[str], target: str) -> str:
3 # Initialize the left and right pointers to the start and end of the list respectively
4 left, right = 0, len(letters)
5
6 # Use binary search to find the position of the next greatest letter
7 while left < right:
8 # Find the middle index
9 mid = (left + right) // 2 # the '>> 1' is a bitwise operation equivalent to integer division by 2
10
11 # If the middle letter is greater than the target, look to the left half
12 if ord(letters[mid]) > ord(target):
13 right = mid
14 else:
15 # Otherwise, look to the right half
16 left = mid + 1
17
18 # The modulo operation ensures wrapping around if the target letter is greater than any letter in the list
19 return letters[left % len(letters)]
20
1class Solution {
2 public char nextGreatestLetter(char[] letters, char target) {
3 // Initialize the start and end pointers for binary search
4 int start = 0;
5 int end = letters.length;
6
7 // Perform binary search to find the smallest letter greater than target
8 while (start < end) {
9 // Calculate the mid point to split the search into halves
10 int mid = (start + end) >>> 1; // Using unsigned shift for safe mid calculation
11
12 // If the middle letter is greater than the target
13 if (letters[mid] > target) {
14 // We have a new possible candidate for next greatest letter (inclusive)
15 // and we need to search to the left of mid (exclusive)
16 end = mid;
17 } else {
18 // If mid letter is less than or equal to the target,
19 // we need to search to the right of mid (exclusive)
20 start = mid + 1;
21 }
22 }
23
24 // After the search, start is the least index where letters[index] > target,
25 // since the array is circular, we use modulo operator to wrap around the index
26 return letters[start % letters.length];
27 }
28}
29
1#include <vector>
2
3class Solution {
4public:
5 char nextGreatestLetter(vector<char>& letters, char target) {
6 // Initialize the pointers for the binary search.
7 int left = 0;
8 int right = letters.size();
9
10 // Perform binary search.
11 while (left < right) {
12 // Find the middle index.
13 int mid = left + (right - left) / 2; // Prevent potential overflow.
14
15 // If the middle letter is strictly greater than the target,
16 // move the right pointer to mid, as we want the smallest letter
17 // that is greater than the target.
18 if (letters[mid] > target) {
19 right = mid;
20 } else {
21 // If the middle letter is less than or equal to the target,
22 // move the left pointer past mid.
23 left = mid + 1;
24 }
25 }
26
27 // Since the list is circular, if we go past the end,
28 // we return the first element (modulo operation).
29 return letters[left % letters.size()];
30 }
31};
32
1function nextGreatestLetter(letters: string[], target: string): string {
2 // Initialize the number of elements in the 'letters' array.
3 const numLetters = letters.length;
4 // Set the initial search interval between the start and end of the array.
5 let leftIndex = 0;
6 let rightIndex = numLetters;
7
8 // Perform a binary search to find the smallest letter greater than the target.
9 while (leftIndex < rightIndex) {
10 // Calculate the middle index.
11 let middleIndex = leftIndex + ((rightIndex - leftIndex) >>> 1); // Same as Math.floor((left + right) / 2)
12
13 // If the letter at the middle index is greater than the target,
14 // it could be a potential answer, so move the right index to the middle.
15 // Otherwise, move the left index to one position after the middle.
16 if (letters[middleIndex] > target) {
17 rightIndex = middleIndex;
18 } else {
19 leftIndex = middleIndex + 1;
20 }
21 }
22
23 // Since the letters wrap around, we use the modulo operator (%) with the number of letters.
24 // This ensures we get a valid index if the 'leftIndex' goes beyond the array bounds.
25 return letters[leftIndex % numLetters];
26}
27
Time and Space Complexity
Time Complexity
The provided code performs a binary search on the sorted list of letters to find the smallest letter in the list that is larger than the target
character. The time complexity of binary search is O(log n)
, where n
is the number of elements in the input list. This is because, with each comparison, it effectively halves the size of the search space.
Initially, the search space is the entire letters
list. With each iteration of the loop, either the left
or right
index is adjusted to narrow down the search space. Since the search space is divided by two in every step, the maximum number of steps is proportional to log2(n)
. Therefore, the time complexity is O(log n)
.
Space Complexity
The space complexity of the code is O(1)
. This is because the space required does not scale with the size of the input list. The code uses a constant amount of extra space for variables such as left
, right
, and mid
. There are no additional data structures or recursive calls that would increase the space complexity. Regardless of the list size, the amount of memory required remains the same.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!