TIC
The Interns Company

Find Minimum in Rotated Sorted Array

MediumAcceptance: 46.2%
ArrayBinary Search

Problem Statement

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 or [0,1,2,4,5,6,7] if it was rotated 7 times. Given the sorted rotated array nums of unique elements, return the minimum element of this array.

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.

Input Format:

  • An array of integers nums that is sorted and rotated

Output Format:

  • Return the minimum element in the array.

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.

Solutions

Binary Search Approach

Time: O(log n)
Space: O(1)

Use binary search to find the pivot point (minimum element) in the rotated array. The key insight is to compare the middle element with the rightmost element to determine which half of the array contains the minimum.

Optimized Binary Search Approach

Time: O(log n)
Space: O(1)

A cleaner binary search implementation that compares the middle element with the rightmost element to determine which half to search.

Algorithm Walkthrough

Example input: nums = [4,5,6,7,0,1,2]

Step-by-step execution:

  1. Initialize left=0, right=6
  2. Calculate mid=3, nums[mid]=7
  3. Compare: nums[mid]=7 > nums[right]=2, so minimum is in right half
  4. Update left=mid+1=4, so left=4, right=6
  5. Calculate mid=5, nums[mid]=1
  6. Compare: nums[mid]=1 < nums[right]=2, so minimum is in left half (including mid)
  7. Update right=mid=5, so left=4, right=5
  8. Calculate mid=4, nums[mid]=0
  9. Compare: nums[mid]=0 < nums[right]=1, so minimum is in left half (including mid)
  10. Update right=mid=4, so left=4, right=4
  11. left and right converge, return nums[left]=0

Hints

Hint 1
Think about using binary search to find the minimum in O(log n) time.
Hint 2
The minimum element is the only element whose previous element is greater than it.
Hint 3
If the array is rotated, the minimum element would be the pivot point.

Video Tutorial

Find Minimum in Rotated Sorted Array - Binary Search Approach

YouTube•Learn the Find Minimum in Rotated Sorted Array solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the binary search process to find the minimum element in the rotated sorted array.

Key visualization elements:

  • current left boundary
  • current right boundary
  • mid point
  • comparison value

Similar Questions

Search in Rotated Sorted Array

Medium

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Asked By

AmazonMicrosoftFacebookGoldman SachsBloombergAdobeUber

Implementation Notes

This problem is a classic application of binary search in a rotated sorted array. Understanding this problem is key to solving other rotated array problems.