LeetCode 153: Find Minimum in Rotated Sorted Array Solution

Master LeetCode problem 153 (Find Minimum in Rotated Sorted Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

153. Find Minimum in Rotated Sorted Array

Medium

Array Binary Search

Problem Explanation

Explanation

To find the minimum element in a rotated sorted array, we can utilize a modified binary search algorithm. The idea is to compare the middle element of the array with the first and last elements to determine which half of the array to discard. This way, we can focus on the unsorted half where the minimum element lies.

Initialize two pointers, left and right, pointing to the start and end of the array respectively.
Perform binary search until left and right converge, indicating that the minimum element has been found.
At each step, compare the middle element with the first and last elements to determine which half is unsorted and update left or right accordingly.
Return the element at the left index, which will be the minimum element.

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

Solution Code

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;
            } else {
                left = mid + 1;
            }
        }
        
        return nums[left];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 153 (Find Minimum in Rotated Sorted Array)?

This page provides optimized solutions for LeetCode problem 153 (Find Minimum in Rotated Sorted Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 153 (Find Minimum in Rotated Sorted Array)?

The time complexity for LeetCode 153 (Find Minimum in Rotated Sorted Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 153 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 153 in Java, C++, or Python.

Back to LeetCode Solutions