Vansh Aggarwal

Posted on May 15

LeetCode Solution: 153. Find Minimum in Rotated Sorted Array

#leetcode #dsa #programming #tutorial

Master the Mystery: Finding the Minimum in a Rotated Sorted Array!

Hey LeetCoders and aspiring developers! 👋 Vansh2710 here, ready to demystify another classic algorithm problem that often pops up in interviews and challenges our problem-solving skills. Today, we're tackling LeetCode 153: "Find Minimum in Rotated Sorted Array."

This problem is a fantastic introduction to how binary search, a technique you might think is only for perfectly sorted arrays, can be cleverly adapted to solve more complex scenarios. Ready to dive in? Let's go!

The Problem: A Twisted Tale of Sorted Numbers

Imagine you have a perfectly sorted array of unique numbers, like [0, 1, 2, 4, 5, 6, 7]. Simple enough, right? The minimum is clearly 0.

Now, here's the twist: this array gets "rotated." This means some number of elements from the end are moved to the beginning.

Example: [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] if it was rotated 4 times. Or, [7, 0, 1, 2, 4, 5, 6] if rotated once.

Your mission, should you choose to accept it, is to find the minimum element in this rotated sorted array. The kicker? Your algorithm must run in O(log n) time. This immediately screams "binary search" to a competitive programmer, but how do we apply it to a "broken" sorted array? That's the fun part!

The "Aha!" Moment: Binary Search's Hidden Power

At first glance, an array like [4,5,6,7,0,1,2] doesn't look sorted. But wait! It's partially sorted. It's actually two sorted arrays mashed together. The minimum element is the "pivot" where the ascending order breaks.

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

The left part: [4,5,6,7] (sorted)
The right part: [0,1,2] (sorted)
The minimum 0 is the first element of the right part.

Our "aha!" moment is realizing that we can still use the core idea of binary search: discarding half of the search space in each step. The trick is figuring out which half to discard.

The key insight: If we compare the middle element (nums[mid]) with the rightmost element (nums[e]), we can tell which "side" the minimum element is on.

If nums[mid] > nums[e]: This means mid is in the "larger" sorted part (e.g., 7 in [4,5,6,7,0,1,2]). The minimum must be in the elements to the right of mid.
If nums[mid] <= nums[e]: This means mid is in the "smaller" sorted part (e.g., 0 in [4,5,6,7,0,1,2]). The minimum is either mid itself or somewhere to its left.

This simple comparison is our compass in the rotated array jungle!

The Approach: Navigating with Binary Search

Let's break down the binary search logic step-by-step:

Initialize Pointers:
- s (start) to 0
- e (end) to nums.size() - 1
Loop Condition: Continue as long as s < e. When s equals e, we've narrowed down our search to a single element, which must be the minimum.
Calculate Midpoint: mid = s + (e - s) / 2. This prevents potential integer overflow compared to (s + e) / 2.
Decision Time! Compare nums[mid] with nums[e]:

*   **Case 1: `nums[mid] > nums[e]`**
    *   This tells us that the pivot (minimum element) *must* be located somewhere to the **right** of `mid`. Why? Because `nums[mid]` is part of the "larger" sorted segment, and `nums[e]` is part of the "smaller" segment. For `nums[mid]` to be greater than `nums[e]`, the break point (the minimum) has to be between `mid` and `e` (inclusive of `e`).
    *   So, we update `s = mid + 1`.

*   **Case 2: `nums[mid] <= nums[e]`**
    *   This implies two possibilities:
        1.  `nums[mid]` is the minimum itself.
        2.  The minimum is somewhere in the left half of the array (including `mid`).
    *   In both scenarios, `mid` or an element to its left could be the minimum. We can safely discard the right half *after* `mid`.
    *   So, we update `e = mid`.

Termination: When the while loop finishes (s == e), the pointer s (or e) will be pointing to the minimum element. Return nums[s].

Let's quickly trace [3,4,5,1,2] (Example 1):

Initial: s=0, e=4, nums = [3,4,5,1,2]
Iteration 1:
- mid = 0 + (4-0)/2 = 2. nums[mid] = nums[2] = 5.
- nums[mid] (5) > nums[e] (2) is True.
- Minimum is to the right. s = mid + 1 = 3.
- State: s=3, e=4.
Iteration 2:
- mid = 3 + (4-3)/2 = 3. nums[mid] = nums[3] = 1.
- nums[mid] (1) <= nums[e] (2) is True.
- Minimum is at or to the left. e = mid = 3.
- State: s=3, e=3.
Loop ends because s is no longer less than e.
Return nums[s] = nums[3] = 1. Correct!

The Code 🧑‍💻

Here's the C++ implementation following our logic:

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int s = 0;
        int e = nums.size() - 1;

        // Loop until s and e meet (or cross, but in this specific binary search variant, they meet)
        while (s < e) {
            int mid = s + (e - s) / 2; // Calculate midpoint to prevent overflow

            // If nums[mid] is greater than nums[e], it means mid is in the 'left' sorted part
            // and the minimum must be in the elements to the right of mid.
            if (nums[mid] >= nums[e]) {
                s = mid + 1;
            }
            // Otherwise, nums[mid] is less than or equal to nums[e].
            // This means mid is in the 'right' sorted part (or is the minimum).
            // The minimum could be mid itself, or something to its left.
            else {
                e = mid;
            }
        }

        // When the loop terminates, s == e, and this index points to the minimum element.
        return nums[s];
    }
};

Time & Space Complexity Analysis

Time Complexity: O(log n)
- Each step of our binary search effectively halves the search space. This is the hallmark of logarithmic time complexity. Regardless of how large n gets, the number of operations grows very slowly.
Space Complexity: O(1)
- We are only using a few extra variables (s, e, mid) to keep track of our pointers. The amount of memory used doesn't scale with the input size n.

Key Takeaways

Binary Search Adaptability: Don't limit binary search to perfectly sorted arrays. Look for properties that allow you to discard half of the search space.
Pivot Point: In rotated sorted arrays, the minimum element acts as a "pivot" or a "break" in the otherwise sorted order.
Comparison Strategy: Comparing nums[mid] with nums[e] is a powerful technique to determine which half contains the minimum in this specific problem.
Edge Cases: The algorithm gracefully handles cases where the array isn't rotated at all (e.g., [1,2,3,4,5] where nums[mid] <= nums[e] will always be true, eventually e will be 0 and nums[0] is returned).

And there you have it! Finding the minimum in a rotated sorted array using an elegant O(log n) binary search solution. This problem is a fantastic way to deepen your understanding of binary search and its versatility. Keep practicing, and you'll master these algorithmic patterns in no time!

Happy coding!

Author Account: Vansh2710
Time Published: 2026-05-15 16:35:29

DEV Community