Find Minimum in Rotated Sorted Array

🎯

Find Minimum in Rotated Sorted Array

mediumBINARY_SEARCHAmazonGoogleMicrosoft

Imagine a circularly shifted sorted list of timestamps from a server log, and you need to find the earliest event quickly.

💡 This problem is about searching in a rotated sorted array, which confuses beginners because the usual sorted array assumptions don't hold. Understanding how to adapt binary search to handle rotation is key.

📋

Problem Statement

Given an integer array nums sorted in ascending order, rotated at some pivot unknown to you beforehand (e.g., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]), find the minimum element in O(log n) time. You may assume no duplicate exists in the array.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4All integers in nums are unique.nums is rotated at some pivot.

💡

Example

Input"[3,4,5,1,2]"

Output1

The array was rotated at index 3, so the minimum element is 1.

Input"[4,5,6,7,0,1,2]"

Output0

The minimum element is 0 after rotation.

Input"[11,13,15,17]"

Output11

Array is not rotated, so the first element is the minimum.

• Array of length 1 → returns the single element
• Array not rotated (fully sorted) → returns first element
• Rotation at last element → minimum is last element
• Large array with rotation near middle → still finds minimum efficiently

⚠️

Common Mistakes

Not handling the case when array is not rotated

Returns wrong minimum or index out of bounds

✅ Check if nums[left] <= nums[right] at start and return nums[left]

Incorrect mid calculation causing overflow

Runtime error or wrong mid index

✅ Use mid = left + (right - left) // 2 instead of (left + right) // 2

Not updating pointers correctly when nums[mid] == nums[right]

Infinite loop or incorrect result

✅ Adjust pointers carefully or use a different condition to avoid infinite loops

Accessing out-of-bound indices when checking neighbors

Runtime error

✅ Use modulo arithmetic or boundary checks when accessing prev and next indices

Confusing when to move left or right pointer

Algorithm fails to converge or returns wrong answer

✅ Remember that if nums[mid] > nums[right], min is in right half; else left half

🧠

Brute Force (Linear Scan)

💡 This approach exists to establish a baseline and ensure understanding of the problem by checking every element. It is simple but inefficient for large inputs.

Intuition

Since the array is rotated, the minimum element is the only element smaller than its previous element. Scanning linearly finds this point.

Algorithm

1. Start from the first element and iterate through the array.
2. Compare each element with the previous one.
3. If an element is smaller than its previous element, return it as the minimum.
4. If no such element is found, return the first element as the array is not rotated.

💡 This approach is straightforward but misses the opportunity to use the sorted property to optimize.

</>

Code

def find_min(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]
    return nums[0]

# Driver code
if __name__ == '__main__':
    arr = [4,5,6,7,0,1,2]
    print(find_min(arr))  # Output: 0

Line Notes

for i in range(1, len(nums))Iterate through array starting from second element to compare with previous

if nums[i] < nums[i - 1]Detect the point where order breaks, indicating minimum element

return nums[i]Return the minimum element found at rotation point

return nums[0]If no break found, array is not rotated; first element is minimum

public class Solution {
    public static int findMin(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return nums[i];
            }
        }
        return nums[0];
    }

    public static void main(String[] args) {
        int[] arr = {4,5,6,7,0,1,2};
        System.out.println(findMin(arr)); // Output: 0
    }
}

Line Notes

for (int i = 1; i < nums.length; i++)Loop through array starting from second element to find rotation point

if (nums[i] < nums[i - 1])Check if current element is smaller than previous, indicating minimum

return nums[i]Return minimum element found at rotation

return nums[0]If no rotation detected, return first element as minimum

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < nums[i - 1]) {
            return nums[i];
        }
    }
    return nums[0];
}

int main() {
    vector<int> arr = {4,5,6,7,0,1,2};
    cout << findMin(arr) << endl; // Output: 0
    return 0;
}

Line Notes

for (int i = 1; i < nums.size(); i++)Traverse array from second element to find rotation point

if (nums[i] < nums[i - 1])Identify the minimum element where order breaks

return nums[i]Return the minimum element found

return nums[0]Return first element if array is not rotated

function findMin(nums) {
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            return nums[i];
        }
    }
    return nums[0];
}

// Test
console.log(findMin([4,5,6,7,0,1,2])); // Output: 0

Line Notes

for (let i = 1; i < nums.length; i++)Loop through array starting from second element to detect rotation

if (nums[i] < nums[i - 1])Find the point where the order breaks indicating minimum

return nums[i]Return the minimum element found

return nums[0]Return first element if no rotation detected

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array once, so time is linear in array size. No extra space is used.

💡 For n=100,000 elements, this means checking each element once, which is slow compared to binary search.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, motivating the need for binary search.

🧠

Modified Binary Search (Pivot Finding)

