LeetCode 0744. Find Smallest Letter Greater Than Target Solution in Java, C++, Python & More | Explanation + Code

Description

You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

 

Example 1:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'.

Example 2:

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.

Example 3:

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

 

Constraints:

• 2 <= letters.length <= 104
• 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.

Solutions

Solution 1: Binary Search

Since letters is sorted in non-decreasing order, we can use binary search to find the smallest character that is larger than target.

We define the left boundary of the binary search as l = 0, and the right boundary as r = n. For each binary search, we calculate the middle position mid = (l + r) / 2. If letters[mid] > target, it means we need to continue searching in the left half, so we set r = mid. Otherwise, we need to continue searching in the right half, so we set l = mid + 1.

Finally, we return letters[l \mod n].

The time complexity is O(log n), where n is the length of letters. The space complexity is O(1).

PythonJavaC++GoTypeScriptRustPHP

class Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: i = bisect_right(letters, ord(target), key=lambda c: ord(c)) return letters[i % len(letters)](code-box)

class Solution { public char nextGreatestLetter(char[] letters, char target) { int i = Arrays.binarySearch(letters, (char) (target + 1)); i = i < 0 ? -i - 1 : i; return letters[i % letters.length]; } }(code-box)

class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { int i = upper_bound(letters.begin(), letters.end(), target) - letters.begin(); return letters[i % letters.size()]; } };(code-box)

func nextGreatestLetter(letters []byte, target byte) byte { i := sort.Search(len(letters), func(i int) bool { return letters[i] > target }) return letters[i%len(letters)] }(code-box)

function nextGreatestLetter(letters: string[], target: string): string { const idx = _.sortedIndex(letters, target + '\0'); return letters[idx % letters.length]; }(code-box)

impl Solution { pub fn next_greatest_letter(letters: Vec<char>, target: char) -> char { let mut l = 0; let mut r = letters.len(); while l < r { let mid = l + (r - l) / 2; if letters[mid] > target { r = mid; } else { l = mid + 1; } } letters[l % letters.len()] } }(code-box)

class Solution { /** * @param String[] $letters * @param String $target * @return String */ function nextGreatestLetter($letters, $target) { $l = 0; $r = count($letters); while ($l < $r) { $mid = $l + $r >> 1; if ($letters[$mid] > $target) { $r = $mid; } else { $l = $mid + 1; } } return $letters[$l % count($letters)]; } }(code-box)