src.min_rot_sort_array

Classes

Solution()

class src.min_rot_sort_array.Solution

findMin(nums: list[int]) → int

Thought process

• The key insight here is that the minimum element is the only element in the array that is smaller than its previous element.

• Since we want to solve the problem in log n the first intuition is always divide and conquer, in this instance that takes the form of a binary search

• Two key things to remember, we init left and right to 0 and len(nums) - 1, and the mid point is calculated as left + (right - left) // 2

Notes

• time complexity is \(O(log n)\)

• space complexity is \(O(1)\)

findMinRecursive(nums: list[int]) → int

Thought process

• Similar to the iterative approach, just using recursion

• The base case is when left >= right, we return the element at the left index

• Probably worse for interviews, but good to know

Notes

• time complexity is \(O(log n)\)

• space complexity is \(O(log n)\) due to the recursive stack