Find Smallest Letter Greater Than Target

Easy

Google

3 views

Topics:

ArraysBinary Search

You are 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

2 <= letters.length <= 10⁴
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

Try coding it in LeetCode

Find Smallest Letter Greater Than Target

Easy

Google

3 views

Topics:

ArraysBinary Search

You are 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

2 <= letters.length <= 10⁴
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of characters in the letters array and target? Are they all lowercase English letters?
What should I return if the target is greater than or equal to the largest letter in the letters array? Should I wrap around to the smallest letter?
Can the letters array be empty?
Is the letters array guaranteed to be sorted in non-decreasing order?
Are there duplicate letters in the letters array?

Brute Force Solution

Approach

The problem requires us to find the smallest letter in a list that is bigger than a specific target letter. A brute-force approach simply checks each letter in the list one by one against the target letter until it finds the right one.

Here's how the algorithm would work step-by-step:

Look at the first letter in the list.
Compare it to the target letter. Is it bigger?
If it is, we've found our answer, so stop and return it.
If it's not, move on to the next letter in the list.
Keep doing this until you find a letter that is bigger than the target letter.
If you reach the end of the list and haven't found a bigger letter, start again from the beginning of the list. The first letter is then the answer.

Code Implementation

def find_smallest_letter_greater_than_target_brute_force(letters, target):

    # Iterate through each letter in the list.
    for letter in letters:

        # Check if the current letter is greater than the target.
        if letter > target:
            return letter

        # If we reach here, no letter was greater. Reset and start from beginning.

    return letters[0]

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the list of letters once. In the worst-case scenario, it goes through all n letters in the list and doesn't find a letter greater than the target. It then loops back to the beginning and returns the first letter. Therefore, the time complexity is directly proportional to the number of letters, n, in the input list. Hence the time complexity simplifies to O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input list of letters, comparing each to the target. It doesn't create any additional data structures like lists, arrays, or hash maps. The algorithm only uses a constant amount of extra memory to store variables related to the current letter being compared. Therefore, the auxiliary space complexity is O(1) as it doesn't depend on the size of the input (N).

Optimal Solution

Approach

The fastest way to find the right letter is to use a method similar to looking up a word in a dictionary. We can quickly narrow down the possibilities by repeatedly dividing the search area in half. This avoids checking each letter individually.

Here's how the algorithm would work step-by-step:

Start by looking at the letter in the middle of the provided list.
If the middle letter is greater than the target letter, then we know the answer must be in the first half of the list. Discard the second half.
If the middle letter is not greater than the target letter, then the answer must be in the second half of the list. Discard the first half.
Repeat the process of checking the middle letter of the remaining portion until only one letter remains.
If the list becomes empty during the process, it means that the target letter is greater than or equal to all letters in the list, in that case, return the first letter of the list as it wraps around.
The remaining letter is the smallest letter greater than the target.

Code Implementation

def find_smallest_letter_greater_than_target(letters, target):
    left_index = 0
    right_index = len(letters) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_letter = letters[middle_index]

        # Narrow search to the left half if middle letter is greater
        if middle_letter > target:

            right_index = middle_index - 1

        # Otherwise, narrow search to the right half
        else:

            left_index = middle_index + 1

    # Wraparound: target is greater than or equal to all letters.
    if left_index == len(letters):
        return letters[0]
    # Return the smallest letter greater than target
    else:
        return letters[left_index]

Big(O) Analysis

Time Complexity

O(log n) – The algorithm employs a binary search strategy. In each iteration, the search space is halved. The number of iterations required to find the target letter is therefore logarithmic with respect to the input size 'n', where 'n' represents the number of letters in the sorted list. Hence, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm described primarily uses a binary search approach. It only stores a few variables to keep track of the current search range (e.g., start, end, middle index). The number of these variables remains constant regardless of the input list's size (N), implying no auxiliary space that scales with the input. Therefore, the algorithm uses constant auxiliary space.

Edge Cases

Case	How to Handle
Empty letters array	Return the default value or throw an exception as there is no smallest greater letter.
Target is greater than or equal to all letters in letters array	Return the first letter in the array, as it wraps around.
Letters array contains only one letter	Return the single letter if it is greater than target, or return the same letter if it is not.
Letters array contains duplicate letters	The algorithm should still return the smallest greater letter correctly, ignoring duplicate positions.
Target is less than all letters in letters array	Return the first element of the array since it is the smallest greater letter.
Letters array contains all identical letters equal to the target	Return the first letter in the array as that will be smallest greater letter due to wraparound.
Letters array is very large (potential memory issues)	Binary search should be efficient enough to handle very large array sizes without memory issues.
Target is the largest possible character value	The first element should be returned due to the wraparound behavior.