Find the Smallest Letter Greater Than the Target

Prerequsites : 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array , 🛖Ceiling(Upper Bound)

Question

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

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

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].

Intuition

1. The array is sorted, providing us with our first clue that we can solve this problem using binary search.
1. All the values that are greater (lexicographically) than the target will be on the right side of the target. All the values less than and equal to the target will be on the left side.
2. This gives us our two halves.
1. when we are in the upper half; get rid of all elements to the right, when in the lower half; get rid of all elements to the left.
3. We hop between each half-chopping element and reduce the range. The last element we will chop from the upper half will be the smallest character greater/after than target. We keep updating the possible value and return the most up-to-date.
2. We end up returning the smallest element after the target in the upper half, as we did in 🛖Ceiling(Upper Bound)
3. There are a few things slightly different from 🛖Ceiling(Upper Bound)
1. Alphabet instead of numbers. ( >(greater than) sign still works for alphabets)
2. The smallest element in letters strictly greater than the target
1. Previously we included the target as a potential ceil.
3. If such a character does not exist, return the first character in letters.
1. If the left and right pointers overlap without finding the ceil we return the first character.

class Solution:

    def ceil(self,nums,target):

        left, right = 0, len(nums) - 1
        ceil = -1

        while left <= right:

            mid = left + (right - left) // 2
						
            #True
                # Possible Value
            if nums[mid] >= target:
                ceil = mid
                right = mid - 1
						
						# False
            else: # target > nums[mid]
                left = mid + 1

				# if not found will return -1  
        return ceil

class Solution:

    def nextGreatestLetter(self, letters, target):
        
        left,right = 0,len(letters)-1
        res = "@" # change
        
        while left <= right:
            
            mid = left + (right-left)//2
            
            #True
                # Possible Value
            if letters[mid] > target: #change 
                res = letters[mid]
                right = mid -1
            
            # False
            else: #letters[mid] <= target:
                left = mid + 1
                
        # if not found will return the first letter
        return res if res != "@" else letters[0] #change

SandBox PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition