Find Smallest Letter Greater Than Target

Leetcode Daily Challenge (9th June, 2023)

9 June, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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

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:-

java

python

leetcode

dsa