Find Minimum in Rotated Sorted Array II - Practice Coding Problems

Find Minimum in Rotated Sorted Array II - 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,4,4,5,6,7] might become:

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,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 that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Input & Output

Example 1 — Basic Rotation

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

› Output: 1

💡 Note: The array is not rotated, minimum is the first element: 1

Example 2 — With Duplicates

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

› Output: 0

💡 Note: Array has duplicates, but minimum is still 0 which appears after the duplicates

Example 3 — All Same Elements

$ Input: nums = [3,3,3,3,3]

› Output: 3

💡 Note: All elements are the same, so minimum is 3

Constraints

n == nums.length
1 ≤ n ≤ 5000
-5000 ≤ nums[i] ≤ 5000
nums is sorted and rotated between 1 and n times.
nums may contain duplicates

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array rotated with possible duplicates

Process

Use binary search but handle duplicate elements

Output

Return the minimum element

Key Takeaway

🎯 Key Insight: When duplicates prevent binary search direction determination, we must fall back to linear reduction

Asked in

A Amazon 45 M Microsoft 38 G Google 32

The key insight is handling duplicates in a rotated sorted array. When duplicates prevent binary search from determining direction, we reduce the search space linearly. Best approach uses modified binary search with average Time: O(log n), worst Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Scan through entire array to find minimum element
Modified Binary Search	O(log n) average, O(n) worst	O(1)	Use binary search with special handling for duplicates

Linear Search — Algorithm Steps

Initialize minimum as first element
Iterate through each element
Update minimum if current element is smaller

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with first element as minimum

Compare

Check each element against current minimum

Result

Return the smallest value found

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int minVal = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < minVal) {
            minVal = nums[i];
        }
    }
    return minVal;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[5000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all n elements

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for minimum variable

✓ Linear Space

125.0K Views

Medium Frequency

~25 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

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler