# 09.06.2023 [744. Find Smallest Letter Greater Than Target]

09.06.2023

744. Find Smallest Letter Greater Than Target easy
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/240

Problem TLDR

Lowest char greater than target.

Intuition

In a sorted array, we can use the Binary Search.

Approach

For more robust code:

• use inclusive lo and hi

• check the last condition lo == hi

• always move lo or hi

• always write a good result res = ...

• safely compute mid

Complexity

• Time complexity:
  O(log(n))

• Space complexity:
  O(1)

Code

fun nextGreatestLetter(letters: CharArray, target: Char): Char {
    var res = letters[0]
    var lo = 0
    var hi = letters.lastIndex
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2
        if (letters[mid] > target) {
            hi = mid - 1
            res = letters[mid]
        } else lo = mid + 1
    }
    return res
}