Skip to main content

Binary Search

Find Smallest Letter Greater Than Target Solution in C++/Java/Python/JS

Problem Description:

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.
Illustration explaining the Problem Statement

Examples:

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

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

Constraints:

  • 2 <= letters.length <= 104
  • 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.

Find Smallest Letter Greater Than Target Problem

Given a sorted array containing letters and a letter target. We need to find the smallest letter greater than the target which lies in the letters array.
How would you approach this problem?

Brute Force Approach

Intuition:

Before we talk about the solution, let's get this very clear: What does lexicographically greater mean?

The meaning of lexicographically greater...

When we say a string (or letter) is lexicographically greater than another, it means the first string (or letter) appears later in the dictionary compared to the second one. Essentially, we are comparing the order of letters as they would appear in a dictionary or alphabetically.

This concept is very similar to how you compare words in a dictionary:

  • "apple" comes before "banana".
  • "cat" comes before "dog".

The comparison is based on the alphabetical order of the letters in the strings.

How to find less than and greater than:

Letter-by-letter comparison:

  • Compare each letter of two strings from left to right.
  • The first pair of letters where the strings differ will determine which one is lexicographically greater.
  • If a letter in one string is greater than the corresponding letter in the other string, the whole string is considered greater.
  • If all letters are the same, the string with the longer length is considered greater.

For single letters:

  • Each letter in the string is compared based on its position in the alphabet.
💡
Try Solving the Problem Yourself First !

Since the array is sorted, we can simply iterate over all the letters in the letters array and return the first letter that is greater than the target.

This works because the letters array is sorted. Initially, while iterating, we may arrive at the letters that are lexicographically less than or equal to the target. But then the first letter, which is greater than the target, will be our answer.

Find Smallest Letter Greater Than Target Solution

We will run a loop from 0 to the size of the letters array to iterate over the values in the letters array. We then keep checking if the letter at index i is greater than the target. The moment this check becomes true, we return letters[i]. As this is the smallest letter greater than the target.

If we find none,then we simply return letters[o] as guided by the problem statement.

Illustration of Find Smallest Letter Greater Than Target Brute Force Approach

Find Smallest Letter Greater Than Target example

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

Initialization:

  • n = letters.size(); → n = 6

Iteration 1 (i = 0):

  • letters[0] = 'a'
    • Check: 'a' > 'b' → false
    • Move to the next iteration

Iteration 2 (i = 1):

  • letters[1] = 'b'
    • Check: 'b' > 'b' → false
    • Move to the next iteration

Iteration 3 (i = 2):

  • letters[2] = 'c'
    • Check: 'c' > 'b' → true
    • Return 'c' and exit the function

Output: 'c'

Find Smallest Letter Greater Than Target Algorithm

Step 1: Initialize variables

  • Find the size of letters using letters.size() and store it in n.

Step 2: Iterate through the letters vector

  • Use a for loop to go through each character in the vector.
  • Check if the current character is greater than target.

Step 3: Return the first letter if no greater letter is found

  • If the loop completes without finding a greater letter, return letters[0].
Brute Force in All Languages
Find Smallest Letter Greater Than Target solution in C++ 
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        // Get the size of the letters array
        int n = letters.size();

        // Iterate through the letters array
        for (int i = 0; i < n; ++i) {
            // If the current letter is greater than the target, return it
            if (letters[i] > target) {
                return letters[i];
            }
        }
        // If no greater letter is found, return the first letter
        return letters[0];
    }
};

Find Smallest Letter Greater Than Target solution in java 
class Solution {
    // This function returns the smallest letter in the sorted array that is greater than the target
    public char nextGreatestLetter(char[] letters, char target) {
        // Get the size of the letters array
        int n = letters.length;

        // Iterate through the letters array
        for (int i = 0; i < n; i++) {
            // If the current letter is greater than the target, return it
            if (letters[i] > target) {
                return letters[i];
            }
        }
        // If no greater letter is found, return the first letter
        return letters[0];
    }
}

Find Smallest Letter Greater Than Target solution in python 
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        # Iterate through the letters list
        for letter in letters:
            # If the current letter is greater than the target, return it
            if letter > target:
                return letter
        # If no greater letter is found, return the first letter
        return letters[0]

