Find Smallest Letter Greater Than Target Problem & Solution

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

See the find smallest letter greater than target problem on LeetCode.

C++ Solution

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  char nextGreatestLetter(vector<char>& letters, char target) {
    int low = 0;
    int high = letters.size() - 1;
    while (low < high) {
      int mid = low + (high - low) / 2;
      if (letters[mid] < target) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    
    if (letters[low] == target) {
      while (low < letters.size() && letters[low] == target) {
        ++low;
      }

      return letters[low < letters.size() ? low : 0];
    } else if (letters[low] > target) {
      return letters[low];
    } else {
      return letters[0];
    }
  }
};

Sample Search Queries

Many Paths. Follow Yours.

Languages

Technologies

Disciplines