Approach #1: Record Letters Seen [Accepted]
Intuition and Algorithm
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.
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.
Complexity Analysis

Time Complexity: , where is the length of
letters
. We scan every element of the array. 
Space Complexity: , the maximum size of
seen
.
Approach #2: Linear Scan [Accepted]
Intuition and Algorithm
Since letters
are sorted, if we see something larger when scanning form left to right, it must be the answer. Otherwise, (since letters
is nonempty), the answer is letters[0]
.
Complexity Analysis

Time Complexity: , where is the length of
letters
. We scan every element of the array. 
Space Complexity: , as we maintain only pointers.
Approach #3: Binary Search [Accepted]
Intuition and Algorithm
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.
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]
.
At the end, if our insertion position says to insert target
into the last position letters.length
, we return letters[0]
instead. This is what the modulo operation does.
Complexity Analysis

Time Complexity: , where is the length of
letters
. We peek only at elements in the array. 
Space Complexity: , as we maintain only pointers.
Analysis written by: @awice.