This content originally appeared on DEV Community and was authored by Mostafa Shariare
Problem Statement
Given a sorted array of characters letters containing only lowercase English letters, and a target letter target, find the smallest element in the array that is greater than the target. Note that the letters wrap around, meaning that if the target is greater than or equal to the largest letter in the array, the search should wrap around and return the smallest letter in the array.
Example 1:
Input: letters = ['c', 'f', 'j'], target = 'a'
Output: 'c'
Example 2:
Input: letters = ['c', 'f', 'j'], target = 'c'
Output: 'f'
Example 3:
Input: letters = ['c', 'f', 'j'], target = 'd'
Output: 'f'
Observations
- The array is sorted, which makes binary search an ideal candidate for efficiently finding the result.
- If the target is smaller than or equal to the smallest letter in the array, we should return that smallest letter.
- If the target is larger than the largest letter in the array, we should return the first letter, because the array wraps around.
With these observations in mind, let's design our solution using binary search.
Approach
Binary search works by repeatedly dividing the search space in half. Here's how we'll apply it to this problem:
-
Initialize Variables: Start with two pointers,
startat the beginning (0) andendat the end (letters.length - 1) of the array. -
Binary Search:
- Calculate the middle index.
- If
letters[mid]is greater thantarget, move theendpointer tomid - 1. - If
letters[mid]is less than or equal totarget, move thestartpointer tomid + 1.
-
Wrap Around: Once the binary search completes, the smallest letter greater than the target will be at the
startindex. Ifstartexceeds the bounds of the array, use modulo operation to wrap around to the first letter in the array. -
Return Result: Return the letter at the
start % letters.lengthindex.
Java Code Implementation
public class Solution {
public static void main(String[] args) {
char[] letters = {'c', 'f', 'j'};
char target = 'a';
char ans = nextGreatestLetter(letters, target);
System.out.println(ans);
}
static char nextGreatestLetter(char[] letters, char target){
int start = 0;
int end = letters.length - 1;
while (start <= end){
int mid = start + (end - start) / 2;
if (target >= letters[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
// Since letters wrap around, we return letters[start % letters.length]
return letters[start % letters.length];
}
}
Explanation of the Code
-
Initialization:
- We start with
start = 0andend = letters.length - 1, which represent the beginning and end of the array.
- We start with
-
Binary Search Logic:
- The condition
if (target >= letters[mid])moves thestartpointer tomid + 1when the target is greater than or equal to the middle element. - Otherwise, we move the
endpointer tomid - 1.
- The condition
-
Handling Wrap Around:
- After the loop, the smallest letter greater than the target will be at the
startindex. Ifstartis beyond the array's last index, we usestart % letters.lengthto wrap around and access the first element.
- After the loop, the smallest letter greater than the target will be at the
Why Binary Search?
Binary search is ideal for this problem because:
- Efficiency: The time complexity of binary search is O(log n), which is much faster than a linear scan (O(n)) for large arrays.
- Sorted Array: The array is sorted, which is the prerequisite for applying binary search.
Edge Cases
- Target Larger than Any Letter: If the target is greater than or equal to the last letter in the array, the search wraps around and returns the first letter.
- Target Smaller than Smallest Letter: The binary search will find the smallest letter greater than the target.
This content originally appeared on DEV Community and was authored by Mostafa Shariare
Mostafa Shariare | Sciencx (2024-09-05T14:49:38+00:00) 🤖 Solving LeetCode Problem 744: Find the Smallest Letter Greater Than Target. Retrieved from https://www.scien.cx/2024/09/05/%f0%9f%a4%96-solving-leetcode-problem-744-find-the-smallest-letter-greater-than-target/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.