💡 This approach leverages the sorted and rotated nature of the array to find the minimum in O(log n) time by narrowing down the search space.

Intuition

The minimum element is the only element whose previous element is greater than it. Using binary search, we compare mid element with the rightmost element to decide which half to search.

Algorithm

1. Initialize left and right pointers at start and end of array.
2. While left < right, find mid index.
3. If nums[mid] > nums[right], minimum is in right half, move left to mid + 1.
4. Else, minimum is in left half including mid, move right to mid.
5. Return nums[left] after loop ends.

💡 This algorithm cleverly reduces the search space by comparing mid and right elements, exploiting the rotated sorted property.

</>

Code

def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

# Driver code
if __name__ == '__main__':
    arr = [4,5,6,7,0,1,2]
    print(find_min(arr))  # Output: 0

Line Notes

left, right = 0, len(nums) - 1Initialize pointers to cover entire array

while left < rightLoop until pointers converge to minimum element

mid = (left + right) // 2Calculate middle index to split search space

if nums[mid] > nums[right]If mid element greater than right, minimum is in right half

left = mid + 1Discard left half including mid, move left pointer

else: right = midMinimum is in left half including mid, move right pointer

return nums[left]Return minimum element after convergence

public class Solution {
    public static 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]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    public static void main(String[] args) {
        int[] arr = {4,5,6,7,0,1,2};
        System.out.println(findMin(arr)); // Output: 0
    }
}

Line Notes

int left = 0, right = nums.length - 1Initialize pointers to cover full array

while (left < right)Loop until pointers meet at minimum

int mid = left + (right - left) / 2Calculate mid index safely to avoid overflow

if (nums[mid] > nums[right])Check if minimum is in right half

left = mid + 1Discard left half including mid

else { right = mid; }Minimum is in left half including mid

return nums[left]Return minimum element after loop

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

int main() {
    vector<int> arr = {4,5,6,7,0,1,2};
    cout << findMin(arr) << endl; // Output: 0
    return 0;
}

Line Notes

int left = 0, right = nums.size() - 1Initialize search boundaries

while (left < right)Continue until boundaries converge

int mid = left + (right - left) / 2Calculate mid index safely

if (nums[mid] > nums[right])If mid element greater than right, min is right side

left = mid + 1Move left pointer past mid

else { right = mid; }Otherwise, min is at mid or left side

return nums[left]Return minimum element found

