Skip to content
AI360Xpert
Back to Binary Search
Medium

Find Minimum in Rotated Sorted Array

Suppose an array of length `n` sorted in ascending order is rotated between `1` and `n` times. 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

Input:nums = [3,4,5,1,2]
Output:1
The original array was [1,2,3,4,5] rotated 3 times.
Input:nums = [4,5,6,7,0,1,2]
Output:0
The original array was [0,1,2,4,5,6,7] 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.

Approach

Iterate through the array and keep track of the minimum element seen so far.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

This approach does not meet the O(log n) time complexity requirement.

Solution.java
class Solution {    public int findMin(int[] nums) {        int min = nums[0];        for (int i = 1; i < nums.length; i++) {            if (nums[i] < min) {                min = nums[i];            }        }        return min;    }}