Skip to content

Volume ITechnology

4.11.4 — Find Minimum in Rotated Sorted Array ​

LeetCode 153 · Medium · ★ Blind 75

The problem ​

A list of different numbers was sorted from smallest to largest. Then it was rotated: some numbers were taken off the end and moved, in order, to the front. For example, [0, 1, 2, 4, 5, 6, 7] rotated 4 times becomes [4, 5, 6, 7, 0, 1, 2]. You are given the rotated list nums. Return its smallest number, in O(\log n) time.

nums = [3, 4, 5, 1, 2]          →  1
nums = [4, 5, 6, 7, 0, 1, 2]    →  0
nums = [11, 13, 15, 17]         →  11    (rotated all the way round, so still sorted)

The list has between 1 and 5,000 numbers, all different.

What the problem is really asking ​

A rotated sorted list is always two sorted runs, with a single drop between them.

[4, 5, 6, 7, 0, 1, 2]
 └── run A ─┘└ run B ┘
             ↑
       the smallest number is right here, at the drop

Every number in run A is bigger than every number in run B. So the smallest number is the first number of run B: the one place where a number is smaller than the number before it.

So the real question is: when you look at the middle, how can you tell which run it is in, and so which half holds the drop?

The brute force, and where it wastes work ​

Scan the whole list for the smallest number.

python
def findMin(nums):
    return min(nums)

That is O(n). The problem asks for O(\log n), which means throwing away half the list at each step without looking at it.

The waste in one sentence: it looks at every number, when one comparison with the last number tells you which half the drop is in.

The idea ​

Look at the middle number, nums[mid], and compare it with the last number of the current range, nums[high].

  • If nums[mid] > nums[high], the numbers go down somewhere between mid and high. In a sorted run they would only go up. So the drop, and the smallest number, lie strictly to the right of mid.
  • Otherwise, nums[mid] <= nums[high], so the numbers from mid to high only go up. There is no drop in that stretch. The smallest number is at mid or to its left.

Why compare with the last number, not the first? ​

Comparing with the first number, nums[low], feels just as natural. But it cannot tell two situations apart.

Suppose nums[mid] > nums[low]. That means low to mid goes up. Is the smallest number to the right of mid? In a rotated list like [4, 5, 6, 7, 0, 1, 2], yes. But in a list that is not rotated, like [1, 2, 3, 4, 5], the smallest number is at low, to the left. The same comparison result would point you in two opposite directions.

Comparing with nums[high] never has this problem. If mid to high goes up, there is no drop there, whether or not the list is rotated. So the smallest number must be at mid or to its left. A list that is not rotated is handled automatically, with no special case.

The solution ​

python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1             # (1)

        while low < high:                        # (2)
            mid = low + (high - low) // 2
            if nums[mid] > nums[high]:           # (3)
                low = mid + 1
            else:                                # (4)
                high = mid

        return nums[low]                         # (5)
ts
function findMin(nums: number[]): number {
  let low = 0, high = nums.length - 1;           // (1)

  while (low < high) {                           // (2)
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] > nums[high]) low = mid + 1;   // (3)
    else high = mid;                             // (4)
  }

  return nums[low];                              // (5)
}

Line by line ​

(1) The range covers the whole list.

(2) Shape B from 4.11.1. We are not looking for a given value. We are closing in on a position, the drop. So the loop runs while low < high, and stops when both point at the same place.

(3) There is a drop between mid and high. So the smallest number is strictly to the right of mid, and mid itself cannot be it, because the number at the drop is smaller than nums[mid]. Move low past mid.

(4) No drop between mid and high. The smallest number is mid itself or somewhere to its left. mid might be the answer, so keep it: high = mid, not mid - 1.

(5) low and high have met on the smallest number.

Many published solutions add an extra early check, if nums[low] < nums[high]: return nums[low], for a list that is not rotated. It is not needed. As explained above, line (4) already pulls high left until it reaches the start.

Trace ​

Take nums = [4, 5, 6, 7, 0, 1, 2].

Steplowhighmidnums[mid] vs nums[high]Action
10637 > 2, drop is to the rightlow = 4
24651 ≤ 2, no drophigh = 5
34540 ≤ 1, no drophigh = 4
end44return nums[4] = 0

Now a list that is not rotated, [1, 2, 3].

SteplowhighmidComparisonAction
10212 ≤ 3high = 1
20101 ≤ 2high = 0
end00return 1

No special case was needed.

Complexity, derived ​

Time. Each step at least halves the range, so there are about \log_2 n steps, each doing one comparison. So O(\log n).

Space. Three numbers, so O(1).

Edge cases ​

  • One number. low == high from the start. The loop never runs, and we return it.
  • Not rotated at all. Shown in the second trace.
  • Rotated by one, like [2, 3, 4, 5, 1]. The drop is at the very end, and the search moves right until it reaches it.
  • Two numbers, like [2, 1]. mid is 0, 2 > 1, so low becomes 1. Return 1.

What repeated numbers do ​

Find Minimum in Rotated Sorted Array II allows repeated numbers, and that breaks this method in one place.

When nums[mid] == nums[high], you learn nothing. Compare [3, 3, 1, 3] and [3, 1, 3, 3]. Both have nums[mid] == nums[high], but the smallest number is on opposite sides of mid.

The only safe move is high -= 1. That drops one copy of a repeated number. It cannot lose the answer, because the number at high has an equal twin at mid, which stays in the range.

So the worst case becomes O(n): a list where every number is the same shrinks by just one each step. This is unavoidable. When repeats are allowed, the drop can hide behind identical numbers, and no comparison can find it faster. Saying that clearly is the right answer.

Variations you will meet ​

  • Search in Rotated Sorted Array. Find a given value instead of the smallest. That is the next page, 4.11.5. One clean way to solve it is to find the drop with this page's code, then binary search the correct run.
  • Find Peak Element. Find any number bigger than both its neighbours. Compare nums[mid] with nums[mid + 1], and move toward the bigger one, because the numbers must turn down somewhere on that side. It works on a list that is not sorted at all, which shows that binary search only needs a rule that safely throws away half.

The general lesson: binary search does not need a fully sorted list. It needs one comparison that tells you which half to keep.

What the interviewer will push on ​

"Why compare with nums[high], not nums[low]?" Comparing with low gives the same result for a rotated list and a non-rotated list, but the answer lies in opposite directions.

"Why high = mid and not mid - 1?" mid might be the smallest number.

"What if the list is not rotated?" It works with no special case. Trace [1, 2, 3] if asked.

"What if numbers can repeat?" On a tie, do high -= 1, and the worst case becomes O(n). Explain why that cannot be avoided.

One thing to volunteer: describe the list as two sorted runs with one drop, and say that the smallest number is exactly at the drop. That picture makes the comparison rule obvious instead of arbitrary.

Next: 4.11.5 Search in Rotated Sorted Array. The same broken list, now asked to find any value in one pass.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet