Description
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 rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
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.
Examples:
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. Solution in Python
To solve this problem in O(log n) time, we can use a modified binary search algorithm. The key idea is to use the properties of the rotated sorted array to narrow down the search for the minimum element.
Python
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
# Initialize the pointers for binary search
left, right = 0, len(nums) - 1
# Perform binary search
while left < right:
mid = (left + right) // 2
# If the middle element is greater than the rightmost element,
# the smallest element must be to the right of the middle element.
if nums[mid] > nums[right]:
left = mid + 1
# If the middle element is less than or equal to the rightmost element,
# the smallest element is to the left of the middle element or it could be the middle element itself.
else:
right = mid
# The left pointer will be pointing to the smallest element.
return nums[left]Explanation:
- Initialize Pointers:
leftis initialized to the start of the array (index 0).rightis initialized to the end of the array (indexlen(nums) - 1).
- Binary Search Loop:
- The loop runs as long as
leftis less thanright. - Calculate the
midindex:mid = (left + right) // 2.
- The loop runs as long as
- Check Middle Element:
- If the element at
midis greater than the element atright, it means the smallest element is to the right ofmid. Hence, we move theleftpointer tomid + 1. - If the element at
midis less than or equal to the element atright, it means the smallest element is to the left ofmidor could bemiditself. Therefore, we move therightpointer tomid.
- If the element at
- Return the Minimum:
- After the loop ends,
leftwill be pointing to the smallest element in the array, which is the result.
- After the loop ends,
This algorithm ensures that we are effectively halving the search space with each iteration, leading to an O(log n) time complexity, which is optimal for this problem.
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
// Initialize the pointers for binary search
let left = 0;
let right = nums.length - 1;
// Perform binary search
while (left < right) {
// Calculate the mid index
let mid = Math.floor((left + right) / 2);
// If the middle element is greater than the rightmost element,
// the smallest element must be to the right of the middle element.
if (nums[mid] > nums[right]) {
left = mid + 1;
}
// If the middle element is less than or equal to the rightmost element,
// the smallest element is to the left of the middle element or it could be the middle element itself.
else {
right = mid;
}
}
// The left pointer will be pointing to the smallest element.
return nums[left];
};Solution in Java
Java
class Solution {
public int findMin(int[] nums) {
// Initialize the pointers for binary search
int left = 0;
int right = nums.length - 1;
// Perform binary search
while (left < right) {
// Calculate the mid index
int mid = left + (right - left) / 2;
// If the middle element is greater than the rightmost element,
// the smallest element must be to the right of the middle element.
if (nums[mid] > nums[right]) {
left = mid + 1;
}
// If the middle element is less than or equal to the rightmost element,
// the smallest element is to the left of the middle element or it could be the middle element itself.
else {
right = mid;
}
}
// The left pointer will be pointing to the smallest element.
return nums[left];
}
}Solution in C#
C#
public class Solution {
public int FindMin(int[] nums) {
// Initialize the pointers for binary search
int left = 0;
int right = nums.Length - 1;
// Perform binary search
while (left < right) {
// Calculate the mid index
int mid = left + (right - left) / 2;
// If the middle element is greater than the rightmost element,
// the smallest element must be to the right of the middle element.
if (nums[mid] > nums[right]) {
left = mid + 1;
}
// If the middle element is less than or equal to the rightmost element,
// the smallest element is to the left of the middle element or it could be the middle element itself.
else {
right = mid;
}
}
// The left pointer will be pointing to the smallest element.
return nums[left];
}
}