Difficulty: Easy | Acceptance: 59.10% | Paid: No Topics: Array, Binary Search
Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.
Note that the letters wrap around. For example, if target == ‘z’ and letters == [‘a’, ‘b’], the answer is ‘a’.
- Examples
- Constraints
- Linear Scan
- Binary Search
Examples
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 = ["x","x","y","y"], target = "z"
Output: "x"
Constraints
2 <= letters.length <= 10⁴
letters[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.
Linear Scan
Intuition Since the array is sorted, we can simply iterate through the array and return the first character that is greater than the target. If no such character exists, we return the first character (wrap around).
Steps
- Iterate through each character in the letters array
- If the current character is greater than the target, return it
- If we reach the end of the array without finding a greater character, return the first character
class Solution:
def nextGreatestLetter(self, letters: list[str], target: str) -> str:
for letter in letters:
if letter > target:
return letter
return letters[0]Complexity
- Time: O(n)
- Space: O(1)
- Notes: Simple but not optimal for large arrays
Binary Search
Intuition Since the array is sorted, we can use binary search to find the smallest character greater than the target in O(log n) time. We’re looking for the leftmost character that is strictly greater than the target.
Steps
- Initialize left = 0 and right = n - 1
- While left <= right, calculate mid = left + (right - left) / 2
- If letters[mid] <= target, move left to mid + 1 (we need a character strictly greater than target)
- Otherwise, move right to mid - 1
- After the loop, left will point to the smallest character greater than target
- If left is out of bounds (equal to n), return letters[0] (wrap around)
class Solution:
def nextGreatestLetter(self, letters: list[str], target: str) -> str:
left, right = 0, len(letters) - 1
while left <= right:
mid = left + (right - left) // 2
if letters[mid] <= target:
left = mid + 1
else:
right = mid - 1
return letters[left] if left < len(letters) else letters[0]Complexity
- Time: O(log n)
- Space: O(1)
- Notes: Optimal solution for large sorted arrays