Find Smallest Letter Greater Than Target - LeetCode

• Sorted chars, possibly with duplicates
• Return the smallest char strictly greater than target, wrapping to letters[0] if none exists

Key idea

• Don't special-case ==. Fold it into the < branch
• Want strictly greater, so == means the answer is still to the right
• This is upper bound: left converges to the first element > target
• Duplicates are handled for free, no dedup needed

char nextGreatestLetter(vector<char>& letters, char target) {
    int left = 0, right = letters.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (letters[mid] <= target) {   // == and < both push right
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return letters[left % letters.size()];
}

Wrap-around

• If target is >= everything, left lands at letters.size()
• % letters.size() brings it back to 0

Bug I hit

• Original version returned letters[mid + 1] on an == match
• Fails on ["x","x","y","y"] with target "y", since mid + 1 is also y
• Tried to fix it by deduping the array first. Overcomplicated, the branch fold does it