A Structure a Day #Day 0

Problem Description:

Given a list of numbers obtained by rotating a sorted list an unknown number of times, write a function to determine the minimum number of times the original sorted list was rotated to obtain the given list. Your function should have the worst-case complexity of O(log N), where N is the length of the list. You can assume that all the numbers in the list are unique.

Example 1:

Input: nums = [19, 25, 29, 3, 5, 6, 7, 9, 11, 14]
Output: 3

Rotation of a list is defined as removing the last element of the list and adding it before the first element. In example 1, the list [19, 25, 29, 3, 5, 6, 7, 9, 11, 14] was obtained by rotating the sorted list [3, 5, 6, 7, 9, 11, 14, 19, 25, 29]3 times.

Example 2:

Input: nums = [5, 6, 9, 0, 2, 3, 4]
Output: 4

In example 2, the list [5, 6, 9, 0, 2, 3, 4] was obtained by rotating the sorted list [0, 2, 3, 4, 5, 6] 4 times.

Solution:

Thought process:

• Given a sorted array that has been rotated an unknown number of times, the minimum number of rotations can be determined by finding the first index where the element is less than the element preceding it.

• This index represents the position of the minimum element in the rotated array.

• If the array is empty, the function returns 0.

Code:

"""
Determines the minimum number of times the original sorted list was rotated to obtain the given list.

Args:
    nums: A list of integers.

Returns:
    The minimum number of times the list was rotated.
"""

def min_times_of_rotation(nums):
    """
    Finds the first index where the element is less than the preceding element.

    Args:
        nums: A list of integers.

    Returns:
        The minimum number of times the list was rotated.
    """

    position = 0
    while position < len(nums):
        if position > 0 and nums[position] < nums[position - 1]:
            return position
        position += 1
    return 0

# Test cases
nums = [8, 4, 3, 6, 7, 9, 2]
print(min_times_of_rotation(nums))

tests = [19, 25, 29, 3, 5, 6, 7, 9, 11, 14]
print(min_times_of_rotation(tests))

x = [5, 6, 9, 0, 2, 3, 4]
print(min_times_of_rotation(x))

x = [6, 7, 8, 9, 0, 1, 2, 3, 4, 5]
print(min_times_of_rotation(x))

Output:

1 3 3 4