algoadvance

Leetcode 744. Find Smallest Letter Greater Than Target

Problem Statement

Leetcode 744: Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and a target character target, the task is to find the smallest character in the list that is larger than the given target character. If no such character exists, you should return the first character in the list.

Example:

• Input: letters = ["c","f","j"], target = "a"
  • Output: "c"
• Input: letters = ["c","f","j"], target = "c"
  • Output: "f"
• Input: letters = ["x","x","y","y"], target = "z"
  • Output: "x"

Constraints:

• 2 <= letters.length <= 10^4
• letters consists of lowercase English letters.
• letters is sorted in non-decreasing order.
• letters contains at least two different characters.

Clarifying Questions

1. Q: Can the list letters contain duplicate letters?
   • A: Yes, the list can contain duplicates, but the list is always sorted and contains at least two different characters.
2. Q: What should be returned if all the characters in the list are less than or equal to the target?
   • A: Return the first character in the list.

Strategy

To find the smallest character greater than the target, we can use a binary search approach due to the following reasons:

1. The list letters is sorted, which makes binary search an optimal choice.
2. Binary search will allow us to perform the search in logarithmic time.

Here is the plan:

1. Initialize low to 0 and high to the length of the list.
2. Perform binary search:
   • Compute the middle index mid.
   • If letters[mid] is less than or equal to target, move the low pointer to mid + 1.
   • If letters[mid] is greater than target, move the high pointer to mid.
3. Once the loop ends, the low pointer should be at the smallest character that is greater than the target. If low reaches the end of the list, wrap around to the first character.

Code

public class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int low = 0;
        int high = letters.length;
        
        // Perform binary search
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        // Since the array is circular
        return letters[low % letters.length];
    }
}

Time Complexity

The time complexity of this approach is (O(\log n)) due to the binary search algorithm, where (n) is the length of the letters array.

Space Complexity

The space complexity is (O(1)) as we are using only a fixed amount of additional space regardless of the input size.

This approach ensures that we efficiently and correctly determine the smallest character greater than the given target in the sorted list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?