LC 744

Solution to LeetCode 744 Find Smallest Letter Greater Than Target.

LeetCode 744

Find Smallest Letter Greater Than Target (Easy). [link]

1. Linear Scan.

   Time complexity O(n), space complexity O(1).

class Solution(object):
    def nextGreatestLetter(self, letters, target):
        """
        :type letters: List[str]
        :type target: str
        :rtype: str
        """
        for char in letters:
            if char > target:
                return char
        return letters[0]

2. Binary Search.

   Find the smallest value in a sorted list such that letters[m] > target.

   Time complexity O(log n), space complexity O(1).

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

Note: There is a library in python for binary search: bisect.

• index = bisect.bisect_left(array, x, lo=0, hi=len(a))

  Find index of x in array such that the array is sorted. lo and hi are used to determine the range of index, but all the elements in the array are considered in default. index is the left position of x. index can be used to split the array into two parts.

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

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

  It assumes there is x in the array. index is the right position of x in the array.

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)]