Problem Overview

  • We are given an array nums
  • The array was originally sorted in ascending order and then left-rotated by k positions, where 1 < k < n
  • All elements in the array are unique
  • We need to find the minimum element in the array
  • The goal is to design a solution with O(log n) time complexity

How I Approached the Problem

I follow a strict rule when solving problems like this:

  • Make it work
  • Then make it optimal

Brute Force Approach

The simplest way to solve this problem is:

  • Traverse the array
  • Keep track of the minimum element encountered

This works as we visit every element of the array.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int mini = INT_MAX;

        for (int it : nums) {
            mini = min(mini, it);
        }

        return mini;
    }
};

Complexity

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

Why This Fails

The problem explicitly requires a logarithmic time solution.

This approach checks every element, resulting in linear time complexity, which does not meet the requirement.

Optimal Solution – Binary Search

Since the array was originally sorted, binary search is the first approch that comes to me after the brute force.

The main challenge is identifying which half of the array contains the minimum.

In a rotated sorted array:

  • If nums[mid] > nums[j], the minimum lies in the right half
  • else, it lies in the left half (including mid)
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = n - 1;

        while (i < j) {
            int mid = (i + j) / 2;

            if (nums[mid] > nums[j]) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }

        return nums[i];
    }
};

Complexity

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

Why This Works

In each iteration, binary search enables us to remove half of the search space.

We can determine where the minimum must exist by comparing mid with the rightmost element.

This keeps the space use constant while reducing the time complexity from O(n) to O(log n).