LeetCode 744. Find Smallest Letter Greater Than Target

Description

https://leetcode.com/problems/find-smallest-letter-greater-than-target/

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

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 = "d"
Output: "f"

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

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

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

Note:

  1. letters has a length in range [2, 10000].
  2. letters consists of lowercase letters, and contains at least 2 unique letters.
  3. target is a lowercase letter.

Explanation

Just check from where the element in the list becomes greater than the target. If the target is greater than the last element in the list, just return the first element of the list.

Python Solution

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
                
        for letter in letters:
            if letter > target:
                return letter
            
        if target >= letters[-1]:
            return letters[0]
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *