## 744. Find Smallest Letter Greater Than Target

Given a list of sorted characters `letters` containing only lowercase letters, and given a target letter `target`, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is `target = 'z'` and `letters = ['a', 'b']`, the answer is `'a'`.

Examples:

```Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"
```

Note:

1. `letters` has a length in range `[2, 10000]`.
2. `letters` consists of lowercase letters, and contains at least 2 unique letters.
3. `target` is a lowercase letter.

b'
\n\n

#### Approach #1: Record Letters Seen [Accepted]

\n

Intuition and Algorithm

\n

Let\'s scan through `letters` and record if we see a letter or not. We could do this with an array of size 26, or with a Set structure.

\n

Then, for every next letter (starting with the letter that is one greater than the target), let\'s check if we\'ve seen it. If we have, it must be the answer.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `letters`. We scan every element of the array.

\n
• \n
• \n

Space Complexity: , the maximum size of `seen`.

\n
• \n
\n
\n

#### Approach #2: Linear Scan [Accepted]

\n

Intuition and Algorithm

\n

Since `letters` are sorted, if we see something larger when scanning form left to right, it must be the answer. Otherwise, (since `letters` is non-empty), the answer is `letters`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `letters`. We scan every element of the array.

\n
• \n
• \n

Space Complexity: , as we maintain only pointers.

\n
• \n
\n
\n

#### Approach #3: Binary Search [Accepted]

\n

Intuition and Algorithm

\n

Like in Approach #2, we want to find something larger than target in a sorted array. This is ideal for a binary search: Let\'s find the rightmost position to insert `target` into `letters` so that it remains sorted.

\n

Our binary search (a typical one) proceeds in a number of rounds. At each round, let\'s maintain the loop invariant that the answer must be in the interval `[lo, hi]`. Let `mi = (lo + hi) / 2`. If `letters[mi] <= target`, then we must insert it in the interval `[mi + 1, hi]`. Otherwise, we must insert it in the interval `[lo, mi]`.

\n

At the end, if our insertion position says to insert `target` into the last position `letters.length`, we return `letters` instead. This is what the modulo operation does.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `letters`. We peek only at elements in the array.

\n
• \n
• \n

Space Complexity: , as we maintain only pointers.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'