153. Find Minimum in Rotated Sorted Array — LeetCode(Python)

I got you!

Problem:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Solution:

l, r = 0, len(nums) - 1
while l < r:
    mid = (l + r) // 2
    if nums[mid] > nums[r]: # nums[mid] is part of left sorted aubarray
        l = mid + 1
    else:
        r = mid
                
return nums[l]

Explanation:

We use binary search to solve this problem.

The left and right pointers are set at both ends of the array.

Then, we start with the while loop. We find the mid element in our range.

If this mid element is larger than the element at the right pointer, we are in the left sorted subarray, so we move our left pointer to the right of mid, since we know that the min of our array is not going to be in the left subarray.

If, however, this mid is smaller than the element at the right pointer, we check the left subarray, keeping mid inclusive since it could also be the first element in the left subarray.

Our while loop terminates when both left and right pointers converge to one index, and the number at that index is returned.

Essentially,

• we shift right if we are in the left sorted portion
• we shift left if we are in the right sorted portion; nums[mid] is kept inclusive, since it could also be the min in this case.

Time and Space Complexity —

Since we are iterating the array in a “binary search manner”, dividing it into two subarrays at each iteration, our code runs in logarithmic time.

Also, we require a constant amount of extra space.

Thus, if n is the length of the array nums,

Time Complexity: O(log(n))

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