← Back to Index

📚 Find Minimum in Rotated Sorted Array II – Java Cheat Sheet

📌 What Is It?

The Find Minimum in Rotated Sorted Array II problem involves finding the minimum element in a rotated sorted array that may contain duplicates. The goal is to solve this in O(log N) time in the best case, but it may degrade to O(N) in the presence of duplicates.

🧱 Pattern Template

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[right]) {
                right = mid; // Minimum is in the left half
            } else if (nums[mid] > nums[right]) {
                left = mid + 1; // Minimum is in the right half
            } else {
                right--; // Handle duplicates by reducing the search space
            }
        }

        return nums[left]; // Minimum element
    }
}

📊 Time Complexity

• Best Case: O(log N) – Halving the search space at each step.
• Worst Case: O(N) – When duplicates force a linear scan.

✅ Use Cases

• Finding the minimum element in rotated sorted arrays with duplicates
• Applications in searching and optimization problems

📘 Common LeetCode Problems

• 154. Find Minimum in Rotated Sorted Array II [Hard] Binary Search

🧪 Example: Find Minimum in Rotated Sorted Array II

Input: nums = [2,2,2,0,1]
Output: 0

Explanation:
- The minimum element in the array is 0.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the minimum element.
• Handle duplicates by reducing the search space when nums[mid] == nums[right].
• Edge cases: arrays with all duplicates, single-element arrays, or no rotation.