DDSA Solutions

744. Find Smallest Letter Greater Than Target

EasyView on LeetCode
ArrayBinary Search
Time: O(log n)
Space: O(1)

Problem Overview

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

Intuition

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

Algorithm

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

Common Pitfalls

  • •Wraparound: if all letters = target, return letters[0] (circular).
744.cs
C#
// 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?

Related Problems