function findMin(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

// Test
console.log(findMin([4,5,6,7,0,1,2])); // Output: 0

Line Notes

let left = 0, right = nums.length - 1Initialize pointers for binary search

while (left < right)Loop until pointers meet

let mid = Math.floor((left + right) / 2)Calculate middle index

if (nums[mid] > nums[right])Check if min is in right half

left = mid + 1Discard left half including mid

else { right = mid; }Keep left half including mid

return nums[left]Return minimum element after loop

⏱

Complexity

TimeO(log n)

SpaceO(1)

Binary search halves the search space each iteration, leading to logarithmic time complexity.

💡 For n=100,000 elements, this means about 17 comparisons, which is very efficient.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and use of binary search.

🧠

Binary Search with Additional Checks (Explicit Pivot Detection)

💡 This approach explicitly checks if mid is the pivot (minimum) by comparing with neighbors, adding clarity at the cost of slightly more code.

Intuition

The minimum element is the only element smaller than its previous element. By checking mid against neighbors, we can identify the pivot directly.

Algorithm

1. Initialize left and right pointers.
2. While left <= right, find mid.
3. Check if mid element is smaller than previous element; if yes, return mid element.
4. Check if mid element is greater than next element; if yes, return next element.
5. If mid element is greater than left element, move left to mid + 1.
6. Else, move right to mid - 1.
7. Return first element if no pivot found.

💡 This approach is more explicit but requires careful boundary checks to avoid index errors.

</>

Code

def find_min(nums):
    left, right = 0, len(nums) - 1
    n = len(nums)
    while left <= right:
        mid = (left + right) // 2
        prev = (mid - 1 + n) % n
        next_ = (mid + 1) % n
        if nums[mid] < nums[prev]:
            return nums[mid]
        if nums[mid] > nums[next_]:
            return nums[next_]
        if nums[mid] >= nums[left]:
            left = mid + 1
        else:
            right = mid - 1
    return nums[0]

# Driver code
if __name__ == '__main__':
    arr = [4,5,6,7,0,1,2]
    print(find_min(arr))  # Output: 0

Line Notes

left, right = 0, len(nums) - 1Initialize search boundaries

while left <= rightLoop until pointers cross

prev = (mid - 1 + n) % nCalculate previous index circularly to avoid out-of-bounds

next_ = (mid + 1) % nCalculate next index circularly

if nums[mid] < nums[prev]Check if mid is pivot by comparing with previous

if nums[mid] > nums[next_]Check if next element is pivot

if nums[mid] >= nums[left]Decide which half to search based on mid and left

left = mid + 1Search right half if mid >= left

right = mid - 1Search left half otherwise

return nums[0]Return first element if no pivot found

public class Solution {
    public static int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int n = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int prev = (mid - 1 + n) % n;
            int next = (mid + 1) % n;
            if (nums[mid] < nums[prev]) {
                return nums[mid];
            }
            if (nums[mid] > nums[next]) {
                return nums[next];
            }
            if (nums[mid] >= nums[left]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return nums[0];
    }

    public static void main(String[] args) {
        int[] arr = {4,5,6,7,0,1,2};
        System.out.println(findMin(arr)); // Output: 0
    }
}

Line Notes

int left = 0, right = nums.length - 1Initialize pointers

while (left <= right)Loop until pointers cross

int prev = (mid - 1 + n) % nCalculate previous index circularly

int next = (mid + 1) % nCalculate next index circularly

if (nums[mid] < nums[prev])Check if mid is pivot

if (nums[mid] > nums[next])Check if next is pivot

if (nums[mid] >= nums[left])Decide which half to search

left = mid + 1Search right half

right = mid - 1Search left half

return nums[0]Return first element if no pivot found

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int n = nums.size();
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int prev = (mid - 1 + n) % n;
        int next = (mid + 1) % n;
        if (nums[mid] < nums[prev]) {
            return nums[mid];
        }
        if (nums[mid] > nums[next]) {
            return nums[next];
        }
        if (nums[mid] >= nums[left]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return nums[0];
}

int main() {
    vector<int> arr = {4,5,6,7,0,1,2};
    cout << findMin(arr) << endl; // Output: 0
    return 0;
}

Line Notes

int left = 0, right = nums.size() - 1Initialize search boundaries

while (left <= right)Loop until pointers cross

int prev = (mid - 1 + n) % nCalculate previous index safely

int next = (mid + 1) % nCalculate next index safely

if (nums[mid] < nums[prev])Check if mid is pivot

if (nums[mid] > nums[next])Check if next is pivot

if (nums[mid] >= nums[left])Decide which half to search

left = mid + 1Search right half

right = mid - 1Search left half

return nums[0]Return first element if no pivot found

function findMin(nums) {
    let left = 0, right = nums.length - 1;
    const n = nums.length;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let prev = (mid - 1 + n) % n;
        let next = (mid + 1) % n;
        if (nums[mid] < nums[prev]) {
            return nums[mid];
        }
        if (nums[mid] > nums[next]) {
            return nums[next];
        }
        if (nums[mid] >= nums[left]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return nums[0];
}

// Test
console.log(findMin([4,5,6,7,0,1,2])); // Output: 0

Line Notes

let left = 0, right = nums.length - 1Initialize pointers

while (left <= right)Loop until pointers cross

let prev = (mid - 1 + n) % nCalculate previous index circularly

let next = (mid + 1) % nCalculate next index circularly

if (nums[mid] < nums[prev])Check if mid is pivot

if (nums[mid] > nums[next])Check if next is pivot

if (nums[mid] >= nums[left])Decide which half to search

left = mid + 1Search right half

right = mid - 1Search left half

return nums[0]Return first element if no pivot found

⏱

Complexity

TimeO(log n)

SpaceO(1)

Binary search with explicit pivot checks still halves search space each iteration.

💡 This approach is slightly more complex but still efficient for large inputs.

Interview Verdict: Accepted and optimal, but more verbose

Good to know for understanding pivot properties, but usually the simpler binary search is preferred.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the modified binary search (Approach 2) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(1)	No	N/A	Mention only - never code
2. Modified Binary Search	O(log n)	O(1)	No	N/A	Code this approach
3. Binary Search with Explicit Pivot Checks	O(log n)	O(1)	No	N/A	Good to mention for deeper understanding

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to clarify the problem, then move to optimal binary search solutions.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force linear scan approach and its inefficiency.Step 3: Introduce the modified binary search approach leveraging rotation properties.Step 4: Write clean code for the binary search solution.Step 5: Test with edge cases and explain time and space complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your understanding of binary search adaptations, handling edge cases, and writing clean, efficient code.

Common Follow-ups

• How to handle duplicates in the array? → Use a modified binary search that handles equal elements carefully.
• How to find the index of the minimum element? → Return the left pointer index instead of the value.

💡 These follow-ups test your ability to adapt the solution to variations and deepen your understanding.

🔍

Pattern Recognition

When to Use

1) Array is sorted but rotated; 2) Need to find minimum or pivot; 3) No duplicates (or handled separately); 4) O(log n) time required.

Signature Phrases

