Find Minimum in Rotated Sorted Array - Practice Coding Problems

Find Minimum in Rotated Sorted Array - Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Input & Output

Example 1 — Rotated Array

$ Input: nums = [3,4,5,1,2]

› Output: 1

💡 Note: The original array was [1,2,3,4,5] rotated 3 times. The minimum element is 1.

Example 2 — Heavily Rotated

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

› Output: 0

💡 Note: The original array was [0,1,2,4,5,6,7] rotated 4 times. The minimum element is 0.

Example 3 — Minimally Rotated

$ Input: nums = [11,13,15,17]

› Output: 11

💡 Note: The original array was [11,13,15,17] rotated 4 times (full rotation). The minimum element is 11.

Constraints

n == nums.length
1 ≤ n ≤ 5000
-5000 ≤ nums[i] ≤ 5000
All the integers of nums are unique
nums is sorted and rotated between 1 and n times

Visualization

Tap to expand

Understanding the Visualization

Original

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

Rotated

After rotation: [4,5,6,7,0,1,2]

Minimum

Find the smallest element: 0

Key Takeaway

🎯 Key Insight: The minimum is always at the rotation point where sorted order breaks

Asked in

a Amazon 45 M Microsoft 38 G Google 32 F Facebook 28

The key insight is that in a rotated sorted array, the minimum element is where the sorted order breaks. The optimal approach uses binary search to compare the middle element with the rightmost element, eliminating half the array each time. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search	O(log n)	O(1)	Use binary search to find the rotation pivot point
Linear Search	O(n)	O(1)	Check every element to find the minimum

Binary Search — Algorithm Steps

Step 1: Set left and right pointers
Step 2: Compare middle with right element
Step 3: Move pointers based on comparison
Step 4: Continue until left meets right

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Initialize left and right pointers

Compare

Compare middle element with right element

Narrow

Move pointers to eliminate half of array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int left = 0, right = numsSize - 1;
    
    while (left < right) {
        int mid = (left + right) / 2;
        
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return nums[left];
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int count = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        nums[count++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
    }
    
    printf("%d\n", solution(nums, count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search divides the array in half each iteration

⚡ Linearithmic

Space Complexity

O(1)

Only using two pointer variables

✓ Linear Space

85.0K Views

High Frequency

~15 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler