LeetCode in Kotlin
744. Find Smallest Letter Greater Than Target
Easy
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 <= 104letters[i]is a lowercase English letter.lettersis sorted in non-decreasing order.letterscontains at least two different characters.targetis a lowercase English letter.
Solution
class Solution {
fun nextGreatestLetter(letters: CharArray, target: Char): Char {
var start = 0
var end = letters.size - 1
// If target is greater than last element return first element of the array.
if (letters[letters.size - 1] <= target) {
return letters[start]
}
while (start < end) {
val mid = start + (end - start) / 2
if (letters[mid] <= target) {
start = mid + 1
} else {
end = mid
}
}
return letters[start]
}
}