Algorithm


Problem Name: 744. Find Smallest Letter Greater Than Target

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

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

Example 2:

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

Example 3:

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 <= 104
  • 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.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public char nextGreatestLetter(char[] letters, char target) {
    int start = 0;
    int end = letters.length - 1;
    int minIdx = Integer.MAX_VALUE;
    while (start  < = end) {
      int mid = (start + end) / 2;
      if (letters[mid] > target) {
        minIdx = mid;
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    return minIdx == Integer.MAX_VALUE ? letters[0] : letters[minIdx];
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
letters = ["c","f","j"], target = "a"

Output

x
+
cmd
"c"

#2 Code Example with Javascript Programming

Code - Javascript Programming


const nextGreatestLetter = function (letters, target) {
  const n = letters.length
  if (target < letters[0] || target >= letters[n - 1]) return letters[0]
  let left = 0
  let right = n - 1
  while (left < right) {
    let mid = left + ((right - left) >> 1)
    if (letters[mid] <= target) left = mid + 1
    else right = mid
  }
  return letters[right]
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
letters = ["c","f","j"], target = "a"

Output

x
+
cmd
"c"

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def nextGreatestLetter(self, letters, target):
        return letters[bisect.bisect(letters, target) % len(letters)]
Copy The Code & Try With Live Editor

Input

x
+
cmd
letters = ["c","f","j"], target = "c"

Output

x
+
cmd
"f"

#4 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0744_FindSmallestLetterGreaterThanTarget
    {
        public char NextGreatestLetter(char[] letters, char target)
        {
            int lo = 0, hi = letters.Length - 1;
            while (lo  < = hi)
            {
                var mid = lo + (hi - lo) / 2;
                if (letters[mid] <= target) lo = mid + 1;
                else hi = mid - 1;
            }

            return letters[lo % letters.Length];
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
letters = ["c","f","j"], target = "c"

Output

x
+
cmd
"f"
Advertisements

Demonstration


Previous
#743 Leetcode Network Delay Time Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#745 Leetcode Prefix and Suffix Search Solution in C, C++, Java, JavaScript, Python, C# Leetcode