Find Smallest Letter Greater Than Target solution in javascript 
/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function(letters, target) {
    // Iterate through the letters array
    for (let letter of letters) {
        // If the current letter is greater than the target, return it
        if (letter > target) {
            return letter;
        }
    }
    // If no greater letter is found, return the first letter
    return letters[0];
};

Find Smallest Letter Greater Than Target Complexity Analysis

Time Complexity: O(n)

The brute force solution iterates through the list of letters and returns the first letter greater than the target. If no such letter is found, it returns the first letter in the list.

Steps:

  1. Iterate through the list of letters → O(N)
  2. Check each letter against the target → O(1) per comparison
  3. Return the first letter greater than the target or wrap around → O(1) in best case but O(N) in worst case

Worst-Case Complexity:

  • If the target character is greater than or equal to all elements in the list, the loop will traverse the entire array.
  • Thus, the worst-case time complexity is O(N).

Space Complexity: O(1)

Auxiliary Space Complexity:
Auxiliary space refers to the extra space or temporary space used by an algorithm, not including the input size.

In the brute force solution:

  • We are not using any extra data structures like arrays or lists.
  • We are simply iterating over the letters list and performing constant-time operations (comparison and return).

Therefore, the auxiliary space complexity is O(1).

Total Space Complexity:
Total space refers to the total space used by the algorithm, including the space required for input storage.

In the brute force solution:

  • We need space to store the input letters list.
  • The space used by the input list letters is O(n), where n is the number of elements in the list.

Therefore, the total space complexity is O(n) because of the space required to store the input list.

Is the brute force solution feasible?

The answer to this question is YES. The brute force solution with complexity O(n) will easily pass all the test cases hence it can be counted as the desired Find Smallest Letter Greater Than Target leetcode solution.

This is because the constraint on n is only up to 104. This is well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.

Optimal Approach

Intuition:

The complexity of the brute force approach is O(n). This is because we used linear search to find the smallest letter greater than x or the target.

Now, think of what to do to optimise our solution. Can we make use of the sorted nature of the letters array to reduce the complexity... How?

💡
Try Solving the Problem Yourself First !

Suppose we chose the middle index of the letters array. Since the array is sorted, we can observe that all the letters after the middle index are lexicographically greater than or equal to the letter at the middle index. Also, all the letters before the middle index are lexicographically smaller or equal to the letter at the middle index.

Now, take a look at the target and the letter at the middle index (mid). The target can be greater than the letter at mid, or the target can be less than or equal to the letter at mid.

Now, let's see what we can conclude by considering each case.

Case 1: Target is lexicographically greater than the letter at mid.

If the target is lexicographically greater than the letter at the mid, then the letter at mid is not a valid answer because we're looking for the smallest letter that is greater than or equal to the target. Since all the letters to the left of mid are smaller than the middle letter, we can ignore them and focus on the right half of the array. The answer will be somewhere to the right of the middle index, as all the letters there will be greater than or equal to the letter at mid.

Example:

Given the sorted array:
letters = ['c', 'f', 'g', 'p', 'x']
Target = 'j'

  1. The middle index is mid = 2, so letters[mid] = 'g'.
  2. Since the target 'j' is greater than 'g', we know that all the letters from index 0 to mid are also less than 'j'.
  3. Thus, we search in the right half of the array (['p', 'x']) to find a letter greater than or equal to 'j'.
Illustration of Find Smallest Letter Greater Than Target Optimal Case 1

Case 2: Target is lexicographically smaller than or equal to the letter at mid.

If the target is lexicographically smaller than or equal to the letter at the middle index (mid), then the letter at mid is a valid candidate for the answer, but we still need to check if there might be a smaller valid letter that is still greater than or equal to the target. In this case, since the letter at mid is greater than or equal to the target, we continue searching in the left half of the array, as there might be an even smaller valid letter that meets the condition.

Example:

