Find Smallest Letter Greater Than Target

Problem Statement:-

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.

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

Problem Explanation with examples:-

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<sup>4</sup>

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

Intuition:-

• Simply iterate through the list and find the first element greater than the target.

• Can also use binary search to find the first element greater than the target as the list is sorted.

Solution:-

• Create an iterator variable i = 0

• Run a while loop till i < len(letters) and letters[i] <= target. Increment i by 1 in each iteration.

• If i >= len(letters), return letters[0] as there is no element greater than the target in the list.

• Else return letters[i] as it is the first element greater than the target.

Code:-

JAVA Solution

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int i = 0;
        while (i < letters.length && letters[i] <= target) {
            i++;
        }
        if (i >= letters.length) {
            return letters[0];
        }
        return letters[i];
    }
}

Python Solution

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        i = 0
        while i < len(letters) and letters[i] <= target:
            i += 1
        if i >= len(letters):
            return letters[0]
        return letters[i]

Complexity Analysis:-

TIME:-

The time complexity is O(n), where n is the length of the letters array. In the worst case, the while loop will iterate through all the elements in the array.

SPACE:-

The space complexity is O(1) as the code only uses a constant amount of additional space to store the loop counter and return the result, regardless of the size of the input array.

References:-

• Loops

Connect with me:-

• Twitter

• Github

• LinkedIn