Leetcode – Find Smallest Letter Greater Than Target Solution in Python

Spread the love

This article will discuss a specific problem from Leetcode known as “Find Smallest Letter Greater Than Target”, problem number 744. We will discuss the problem statement, a step-by-step solution, and Python code to solve it.

Problem Statement

The “Find Smallest Letter Greater Than Target” problem is described as follows:

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

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

Notes:

  • letters has a length in range [2, 10000].
  • letters consists of lowercase letters only, and contains at least two different letters.
  • target is a lowercase letter.

Approach to Solve the Problem

To solve this problem, we need to use a technique called binary search, which is a common algorithm for finding a target value within a sorted list. Binary search works by comparing the target value to the middle element of the list; if they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half until it is successful or the remaining half is empty.

In our case, we need to find the smallest letter which is greater than the target. So if the middle letter is less than or equal to the target, we search the second half of the list. Otherwise, we search the first half. If we can’t find such a letter (all letters in the list are not greater than the target), we return the first letter because the letters are circular.

Python Code

Here is the Python solution for this problem:

class Solution:
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        left, right = 0, len(letters) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if letters[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return letters[left % len(letters)]

In this solution, we define two pointers, left and right, to keep track of the search range. The middle letter is determined by the formula mid = left + (right - left) // 2. If the middle letter is less than or equal to the target, we update left to mid + 1. If the middle letter is greater than the target, we update right to mid - 1. We continue this process until left is greater than right. At this point, if we have found a letter that is greater than the target, left points to it. If not, left points to the first letter in the list. We return letters[left % len(letters)] to handle the circular case.

Time Complexity

The time complexity of this solution is O(log N), where N is the size of the input list. This is because with each comparison, we are reducing the problem size by half. The space complexity is O(1), as we are using a constant amount of space to store the pointers.

Testing the Solution

Let’s test our solution with the following example from Leetcode:

s = Solution()
print(s.nextGreatestLetter(["c", "f", "j"], "a"))
print(s.nextGreatestLetter(["c", "f", "j"], "c"))
print(s.nextGreatestLetter(["c", "f", "j"], "d"))
print(s.nextGreatestLetter(["c", "f", "j"], "g"))
print(s.nextGreatestLetter(["c", "f", "j"], "j"))
print(s.nextGreatestLetter(["c", "f", "j"], "k"))

The expected output is:

"c"
"f"
"f"
"j"
"c"
"c"

Conclusion

The “Find Smallest Letter Greater Than Target” problem on Leetcode is a classic problem to practice binary search. By understanding and implementing the binary search algorithm, you can efficiently solve this problem with a time complexity of O(log N). Always remember to test your solution with various test cases to ensure it works as expected in different scenarios.

Leave a Reply