LC 0744 [E] Find Smallest Letter Greater Than Target - ALawliet/algorithms GitHub Wiki

if the letters are sorted, then the smallest letter greater than target is just the first letter greater than target (rightmost binary search)

it can also be done using normal or leftmost binary search, but that is more confusing, so stick to rightmost

but instead of returning r - 1 in rightmost binary search, we just return l

The binary search loop while (lo < hi) terminates when lo becomes equal to hi, so l and r will be the same anyway

there is an edge case where the returned index can be n, so return 0 in this case because it "loops around"

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

class Solution:
    def nextGreatestLetter(self, A: List[str], T: str) -> str:
        n = len(A)
        L = 0
        R = n - 1
        ans = A[0]
        while L <= R:
            mid = (L + R) // 2
            if A[mid] > T:
                ans = A[mid]
                R = mid - 1
            else:
                L = mid + 1
        return ans
class Solution {
    public char nextGreatestLetter(char[] a, char x) {
        int n = a.length;

        //hi starts at 'n' rather than the usual 'n - 1'. 
        //It is because the terminal condition is 'lo < hi' and if hi starts from 'n - 1', 
        //we can never consider value at index 'n - 1'
        int lo = 0, hi = n;

        //Terminal condition is 'lo < hi', to avoid infinite loop when target is smaller than the first element
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] > x)     hi = mid;
            else    lo = mid + 1;                 //a[mid] <= x
        }
 
        //Because lo can end up pointing to index 'n', in which case we return the first element
        return a[lo % n];
    }
}
class Solution:
    def nextGreatestLetter(self, A: List[str], T: str) -> str:
        n = len(A)
        l = 0
        r = n - 1
        
        while l <= r:
            m = (l + r) // 2
            if A[m] == T:
                l = m + 1
            elif A[m] < T:
                l = m + 1
            elif A[m] > T:
                r = m - 1
                
        return A[0] if l == len(A) else A[l]
class Solution(object):
    def nextGreatestLetter(self, A, T):
        l = bisect.bisect(A, T)
        return A[l % len(A)]