'rotated sorted array''find minimum element''no duplicates''O(log n) time'

NOT This Pattern When

Standard binary search on fully sorted arrays without rotation

Similar Problems

Search in Rotated Sorted Array - uses similar binary search logic to find targetFind Minimum in Rotated Sorted Array II - extension with duplicates handledFind Peak Element - binary search on array properties

Practice

1. What is the time complexity of the optimal approach that uses a single binary search followed by expanding boundaries to find the first and last positions of the target in a sorted array?

medium

A. O(n)

B. O(log n + k), where k is the number of occurrences of the target

C. O(log n * k), where k is the number of occurrences of the target

D. O(log n)

Solution

1. Step 1: Analyze binary search phase

   Binary search runs in O(log n) to find one occurrence of target.

2. Step 2: Analyze boundary expansion phase

   Expanding left and right to find all occurrences takes O(k), where k is count of target.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Combined complexity is O(log n + k), not multiplicative [OK]

Hint: Binary search plus linear expansion over occurrences [OK]

Common Mistakes:

• Assuming O(log n) only
• Multiplying log n by k incorrectly
• Ignoring expansion cost

2. The following code attempts to find the median of two sorted arrays using binary search on the smaller array. Identify the line containing the subtle bug that can cause incorrect median calculation for even total length arrays.

medium

A. Line: if (m + n) % 2 == 0: return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2

B. Line: if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1

C. Line: partitionY = (m + n) // 2 - partitionX

D. Line: while low <= high:

Solution

1. Step 1: Understand partition calculation

   partitionY must be total left half minus partitionX to split arrays correctly.

2. Step 2: Identify off-by-one bug

   Using (m + n) // 2 instead of (m + n + 1) // 2 causes incorrect partition when total length is odd, leading to wrong median.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Partition calculation off-by-one breaks median correctness [OK]

Hint: Partition indices must sum to half total length exactly, using (m+n+1)//2 for correct odd/even handling [OK]

Common Mistakes:

• Swapping arrays incorrectly
• Wrong median formula for even length
• Loop boundary off-by-one

3. What is the time complexity of the optimal approach that performs binary search on each row of an m x n matrix to find a target value?

medium

A. O(log m * log n)

B. O(m * n)

C. O(m * log n)

D. O(m + n)

Solution

1. Step 1: Identify outer loop complexity

   We iterate over m rows, so outer loop is O(m).

2. Step 2: Identify inner binary search complexity

   Binary search on each row of length n takes O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(m * log n), not O(m*n) or O(log m * log n) [OK]

Hint: Binary search is logarithmic per row [OK]

Common Mistakes:

• Confusing with brute force O(m*n)
• Thinking binary search applies to columns too
• Assuming double log complexity

4. What is the worst-case time complexity of the optimal binary search algorithm that handles duplicates in a rotated sorted array?

medium

A. O(n) because duplicates can force linear scanning in worst case

B. O(log n) because binary search halves the search space each iteration

C. O(n log n) due to repeated duplicate skipping combined with binary search

D. O(1) since duplicates are skipped quickly

Solution

1. Step 1: Analyze binary search with duplicates

   Duplicates at boundaries can cause the algorithm to skip only one element per iteration, degrading to linear scan.

2. Step 2: Conclude worst-case complexity

   In worst case (all elements equal), the algorithm behaves like linear search -> O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicates break binary halving, causing linear worst-case [OK]

Hint: Duplicates can degrade binary search to linear time [OK]

Common Mistakes:

• Assuming always O(log n)
• Confusing average and worst case
• Thinking duplicate skipping is constant time

5. Suppose the problem is modified so that the multiplication table allows repeated use of the same row and column indices (i.e., infinite repetitions of each product). Which of the following changes to the algorithm is correct to find the k-th smallest number under this new condition?

hard

A. Use the same binary search with the counting function unchanged, since repetition doesn't affect counts.

B. Switch to generating all products up to k and sorting them, since binary search no longer applies.

C. Use a min-heap to generate products in ascending order with duplicates allowed, extracting k elements.

D. Modify the counting function to remove the cap by n, counting all multiples less than or equal to x for each i.

Solution

1. Step 1: Understand the new problem condition

   Allowing infinite repetitions means the multiplication table is conceptually infinite, so counting by rows capped at n no longer applies.

2. Step 2: Analyze algorithmic implications

   Binary search with counting function fails because counts become infinite or undefined; generating all values is impossible.

3. Step 3: Use a min-heap approach

   A min-heap can generate products in ascending order with duplicates allowed, extracting the k-th smallest efficiently.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap approach handles infinite repetitions correctly [OK]

Hint: Infinite repetitions break counting; use min-heap [OK]

Common Mistakes:

• Assuming counting function unchanged
• Trying to generate all values