Logo

Kode$word

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153
Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

LeetCode 153 – Find the minimum element in a rotated sorted array in O(log n) time.

13 views
0
0
LeetcodeMediumBinary Search
Github icon

🔗 Try This Problem First

Platform: LeetCode

Problem Number: 153

👉 Practice here: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

🧠 Problem Understanding

You are given a sorted array that has been rotated between 1 and n times.

Example:

Original sorted array:

[0,1,2,4,5,6,7]

After rotation:

[4,5,6,7,0,1,2]

Your task:

👉 Return the minimum element from this rotated array.

👉 Time complexity must be O(log n).

👉 All elements are unique.


🔍 Key Observation

In a rotated sorted array:

  1. The array is divided into two sorted halves.
  2. The minimum element is the pivot point where rotation happened.
  3. One half will always be sorted.
  4. We can use Binary Search to find where the sorted order breaks.

Example:

[4,5,6,7,0,1,2]
↑
Minimum


🚀 Approach 1: Brute Force (Not Allowed by Constraint)

Idea

Scan entire array and track minimum.

int min = nums[0];
for(int i = 1; i < nums.length; i++){
min = Math.min(min, nums[i]);
}
return min;

Complexity

  1. Time: O(n)
  2. Space: O(1)

❌ Not acceptable because problem requires O(log n).


🚀 Approach 2: Binary Search (Optimal – O(log n))

💡 Core Idea

Compare nums[mid] with nums[right].

There are only two possibilities:


Case 1: nums[mid] > nums[right]

Minimum is in right half.

[4,5,6,7,0,1,2]
mid r

Move left pointer:

l = mid + 1


Case 2: nums[mid] <= nums[right]

Minimum is in left half including mid.

[4,5,6,7,0,1,2]
mid r

Move right pointer:

r = mid

✅ Optimized Code

class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;

while (l < r) {
int mid = l + (r - l) / 2;

if (nums[mid] > nums[r]) {
l = mid + 1;
} else {
r = mid;
}
}

return nums[r];
}
}


📊 Dry Run

Input:

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


Steplrmidnums[mid]Action
106377 > 2 → l = 4
246511 <= 2 → r = 5
345400 <= 1 → r = 4
Stop44--Return nums[4]

✅ Output = 0

🧩 Why This Works

  1. If middle element is greater than rightmost, rotation point is to the right.
  2. If middle element is smaller than or equal to rightmost, minimum is on the left side.
  3. We continuously shrink search space until l == r.
  4. That position holds the minimum element.


⏱ Time & Space Complexity

MetricValue
Time ComplexityO(log n)
Space ComplexityO(1)

Because:

  1. We eliminate half of the array each iteration.
  2. No extra space is used.


⚠️ Important Edge Cases

  1. Array size = 1

[10] → 10

  1. Already sorted (no visible rotation)

[11,13,15,17] → 11

  1. Rotation at last position

[1,2,3,4,5] → 1


🎯 Interview Insight

This problem teaches:

  1. Modified Binary Search
  2. Identifying sorted halves
  3. Handling rotated arrays
  4. Understanding pivot logic

This is a very common FAANG interview question and often appears in variations like:

  1. Search in Rotated Sorted Array
  2. Find Peak Element
  3. Minimum in Rotated Array with Duplicates


🏁 Final Takeaway

  1. Brute force works but violates constraint.
  2. Binary search is the correct approach.
  3. Compare mid with right.
  4. Shrink search space until pointers meet.
  5. Return nums[l] or nums[r].


Related Articles

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Optimizing from O(n) Linear Scan to O(log n) Binary Search

Read Article
Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

A Complete Guide to Solving “Find Unique Binary String” Using Hashing, Brute Force Thinking, and Cantor’s Diagonalization

Read Article
Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Peak Index in a Mountain Array – Brute Force to Binary Search (LeetCode 852)

Learn how to find the peak index in a mountain array using multiple approaches including brute force, linear scan, and an optimized binary search solution with O(log n) time complexity.

Read Article

Ai Assistant Kas