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 non-empty), 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.