Find Smallest Letter Greater Than Target - Leetcode Solution

Problem Statement:

Given a sorted array of lowercase letters, and a target letter, find the smallest letter in the array which is greater than the target.

Examples:

Input: letters = ["c", "f", "j"], target = "a" Output: "c"

Input: letters = ["c", "f", "j"], target = "c" Output: "f"

Input: letters = ["c", "f", "j"], target = "k" Output: "c"

Approach:

Since we are given a sorted array, we can use binary search to find the letter greater than the target. We can start by initializing left as 0 and right as n-1 where n is the length of the letters array. We can keep updated the mid of the array and compare it with the target. If it is less than the target, we can update left to mid+1, else we can update right to mid-1. We continue this until we find a letter greater than the target.

If we reach the end of the array, we can return the first element as the answer. Otherwise, we return the element which is greater than the target.

Solution:

The solution code in Python is given below:

class Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: n = len(letters) left, right = 0, n-1

    while left <= right:
        mid = left + (right - left) // 2
        if letters[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    
    if left == n:
        return letters[0]
    else:
        return letters[left]

Complexity Analysis:

• Time Complexity: The time complexity of the binary search algorithm used in the solution is O(log n) where n is the length of the input array. Therefore, the overall time complexity of the solution is O(log n).
• Space Complexity: The space complexity of the solution is O(1) since we are not using any extra space.

1