744. Find Smallest Letter Greater Than Target

EasyView on LeetCode

Array Binary Search

Time: O(log n)

Space: O(1)

Intuition

Binary search for the smallest letter in the (circular) sorted array that is strictly greater than target.

Algorithm

1Binary search: find first letter > target.
2If no such letter exists, wrap around and return letters[0].

Common Pitfalls

•Wraparound: if all letters ≤ target, return letters[0] (circular).

744.cs

// Approach: Binary search for the first letter strictly greater than target; wrap around to letters[0] if none found.
// Time: O(log n) Space: O(1)

public class Solution
{
    public char NextGreatestLetter(char[] letters, char target)
    {
        int l = 0;
        int r = letters.Length;

        while (l < r)
        {
            int m = (l + r) / 2;
            if (letters[m] > target)
                r = m;
            else
                l = m + 1;
        }

        return letters[l % letters.Length];
    }
}

Was this solution helpful?