<filename>dsa/patterns/binary_search/next_letter.py
"""
Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’.

Assume the given array is a circular list, which means that the last letter is assumed to be connected with the first letter. 
This also means that the smallest letter in the given array is greater than the last letter of the array and is also the first 
letter of the array.

Write a function to return the next letter of the given ‘key’.

Example 1:
Input: ['a', 'c', 'f', 'h'], key = 'f'
Output: 'h'
Explanation: The smallest letter greater than 'f' is 'h' in the given array.

Example 2:
Input: ['a', 'c', 'f', 'h'], key = 'b'
Output: 'c'
Explanation: The smallest letter greater than 'b' is 'c'.

Example 3:
Input: ['a', 'c', 'f', 'h'], key = 'm'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'm' is 'a'.

Example 4:
Input: ['a', 'c', 'f', 'h'], key = 'h'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'h' is 'a'.

Idea: 
-> Take care of the out of bound cases then take care of inside.
-> This is just like finding ceil but with diffence in case where letters[mid] == key
"""

def next_letter(letters, key):
    left, right = 0, len(letters)-1

    while left <= right:
        mid = (left + right) >> 1
        if letters[mid] <= key:
            left = mid + 1
        else:
            right = mid - 1
    return letters[left % len(letters)]

# def next_letter(letters, key):
#     if key < letters[0] or letters[-1] <= key:
#         return letters[0]

#     left, right = 0, len(letters)-1

#     while left < right:
#         mid = (left + right) >> 1
#         if letters[mid] <= key:
#             left = mid + 1
#         else:
#             right = mid 
#     return letters[left]

if __name__ == "__main__":
    print(next_letter(['a', 'c', 'f', 'h'], key = 'f'))
    print(next_letter(['a', 'c', 'f', 'h'], key = 'b'))
    print(next_letter(['a', 'c', 'f', 'h'], key = 'm'))
    print(next_letter(['a', 'c', 'f', 'h'], key = 'h'))
    print(next_letter(["c", "f", "j"], key='a'))
<filename>dsa/patterns/binary_search/next_letter.py
"""
Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’.

Assume the given array is a circular list, which means that the last letter is assumed to be connected with the first letter. 
This also means that the smallest letter in the given array is greater than the last letter of the array and is also the first 
letter of the array.

Write a function to return the next letter of the given ‘key’.

Example 1:
Input: ['a', 'c', 'f', 'h'], key = 'f'
Output: 'h'
Explanation: The smallest letter greater than 'f' is 'h' in the given array.

Example 2:
Input: ['a', 'c', 'f', 'h'], key = 'b'
Output: 'c'
Explanation: The smallest letter greater than 'b' is 'c'.

Example 3:
Input: ['a', 'c', 'f', 'h'], key = 'm'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'm' is 'a'.

Example 4:
Input: ['a', 'c', 'f', 'h'], key = 'h'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'h' is 'a'.

Idea: 
-> Take care of the out of bound cases then take care of inside.
-> This is just like finding ceil but with diffence in case where letters[mid] == key
"""

def next_letter(letters, key):
    left, right = 0, len(letters)-1

    while left <= right:
        mid = (left + right) >> 1
        if letters[mid] <= key:
            left = mid + 1
        else:
            right = mid - 1
    return letters[left % len(letters)]

# def next_letter(letters, key):
#     if key < letters[0] or letters[-1] <= key:
#         return letters[0]

#     left, right = 0, len(letters)-1

#     while left < right:
#         mid = (left + right) >> 1
#         if letters[mid] <= key:
#             left = mid + 1
#         else:
#             right = mid 
#     return letters[left]

if __name__ == "__main__":
    print(next_letter(['a', 'c', 'f', 'h'], key = 'f'))
    print(next_letter(['a', 'c', 'f', 'h'], key = 'b'))
    print(next_letter(['a', 'c', 'f', 'h'], key = 'm'))
    print(next_letter(['a', 'c', 'f', 'h'], key = 'h'))
    print(next_letter(["c", "f", "j"], key='a'))
Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’.  Assume the given array is a circular list, which means that the last letter is assumed to be connected with the first letter.  This also means that the smallest letter in the given array is greater than the last letter of the array and is also the first  letter of the array.  Write a function to return the next letter of the given ‘key’.  Example 1: Input: ['a', 'c', 'f', 'h'], key = 'f' Output: 'h' Explanation: The smallest letter greater than 'f' is 'h' in the given array.  Example 2: Input: ['a', 'c', 'f', 'h'], key = 'b' Output: 'c' Explanation: The smallest letter greater than 'b' is 'c'.  Example 3: Input: ['a', 'c', 'f', 'h'], key = 'm' Output: 'a' Explanation: As the array is assumed to be circular, the smallest letter greater than 'm' is 'a'.  Example 4: Input: ['a', 'c', 'f', 'h'], key = 'h' Output: 'a' Explanation: As the array is assumed to be circular, the smallest letter greater than 'h' is 'a'.  Idea:  -> Take care of the out of bound cases then take care of inside. -> This is just like finding ceil but with diffence in case where letters[mid] == key # def next_letter(letters, key): #     if key < letters[0] or letters[-1] <= key: #         return letters[0] #     left, right = 0, len(letters)-1 #     while left < right: #         mid = (left + right) >> 1 #         if letters[mid] <= key: #             left = mid + 1 #         else: #             right = mid #     return letters[left]