[LeetCode] Find Smallest Letter Greater Than Target

Problem: 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:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.

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 <= 10^4
• 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.

Approach: This is a simple binary search problem with following changes:

1. If letters[mid] <= target then obviously we will search on the right side so start becomes mid + 1.
2. Else we go to the left to see there is a smaller letter which is greater than target so end becomes mid.
3. In the end we return letters[end]

Implementation in C#:

    public char NextGreatestLetter(char[] letters, char target)

    {

        int start = 0, end = letters.Length - 1;

        if (target < letters[start] || target >= letters[end])

        {

            return letters[start];

        }

        while (start < end)

        {

            int mid = start + (end - start) / 2;

            if (letters[mid] <= target)

            {

                start = mid + 1;

            }

            else

            {

                end = mid;

            }

        }

        return letters[end];

    }

Complexity: O(log(n))