### View *Find Smallest Letter Greater Than Target* on LeetCode

## Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(log n) - Binary search is the main algorithm used in the solution, resulting in the O(log n) time complexity.

**Space Complexity**

O(1) - The number of created variables is independent of the input, resulting in the O(1) space complexity.

**Runtime Beats**

98.83% of other submissions

## Explanation

The function first checks if there are letters within the input lists which meet our criteria; if none do, then return the first letter, as specified in the problem.

Initialize the left and right pointers and then loop until `l`

is greater than `r.`

In this modification of binary search, we include where `l`

== `r`

because of the specific input domain.

Create and initialize `m`

to the middle of `l`

and `r,`

and then check conditionals:

`if target >= letters[m]:`

If the target is greater than or equal to the current letter, then there will be smaller letters to the left of the list`else:`

If the target is less than the current letter, there will be larger letters to the right of the list

Once the while loop exists, the left pointer will remain at the next greatest letter, so we return the letter at that index.

## Algorithm Used

**Binary Search -** A search algorithm that repeatedly halves the search interval until the target variable is found at the middle index.

**Visual Examples**

Binary search being performed on an array that contains the target, click to view

Binary search being performed on an array that does **not** contain the target, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
if target >= letters[-1] or target < letters[0]:
return letters[0]
l = 0
r = len(letters) - 1
while l <= r:
m = (l+r)//2
if target >= letters[m]:
l = m+1
else:
r = m-1
return letters[l]