Given the sorted array:
letters = ['c', 'f', 'j', 'p', 'x']
Target = 'f'

  1. The middle index is mid = 2, so letters[mid] = 'j'.
  2. Since the target 'f' is smaller than 'j', we know that 'j' could be a valid answer as it can be the smallest letter greater than the target. But we are not sure if this is our answer, as an even smaller letter may exist to the left of mid, which is still greater than the target.
  3. Hence, we choose to search on the left (['c', 'f']) to check if we find the smallest letter greater than the target.
Illustration of Find Smallest Letter Greater Than Target Optimal Case 2

In this manner, we reduce our search space, narrowing it down to the smallest letter greater than the target.

First, we define the search space by using two pointers, low and high, which lie at 0 and n-1, respectively.

Then we select mid, which is the middle element of the search space.

If the letter at mid is greater than the target, then it may be our answer; we are not sure, so we will include this letter in our new search space. so we set high = mid.

If the letter at mid is smaller than or equal to the target, then the letter at mid and also all that precede this letter cannot be the answer, so we set low = mid+1.

In the end, we check if the letter at the low is greater than the target. If this check succeeds, we return the letter at low. Otherwise, we return the first element of the letters array as guided by the problem statement.

The algorithm which is used to solve this problem here is called Binary Search!.

💡
Binary Search in detail !
0:00
/0:57

Animation of Find Smallest Letter Greater Than Target Optimal Approach

Find Smallest Letter Greater Than Target example

Input: letters = ["a","b", "c","p","q","r"], target = "b"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c

Initial Setup:

  • letters = ["a", "b", "c", "p", "q", "r"]
  • target = "b"
  • low = 0
  • high = 5 (because the size of the list is 6, so n - 1 = 5)

Step-by-Step Dry Run:First iteration (low = 0, high = 5):

  1. Calculate mid:
    mid = (low + high) / 2 = (0 + 5) / 2 = 2
    So, mid = 2.
  2. Compare letters[mid] with target:
    letters[mid] = "c" and target = "b".
    Since "c" > "b", we update high to mid.
    Now, high = 2.

Second iteration (low = 0, high = 2):

  1. Calculate mid:
    mid = (low + high) / 2 = (0 + 2) / 2 = 1
    So, mid = 1.
  2. Compare letters[mid] with target:
    letters[mid] = "b" and target = "b".
    Since "b" <= "b", we update low to mid + 1.
    Now, low = 2.

Exit the loop:

At this point, low and high both point to index 2. The condition low < high no longer holds (low == high), so we exit the loop.

