744. Find Smallest Letter Greater Than Target

Approach 1: Binary Search using bisect

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        index = bisect.bisect(letters, target)
        return letters[index % len(letters)]

As the documentation of bisect reads, bisect.bisect returns an insertion point which comes after (to the right of) any existing entries of target in letters

bisect.bisect(a, x, lo=0, hi=len(a))

Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.

The returned insertion point i partitions the array a into two halves so that all(val <= x for valin a[lo:i]) for the left side and all(val > x for val in a[i:hi]) for the right side.

This algorithm comes in at 100% percentile runtime

Time Complexity: O(logN), because it uses a basic bisection

Space Complexity: O(1)