# Find Smallest Letter Greater Than Target
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-smallest-letter-greater-than-target)
Canonical: https://scaleengineer.com/dsa/problems/find-smallest-letter-greater-than-target
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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 <= 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.

# Approaches
## Linear Scan
This approach involves a simple linear scan through the `letters` array. We iterate through each character and return the first one we find that is lexicographically greater than the `target`. If we reach the end of the array without finding such a character, we return the first element of the array as per the problem's wrap-around rule.
**Time:** O(N), where N is the length of the `letters` array. In the worst case, we may need to iterate through the entire array (e.g., if the target is greater than or equal to all but the last element, or all elements). · **Space:** O(1), as it uses a constant amount of extra space.
**Pros:** Simple to understand and implement.; Requires minimal code.
**Cons:** Does not leverage the sorted property of the array efficiently.; Has a linear time complexity, which is suboptimal for large inputs compared to a logarithmic approach.
### Explanation
The algorithm iterates through the `letters` array, which is sorted in non-decreasing order. For each character, it checks if it is greater than the `target`. Since the array is sorted, the first character that satisfies this condition is guaranteed to be the smallest character greater than the `target`. If the loop finishes, it means no character in `letters` is greater than `target`. The problem statement requires us to return the first character in `letters` in this scenario.

```java
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for (char c : letters) {
            if (c > target) {
                return c;
            }
        }
        return letters[0];
    }
}
```
### Algorithm
- 1. Iterate through the `letters` array from the first element to the last.
- 2. For each character `c` in the array, compare it with the `target` character.
- 3. If `c` is lexicographically greater than `target`, it is the smallest such character because the array is sorted. Return `c` immediately.
- 4. If the loop completes without finding any character greater than `target`, it implies all characters are less than or equal to `target`. In this case, return the first character of the array, `letters[0]`, to handle the wrap-around requirement.

## Binary Search
Since the input array `letters` is sorted, we can use a more efficient binary search algorithm. The goal is to find the smallest character that is strictly greater than the `target`. This is a classic application of binary search to find the 'upper bound' or the first element in a sorted range that is greater than a given value.
**Time:** O(log N), where N is the length of the `letters` array. Each step of the binary search halves the search space. · **Space:** O(1), as it only requires a few variables for the pointers, using constant extra space.
**Pros:** Highly efficient with O(log N) time complexity.; Optimal solution for the problem, especially for large arrays.
**Cons:** Slightly more complex to implement correctly than a linear scan.; Requires careful handling of boundary conditions to avoid off-by-one errors.
### Explanation
This approach leverages the sorted property of the array to achieve logarithmic time complexity. We define a search space with `low` and `high` pointers. In each step, we check the middle element. If it's greater than the `target`, we know it's a potential answer, and we try to find an even smaller one in the left half. If the middle element is less than or equal to the `target`, the answer must lie in the right half. This process continues until the search space is narrowed down to a single element. The final `low` index points to the insertion point for `target`, which is exactly the index of the smallest element greater than `target`. The wrap-around case (when no element is greater than `target`) is elegantly handled by using the modulo operator on the final index.

```java
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int low = 0;
        int high = n;

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        // If low == n, it means target is >= all elements.
        // The modulo operator handles the wrap-around.
        return letters[low % n];
    }
}
```
### Algorithm
- 1. Initialize two pointers, `low = 0` and `high = letters.length`.
- 2. While `low < high`, perform the binary search:
  - a. Calculate the middle index: `mid = low + (high - low) / 2`.
  - b. If `letters[mid]` is greater than `target`, it means the result could be `letters[mid]` or a character to its left. So, we update `high = mid`.
  - c. If `letters[mid]` is less than or equal to `target`, the result must be in the right half of the array. So, we update `low = mid + 1`.
- 3. The loop terminates when `low` and `high` converge. The `low` pointer now indicates the index of the smallest character greater than `target`.
- 4. If `low` is equal to `letters.length`, it means all characters were less than or equal to `target`. The wrap-around is handled by returning `letters[low % letters.length]`.

# Solutions
### Java

```java
class Solution { public char nextGreatestLetter ( char [] letters , char target ) { int left = 0 , right = letters . length ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( letters [ mid ] > target ) { right = mid ; } else { left = mid + 1 ; } } return letters [ left % letters . length ]; } }
```

### CPP

```cpp
class Solution { public: char nextGreatestLetter ( vector < char >& letters , char target ) { int left = 0 , right = letters . size (); while ( left < right ) { int mid = left + right >> 1 ; if ( letters [ mid ] > target ) { right = mid ; } else { left = mid + 1 ; } } return letters [ left % letters . size ()]; } };
```

### Python

```python
class Solution : def nextGreatestLetter ( self , letters : List [ str ], target : str ) -> str : left , right = 0 , len ( letters ) while left < right : mid = ( left + right ) >> 1 if ord ( letters [ mid ]) > ord ( target ): right = mid else : left = mid + 1 return letters [ left % len ( letters )]
```