LeetCode: Find Smallest Letter Greater Than Target

Posted on January 15, 2018July 26, 2020 by braindenny

Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.

Examples:

Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

Note:

letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/find-smallest-letter-greater-than-target
// Basic Ideas: binary search
//
// How to check, drop and move?
//      If target == middle, check the right half
//            left = mid+1
//      If target > middle, check the right half
//            left = mid+1
//      If target < middle, check the left half
//            right = mid
//
// When to stop?
//      left < right: adjacent with two elements
//
// Corner cases:
//      No letter is greater than the target
//
// Complexity: Time O(log(n)), Space O(1)
func nextGreatestLetter(letters []byte, target byte) byte {
    // corner case: all letters smaller than the target
    if target >= letters[len(letters)-1] {
        return letters[0]
    }
    left, right := 0, len(letters)-1
    for left < right {
        mid := (right-left)/2 + left
        if letters[mid] <= target {
            left = mid+1
        } else {
            right = mid
        }
    }
    return letters[right]
}

Post Views: 3