Final Check:

  1. Check letters[low] against target:
    letters[low] = "c" and `target = "b".
    Since "c" > "b", we return letters[low], which is "c".

Output:

  • The function will return "c" as the next greatest letter.

Find Smallest Letter Greater Than Target Algorithm

Step 1: Initialize Variables:

  • Create two pointers: low and high.
    • low should start at 0 (beginning of the list).
    • high should be initialized to n - 1 (end of the list), where n is the size of the letters list.

Step 2: Binary Search Loop:

  • Set the loop condition: While low < high, we will perform the binary search.
  • Inside the loop, calculate the middle index mid:
    mid = (low + high) / 2.
  • Check if the letter at mid is greater than target:
    • If letters[mid] > target, then:
    • The next greatest letter must be to the left of mid, so move the high pointer to mid.
    • Otherwise, if letters[mid] <= target:
    • The next greatest letter must be to the right of mid, so move the low pointer to mid + 1.

Step 3: Check the Final Position:

  • After the loop ends, you will have narrowed down the search space to a single element.
  • Check if letters[low] is greater than target:
    • If letters[low] > target, return letters[low] as the next greatest letter.
    • Otherwise, return letters[0] because the list wraps around, and the next greatest letter is the first one.

Step 4: Return the Result:

  • If no greater letter is found during the loop, the answer would be the first letter in the sorted list.
Optimal Approach in All Languages
Find Smallest Letter Greater Than Target solution in c++ 
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        // Get the size of the letters vector
        int n = letters.size(); 
        
        // Initialize low and high pointers
        int low = 0, high = n - 1;  

        // Binary search loop
        while (low < high) {
            // Calculate the middle index
            int mid = (low + high) / 2;  

            // If mid element is greater than target, adjust high pointer
            if (letters[mid] > target) {
                high = mid;
            }
            // Otherwise, adjust low pointer
            else {
                low = mid + 1;
            }
        }

        // Check if the element at low index is greater than target
        if (letters[low] > target) {
            return letters[low];  // Return the next greatest letter
        }
        
        // If no element greater than target, return the first element in the list
        return letters[0];
    }
};

Find Smallest Letter Greater Than Target solution in java 
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        // Initialize low and high pointers
        int low = 0, high = letters.length - 1;

        // Binary search loop
        while (low < high) {
            // Calculate the middle index
            int mid = (low + high) / 2;

            // If mid element is greater than target, adjust high pointer
            if (letters[mid] > target) {
                high = mid;
            }
            else {  // Otherwise, adjust low pointer
                low = mid + 1;
            }
        }

        // Check if the element at low index is greater than target
        if (letters[low] > target) {
            return letters[low];  // Return the next greatest letter
        }

        // If no element greater than target, return the first element in the list
        return letters[0];
    }
}

Find Smallest Letter Greater Than Target solution in python 
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        # Initialize low and high pointers
        low, high = 0, len(letters) - 1

        # Binary search loop
        while low < high:
            # Calculate the middle index
            mid = (low + high) // 2

            # If mid element is greater than target, adjust high pointer
            if letters[mid] > target:
                high = mid
            else:  # Otherwise, adjust low pointer
                low = mid + 1

        # Check if the element at low index is greater than target
        if letters[low] > target:
            return letters[low]  # Return the next greatest letter
        
        # If no element greater than target, return the first element in the list
        return letters[0]

Find Smallest Letter Greater Than Target solution in javascript 
/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function(letters, target) {
    // Initialize low and high pointers
    let low = 0, high = letters.length - 1;

    // Binary search loop
    while (low < high) {
        // Calculate the middle index
        let mid = Math.floor((low + high) / 2);

        // If mid element is greater than target, adjust high pointer
        if (letters[mid] > target) {
            high = mid;
        }
        else {  // Otherwise, adjust low pointer
            low = mid + 1;
        }
    }

    // Check if the element at low index is greater than target
    if (letters[low] > target) {
        return letters[low];  // Return the next greatest letter
    }

    // If no element greater than target, return the first element in the list
    return letters[0];
};

Find Smallest Letter Greater Than Target Complexity Analysis

Time Complexity: O(log n)

Initialization:

  • Initializing low, high, and mid takes constant time, i.e., O(1).

Binary Search:

  • The core part of the algorithm is the binary search loop.
  • In each iteration, we compute the middle index (mid = (low + high) / 2), and then either move high or low pointers to narrow down the search space.

Breaking It Down

  1. At the beginning: The search space has n elements.
  2. After 1st iteration: The search space is reduced to n/2.
  3. After 2nd iteration: The search space is n/4.
  4. After k iterations: The search space becomes n / 2k.

The search ends when only one element remains, which happens when: n/2k = 1

Taking log base 2 on both sides: k=log⁡2(n)

Thus, binary search runs in O(log n) time complexity.

Final Check:

  • After exiting the loop, we check the value at letters[low] to decide if it's the next greatest letter. This is a constant-time operation, i.e., O(1).

Space Complexity: O(1)

Auxiliary Space Complexity:
Auxiliary space refers to the extra space or temporary space used by the algorithm (excluding the space used by the input).

In this approach, we only use a few integer variables:

  • low: an integer that tracks the lower bound of the search space.
  • high: an integer that tracks the upper bound of the search space.
  • mid: an integer that tracks the middle index of the search space.
  • n: an integer that holds the size of the letters list (used for initialization).

These variables occupy a constant amount of space, irrespective of the size of the input.

Hence, Auxiliary Space Complexity is O(1)

Total Space Complexity:
Total space refers to the space used by the input along with any auxiliary space used by the algorithm.

  • The input letters is passed as an argument, which is the only variable that takes space proportional to the input size. O(n)
  • Since the algorithm does not use any additional data structures (like arrays or lists) that depend on the input size, the total space complexity is simply the space required for the input list plus the auxiliary space.

Total Space Complexity = O(n) + O(1) = O(n)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Count Elements With Strictly Smaller and Greater Elements 

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appear in nums.

2. Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.