744. Find Smallest Letter Greater Than Target

Problem

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:

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

Problem Summary

Given a sorted array letters containing only lowercase letters and a target letter target, find the smallest letter in the sorted array that is greater than the target letter.

The order of letters in the array is circular. For example, if the target letter is target = 'z' and the sorted array is letters = ['a', 'b'], then the answer returned is 'a'.

Note:

1. The length of letters is in the range [2, 10000].
2. letters consists only of lowercase letters and contains at least two different letters.
3. The target letter target is a lowercase letter.

Solution Approach

• Given a byte array, find the first letter after target in this byte array. The array is circular.
• This problem is also a binary search problem. First search for target in the array; if found, take the letter after this letter. If not found, take the letter at the low index. Note that the array is circular, so the final result needs to take the index modulo the length of the array.

Code

package leetcode

func nextGreatestLetter(letters []byte, target byte) byte {
	low, high := 0, len(letters)-1
	for low <= high {
		mid := low + (high-low)>>1
		if letters[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	find := letters[low%len(letters)]
	if find <= target {
		return letters[0]
	}
	return find
}