leetcode

commit 5ceb3e5ec284aa4980a9367f65c377f83370590c
parent 790ba8e85fa5957e4a23f18c5ceb546355423116
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 30 Jan 2026 17:13:50 -0700

744. find smallest letter greater than target

Diffstat:
M
find_smallest_letter.c
 | 
36
+++++++++++++-----------------------
A
find_smallest_letter.py
 | 
28
++++++++++++++++++++++++++++

2 files changed, 41 insertions(+), 23 deletions(-)
diff --git a/find_smallest_letter.c b/find_smallest_letter.c
@@ -1,36 +1,26 @@
 // 744. Find Smallest Letter Greater Than Target
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
 
-/* given an array of characters 'letters' that is sorted in non-decreasing
+/*
+ * 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'.
  */
 
-char nextGreatestLetter(char *letters, int letters_size, char target) {
-  int start = 0, end = letters_size - 1, mid;
-  while (start < end) {
-    mid = start + (end - start) / 2;
-    if (letters[mid] - target < 0)
-      start = mid + 1;
-    else if (letters[mid] - target > 0)
-      end = mid;
-    else
-      break;
-  }
-  while (mid < letters_size - 1 && letters[mid] <= target)
-    mid++;
-  char ans = letters[mid];
-  return letters[mid] <= target && mid == letters_size - 1 ? letters[0] : ans;
+char nextGreatestLetter(char *letters, int lettersSize, char target) {
+  for (int i = 0; i < lettersSize; i++)
+    if ((int)letters[i] > (int)target)
+      return letters[i];
+  return letters[0];
 }
 
 int main() {
-  char l1_2[] = {'c', 'f', 'j'};
+  char l1[] = {'c', 'f', 'j'};
+  char l2[] = {'c', 'f', 'j'};
   char l3[] = {'x', 'x', 'y', 'y'};
-  printf("%c\n", nextGreatestLetter(l1_2, 3, 'a')); // expect: c
-  printf("%c\n", nextGreatestLetter(l1_2, 3, 'c')); // expect: f
-  printf("%c\n", nextGreatestLetter(l1_2, 4, 'z')); // expect: x
+  printf("%c\n", nextGreatestLetter(l1, ARRAY_SIZE(l1), 'a')); // expect: c
+  printf("%c\n", nextGreatestLetter(l2, ARRAY_SIZE(l2), 'c')); // expect: f
+  printf("%c\n", nextGreatestLetter(l3, ARRAY_SIZE(l3), 'z')); // expect: x
 }
diff --git a/find_smallest_letter.py b/find_smallest_letter.py
@@ -0,0 +1,28 @@
+# 744. Find Smallest Letter Greater Than Target
+from bisect import bisect_right
+
+"""
+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'.
+"""
+
+
+class Solution(object):
+    def nextGreatestLetter(self, letters, target):
+        """
+        :type letters: List[str]
+        :type target: str
+        :rtype: str
+        """
+        pos = bisect_right(letters, target)
+        return letters[0] if pos == len(letters) else letters[pos]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.nextGreatestLetter(letters=["c", "f", "j"], target="a"))
+    print(obj.nextGreatestLetter(letters=["c", "f", "j"], target="c"))
+    print(obj.nextGreatestLetter(letters=["x", "x", "y", "y"], target="z"))