744. Find Smallest Letter Greater Than Target

DifficultyEasy

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 \(\textit{letters}\) is sorted in non-decreasing order, we can use binary search to find the smallest character that is larger than \(\textit{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 \(\textit{mid} = (l + r) / 2\). If \(\textit{letters}[\textit{mid}] > \textit{target}\), it means we need to continue searching in the left half, so we set \(r = \textit{mid}\). Otherwise, we need to continue searching in the right half, so we set \(l = \textit{mid} + 1\).

Finally, we return \(\textit{letters}[l \mod n]\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\), where \(n\) is the length of \(\textit{letters}\).

1
2
3
4

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)]

1
2
3
4
5
6
7

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];
    }
}

1
2
3
4
5
6
7

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()];
    }
};

1
2
3
4

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)]
}

1
2
3
4

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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()]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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)];
    }
}

Comments