What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 191 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

14. Rotated Array with Duplicates: Find Minimum in Rotated Sorted Array II (LC 154) • Invariant Proof & Speed-Run

Theory Context•Binary Search Boundary

HardLC 154

Find Minimum in Rotated Sorted Array II (LeetCode 154)

You will see why a tie between nums[mid] and nums[hi] cannot pick a side once values repeat, and the one-index move that keeps the search correct.

nums holds n integers. It started out sorted from smallest to largest, with repeats allowed, and was then rotated between 1 and n times; each rotation takes the last value and puts it at the front. So [0,1,4,4,5,6,7] turns into [4,5,6,7,0,1,4] after 4 rotations, and back into itself after 7.

Find the smallest value in nums, in as few steps as you can.

Follow-up: without repeated values this is Find Minimum in Rotated Sorted Array (LC 153). Can repeats change how fast you can go, and why?

Worked Examples

Example 1

Input:nums = [1,3,5]

Output:1

Explanation: Rotated 3 times, which is `n` times, the array is back in sorted order, so the smallest value is the first one.

Example 2

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

Output:0

Explanation: The values drop from `2` to `0` between indices 2 and 3; `0` is the smallest value.

⚖️Formal Constraints & Bounds

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

nums[mid] > nums[hi] puts mid in the left run, so the minimum is strictly to its right; nums[mid] < nums[hi] puts mid and hi in one sorted run, so the minimum is mid or to its left. A tie can happen in either run, so it only drops hi: nums[mid] has the same value and stays in range, so the minimum value is never lost.

Real-World Scenario & Production Applications

A fixed-size ring buffer that stores a rising daily count overwrites its oldest slot and keeps going, so read from slot 0 it is a sorted array rotated at the write position, and the oldest entry is where the smallest count starts. When a count stays flat for days, equal values sit on both sides of the write position, and one comparison can no longer say which side a probe landed on.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Which Run Is `mid` In?

A rotated sorted array is two sorted runs. nums[mid] > nums[hi] puts mid in the left run, so the minimum is strictly to its right; nums[mid] < nums[hi] puts mid in the right run, so the minimum is mid or to its left.

Mathematical Recurrence / Code Invariant

if nums[mid] > nums[hi]:
    lo = mid + 1
elif nums[mid] < nums[hi]:
    hi = mid

Step-by-Step Execution Trace Table

Trace for the trap input nums = [3,1,3,3,3] (not a LeetCode example: neither LeetCode example ever ties).

Step	`[lo, hi]`	`mid`	`nums[mid]` vs `nums[hi]`	Action
1	`[0, 4]`	2	`3 == 3`, a tie	`hi -= 1`, so `hi = 3` (with `>=` folded into the first branch, `lo = 3` would jump past the `1` at index 1)
2	`[0, 3]`	1	`1 < 3`	`hi = mid = 1`
3	`[0, 1]`	0	`3 > 1`	`lo = mid + 1 = 1`
4	`[1, 1]`		`lo == hi`	Return `nums[1] = 1`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	A rotated sorted array is two sorted runs: compare `nums[mid]` with `nums[hi]` to learn which run `mid` is in, and move toward the drop.
2	Keep the minimum value inside `[lo, hi]`: `nums[mid] > nums[hi]` means `lo = mid + 1`; `nums[mid] < nums[hi]` means `hi = mid`.
3	`lo, hi = 0, len(nums) - 1`; `while lo < hi:` take `mid = lo + (hi - lo) // 2`, branch three ways on `nums[mid]` against `nums[hi]`; `return nums[lo]` after the loop.
4	The trap: a tie, `nums[mid] == nums[hi]`, gets its own branch, `hi -= 1`. Folding it into `>` (`lo = mid + 1`) jumps past the `1` in `[3, 1, 3, 3, 3]`.

Target: Find Minimum in Rotated Sorted Array II (LeetCode 154). Every index may hold the minimum.

Boundary Model: Closed Candidate Interval [L, R]

Both L and R are inclusive valid indices. When condition matches or fails, candidate space shrinks by setting lo = mid + 1 or hi = mid - 1 symmetrically.

Loop Invariant Termination

while (lo <= hi) with mid = lo + (hi - lo) // 2.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Rotated Array finds the minimum by comparing nums[mid] with nums[hi]: bigger means mid is in the left run, smaller means it is in the right run. That works because, with distinct values, every value in the left run is bigger than every value in the right run. Repeated values break the "bigger" part: a value in the left run can now equal a value in the right run, so nums[mid] == nums[hi] can happen with mid in either run. [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1] both tie at mid = 2, and their minimums sit on opposite sides.

🔦 The Analogy: Two Identical Street Signs

You walk a road that loops back on itself and want the lowest house number. Normally the sign at the end of the road tells you whether you are before or after the loop point. But if the sign in front of you reads exactly what the end sign reads, you cannot tell which stretch you are on. You do not guess: you cross out the end sign, because the sign in front of you still shows the same number, and ask again with the next one.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1   # left run: the minimum is strictly to the right
    elif nums[mid] < nums[hi]:
        hi = mid       # right run: mid may be the minimum
    else:
        hi -= 1        # tie: drop one index; a copy of nums[hi] stays at mid
return nums[lo]

The tie branch keeps the invariant: the minimum value is always held by some index in [lo, hi]. If nums[hi] was the minimum, nums[mid] has the same value and mid < hi is still in range, so dropping hi loses nothing. The price is speed: a tie removes one index instead of half, so an array full of equal values takes n - 1 steps.

💡 Summary

Keep Rotated Array's two strict branches and give the tie its own branch, hi -= 1. Never fold the tie into > or <: either way you can throw away the minimum. $O(\log n)$ without ties, $O(n)$ in the worst case (which no algorithm can beat), $O(1)$ space.

The tie folded into >: Give the tie its own branch, else: hi -= 1, never fold it into a strict one: with if nums[mid] >= nums[hi]: lo = mid + 1, [3, 1, 3, 3, 3] ties at mid = 2 and lo jumps to 3, past the 1 at index 1.
hi = mid on a tie: hi -= 1, not hi = mid, on a tie: keeping hi = mid from Rotated Array is just as blind. In [1, 1, 1, 0, 1] the tie at mid = 2 would cut off the 0 at index 3.
Expecting O(log n) every time: A tie drops one index, not half, so ties can make the worst case O(n), as with all values equal. No algorithm does better: 1s with one 0 at any index, such as [1, 1, 1, 1, 1, 0, 1], are all valid inputs, and until you read the 0 every value you have not read could be it.
Search needs both ends: The same tie blocks Search in Rotated Sorted Array II (LC 81): when nums[lo] == nums[mid] == nums[hi] neither half can be proven sorted, so shrink both ends with lo += 1 and hi -= 1. That is safe because the line before has already returned when nums[mid] == target, so both ends, equal to it, are not the target.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer hears 'with repeats allowed' in a rotated-array problem and adds one branch before writing the loop.

Pattern Recognition Signals

The 10-second spot

"Sorted from smallest to largest" and "rotated between 1 and n times" describe a rotated sorted array: two sorted runs with one drop, which is Rotated Array. "With repeats allowed" is what makes this card: equal values can sit at mid and at hi in either run, so the usual comparison needs a third case. "In as few steps as you can" rules out a plain scan when no ties get in the way.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

The minimum value of nums is always held by some index in [lo, hi]. nums[mid] > nums[hi] means lo = mid + 1; nums[mid] < nums[hi] means hi = mid; a tie means hi -= 1, because nums[mid] holds the same value as nums[hi] and stays in range.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Give the tie its own branch, else: hi -= 1: with if nums[mid] >= nums[hi]: lo = mid + 1, [3, 1, 3, 3, 3] ties at mid = 2 and lo jumps to 3, past the 1 at index 1.
hi -= 1, not hi = mid, on a tie: in [1, 1, 1, 0, 1] the tie at mid = 2 would cut off the 0 at index 3.
Compare with nums[hi], not nums[lo]: an array rotated n times is fully sorted, and nums[mid] >= nums[lo] there would walk away from the minimum at index 0 (Example 1).
hi = mid, not hi = mid - 1, when nums[mid] < nums[hi]: mid may be the minimum itself. On [3, 1, 3, 3, 3], after the tie, mid = 1 holds the 1, and hi = mid - 1 would drop it.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Rotated Array with Duplicates. A rotated sorted array is two sorted runs, and comparing nums at mid with nums at hi usually tells me which run mid is in: bigger means the minimum is to the right, so lo becomes mid plus one; smaller means mid may be the minimum, so hi becomes mid. With repeats there's a third case, a tie, and a tie says nothing: mid could be in either run. So on a tie I only drop hi by one. That's safe, because nums at mid holds the same value, so if hi held the minimum a copy survives at mid. The trap I avoid is folding the tie into the bigger branch: on three, one, three, three, three that jumps past the one. It's O(log n) without ties and O(n) in the worst case, which no algorithm can beat, with O(1) space.

So: spot the repeats, give the tie its own hi -= 1 branch, and say out loud why the worst case is O(n) and why nothing beats it.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log n) without ties, O(n) worst case

Look at the code: every pass of while lo < hi does one comparison of nums[mid] with nums[hi] and then moves one end. The strict branches lo = mid + 1 and hi = mid remove about half of [lo, hi], so a run with no tie takes about log2(n) passes. The tie branch hi -= 1 removes one index, so each pass still removes at least one index, and there are at most n - 1 passes: O(n). That bound is reached, for example, when every value is equal: every pass ties. And it cannot be beaten: 1s with one 0 at any index, such as [1, 1, 1, 1, 1, 0, 1], are all valid inputs, and until an algorithm reads the 0 every value it has not read could be it, so in the worst case it must read all n values.

SPACE COMPLEXITY

O(1)

The code keeps lo, hi and mid, whatever the length of nums, and returns one value. There is no recursion and no copy of the array, so the extra space is O(1).

Formal Recurrence Relation

T(n) = T(n / 2) + O(1) = O(log n) on a strict comparison; T(n) = T(n - 1) + O(1) = O(n) when every comparison ties

Derivation Progression

Setup

O(1)

lo, hi = 0, len(nums) - 1 is constant work.

One pass

O(1)

One midpoint, one comparison of nums[mid] with nums[hi], one move of lo or hi.

Strict comparison

halves [lo, hi]

lo = mid + 1 or hi = mid keeps about half of the range, so passes without a tie add up to about log2(n).

Tie

removes 1 index

hi -= 1 shrinks the range by one, so at most n - 1 passes in all: O(n) when ties keep coming, as with all values equal.

Lower bound

Ω(n) for any algorithm

With 1s and one hidden 0, every unread index could hold the 0, so no algorithm can promise fewer than n reads.

Variable Definitions

$n$

The length of nums

$hi - lo + 1$

The number of indices still in range; every pass removes at least one

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion

🔵 Auxiliary Heap

O(1): lo, hi, mid

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(\log n)$ : no comparison ties, as in Example 2, so every pass halves the range

Average Case

$O(\log n)$ plus one pass per tie

Worst Case

$O(n)$ : every comparison ties, as when all values are equal, and each pass drops one index

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "sorted from smallest to largest, with repeats allowed" and "rotated between 1 and n times": a rotated sorted array whose values can repeat. That is Rotated Array with Duplicates: Rotated Array's comparison of nums[mid] with nums[hi], plus a tie branch, hi -= 1.

CONSTRAINTS & BOUNDS

$n \le 5000$ and $-5000 \le$ nums[i] $\le 5000$ . Budget: $O(\log n)$ comparisons when no tie occurs, at most $n - 1 = 4999$ when ties keep coming, and $O(1)$ space. No algorithm can promise fewer than $n$ reads on these inputs, so the worst case is already optimal.

FAANG PRODUCTION TRAPS & EDGE CASES

The worst case is the thing to plan for at scale: a long flat stretch of equal values turns a handful of probes into a walk over the whole stretch, and a tie gives no hint of how long the stretch is. When every probe is an expensive read (a disk block, a remote call), data with many repeats can make one sequential scan cheaper than many scattered probes; with few repeats the search stays near $\log_2 n$ probes.

Core Algorithmic State Invariants

Two Runs, Compared at hi

A rotated sorted array is two sorted runs. nums[mid] > nums[hi] puts mid in the left run (lo = mid + 1); nums[mid] < nums[hi] puts it in the right run (hi = mid).

A Tie Picks No Side

With repeats, nums[mid] == nums[hi] happens in either run. Drop only hi with hi -= 1: nums[mid] holds the same value, so the minimum value stays inside [lo, hi].

One Index per Tie

Strict comparisons halve the range, a tie removes one index: O(log n) without ties, O(n) worst case, which no algorithm can beat. O(1) space.

Theory Context•Binary Search Boundary

HardLC 154

Find Minimum in Rotated Sorted Array II (LeetCode 154)

You will see why a tie between nums[mid] and nums[hi] cannot pick a side once values repeat, and the one-index move that keeps the search correct.

Find the smallest value in nums, in as few steps as you can.

Follow-up: without repeated values this is Find Minimum in Rotated Sorted Array (LC 153). Can repeats change how fast you can go, and why?

Worked Examples

Example 1

Input:nums = [1,3,5]

Output:1

Explanation: Rotated 3 times, which is `n` times, the array is back in sorted order, so the smallest value is the first one.

Example 2

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

Output:0

Explanation: The values drop from `2` to `0` between indices 2 and 3; `0` is the smallest value.

⚖️Formal Constraints & Bounds

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Which Run Is `mid` In?

Mathematical Recurrence / Code Invariant

if nums[mid] > nums[hi]:
    lo = mid + 1
elif nums[mid] < nums[hi]:
    hi = mid

Step-by-Step Execution Trace Table

Trace for the trap input nums = [3,1,3,3,3] (not a LeetCode example: neither LeetCode example ever ties).

Step	`[lo, hi]`	`mid`	`nums[mid]` vs `nums[hi]`	Action
1	`[0, 4]`	2	`3 == 3`, a tie	`hi -= 1`, so `hi = 3` (with `>=` folded into the first branch, `lo = 3` would jump past the `1` at index 1)
2	`[0, 3]`	1	`1 < 3`	`hi = mid = 1`
3	`[0, 1]`	0	`3 > 1`	`lo = mid + 1 = 1`
4	`[1, 1]`		`lo == hi`	Return `nums[1] = 1`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	A rotated sorted array is two sorted runs: compare `nums[mid]` with `nums[hi]` to learn which run `mid` is in, and move toward the drop.
2	Keep the minimum value inside `[lo, hi]`: `nums[mid] > nums[hi]` means `lo = mid + 1`; `nums[mid] < nums[hi]` means `hi = mid`.
3	`lo, hi = 0, len(nums) - 1`; `while lo < hi:` take `mid = lo + (hi - lo) // 2`, branch three ways on `nums[mid]` against `nums[hi]`; `return nums[lo]` after the loop.
4	The trap: a tie, `nums[mid] == nums[hi]`, gets its own branch, `hi -= 1`. Folding it into `>` (`lo = mid + 1`) jumps past the `1` in `[3, 1, 3, 3, 3]`.

Target: Find Minimum in Rotated Sorted Array II (LeetCode 154). Every index may hold the minimum.

Boundary Model: Closed Candidate Interval [L, R]

Both L and R are inclusive valid indices. When condition matches or fails, candidate space shrinks by setting lo = mid + 1 or hi = mid - 1 symmetrically.

Loop Invariant Termination

while (lo <= hi) with mid = lo + (hi - lo) // 2.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🔦 The Analogy: Two Identical Street Signs

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1   # left run: the minimum is strictly to the right
    elif nums[mid] < nums[hi]:
        hi = mid       # right run: mid may be the minimum
    else:
        hi -= 1        # tie: drop one index; a copy of nums[hi] stays at mid
return nums[lo]

💡 Summary

The tie folded into >: Give the tie its own branch, else: hi -= 1, never fold it into a strict one: with if nums[mid] >= nums[hi]: lo = mid + 1, [3, 1, 3, 3, 3] ties at mid = 2 and lo jumps to 3, past the 1 at index 1.
hi = mid on a tie: hi -= 1, not hi = mid, on a tie: keeping hi = mid from Rotated Array is just as blind. In [1, 1, 1, 0, 1] the tie at mid = 2 would cut off the 0 at index 3.
Expecting O(log n) every time: A tie drops one index, not half, so ties can make the worst case O(n), as with all values equal. No algorithm does better: 1s with one 0 at any index, such as [1, 1, 1, 1, 1, 0, 1], are all valid inputs, and until you read the 0 every value you have not read could be it.
Search needs both ends: The same tie blocks Search in Rotated Sorted Array II (LC 81): when nums[lo] == nums[mid] == nums[hi] neither half can be proven sorted, so shrink both ends with lo += 1 and hi -= 1. That is safe because the line before has already returned when nums[mid] == target, so both ends, equal to it, are not the target.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer hears 'with repeats allowed' in a rotated-array problem and adds one branch before writing the loop.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Give the tie its own branch, else: hi -= 1: with if nums[mid] >= nums[hi]: lo = mid + 1, [3, 1, 3, 3, 3] ties at mid = 2 and lo jumps to 3, past the 1 at index 1.
hi -= 1, not hi = mid, on a tie: in [1, 1, 1, 0, 1] the tie at mid = 2 would cut off the 0 at index 3.
Compare with nums[hi], not nums[lo]: an array rotated n times is fully sorted, and nums[mid] >= nums[lo] there would walk away from the minimum at index 0 (Example 1).
hi = mid, not hi = mid - 1, when nums[mid] < nums[hi]: mid may be the minimum itself. On [3, 1, 3, 3, 3], after the tie, mid = 1 holds the 1, and hi = mid - 1 would drop it.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Rotated Array with Duplicates. A rotated sorted array is two sorted runs, and comparing nums at mid with nums at hi usually tells me which run mid is in: bigger means the minimum is to the right, so lo becomes mid plus one; smaller means mid may be the minimum, so hi becomes mid. With repeats there's a third case, a tie, and a tie says nothing: mid could be in either run. So on a tie I only drop hi by one. That's safe, because nums at mid holds the same value, so if hi held the minimum a copy survives at mid. The trap I avoid is folding the tie into the bigger branch: on three, one, three, three, three that jumps past the one. It's O(log n) without ties and O(n) in the worst case, which no algorithm can beat, with O(1) space.

So: spot the repeats, give the tie its own hi -= 1 branch, and say out loud why the worst case is O(n) and why nothing beats it.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log n) without ties, O(n) worst case

SPACE COMPLEXITY

O(1)

The code keeps lo, hi and mid, whatever the length of nums, and returns one value. There is no recursion and no copy of the array, so the extra space is O(1).

Formal Recurrence Relation

T(n) = T(n / 2) + O(1) = O(log n) on a strict comparison; T(n) = T(n - 1) + O(1) = O(n) when every comparison ties

Derivation Progression

Setup

O(1)

lo, hi = 0, len(nums) - 1 is constant work.

One pass

O(1)

One midpoint, one comparison of nums[mid] with nums[hi], one move of lo or hi.

Strict comparison

halves [lo, hi]

lo = mid + 1 or hi = mid keeps about half of the range, so passes without a tie add up to about log2(n).

Tie

removes 1 index

hi -= 1 shrinks the range by one, so at most n - 1 passes in all: O(n) when ties keep coming, as with all values equal.

Lower bound

Ω(n) for any algorithm

With 1s and one hidden 0, every unread index could hold the 0, so no algorithm can promise fewer than n reads.

Variable Definitions

$n$

The length of nums

$hi - lo + 1$

The number of indices still in range; every pass removes at least one

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion

🔵 Auxiliary Heap

O(1): lo, hi, mid

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(\log n)$ : no comparison ties, as in Example 2, so every pass halves the range

Average Case

$O(\log n)$ plus one pass per tie

Worst Case

$O(n)$ : every comparison ties, as when all values are equal, and each pass drops one index

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Two Runs, Compared at hi

A rotated sorted array is two sorted runs. nums[mid] > nums[hi] puts mid in the left run (lo = mid + 1); nums[mid] < nums[hi] puts it in the right run (hi = mid).

A Tie Picks No Side

With repeats, nums[mid] == nums[hi] happens in either run. Drop only hi with hi -= 1: nums[mid] holds the same value, so the minimum value stays inside [lo, hi].

One Index per Tie

Strict comparisons halve the range, a tie removes one index: O(log n) without ties, O(n) worst case, which no algorithm can beat. O(1) space.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: FIND MINIMUM IN ROTATED SORTED ARRAY II (LEETCODE 154)

T = O(log n) without ties, O(n) worst caseS = O(1)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
lo, hi = 0, len(nums) - 1	`lo, hi = 0, len(nums) - 1`	Every index may hold the minimum.
while lo < hi:	`while lo < hi:`	Stop when one index is left: the invariant says it holds the minimum value.
if nums[mid] > nums[hi]: lo = mid + 1	`if nums[mid] > nums[hi]: lo = mid + 1`	`mid` is bigger than a value to its right, so it is in the left run and the minimum is strictly to its right.
elif nums[mid] < nums[hi]: hi = mid	`elif nums[mid] < nums[hi]: hi = mid`	`mid` and `hi` are in the same sorted run, so the minimum is `mid` or to its left; `mid` must stay.
else: hi -= 1	`else: hi -= 1`	A tie cannot say which run `mid` is in. Drop only `hi`: `nums[mid]` holds the same value, so the minimum value is still in range.
return nums[lo]	`return nums[lo]`	`lo == hi` is the one index left, and it holds the minimum value.

Step

[lo, hi]

mid

nums[mid] vs nums[hi]

Action

[0, 4]

3 == 3, a tie

hi -= 1, so hi = 3 (with >= folded into the first branch, lo = 3 would jump past the 1 at index 1)

[0, 3]

1 < 3

hi = mid = 1

[0, 1]

3 > 1

lo = mid + 1 = 1

[1, 1]

lo == hi

Return nums[1] = 1

while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] > nums[hi]: lo = mid + 1 # left run: the minimum is strictly to the right elif nums[mid] < nums[hi]: hi = mid # right run: mid may be the minimum else: hi -= 1 # tie: drop one index; a copy of nums[hi] stays at mid return nums[lo]

Step

[lo, hi]

mid

nums[mid] vs nums[hi]

Action

[0, 4]

3 == 3, a tie

hi -= 1, so hi = 3 (with >= folded into the first branch, lo = 3 would jump past the 1 at index 1)

[0, 3]

1 < 3

hi = mid = 1

[0, 1]

3 > 1

lo = mid + 1 = 1

[1, 1]

lo == hi

Return nums[1] = 1

Canonical Invariant

Concrete Code

Engineering Rationale

lo, hi = 0, len(nums) - 1

lo, hi = 0, len(nums) - 1

Every index may hold the minimum.

while lo < hi:

while lo < hi:

Stop when one index is left: the invariant says it holds the minimum value.

if nums[mid] > nums[hi]: lo = mid + 1

if nums[mid] > nums[hi]:
    lo = mid + 1

`mid` is bigger than a value to its right, so it is in the left run and the minimum is strictly to its right.

elif nums[mid] < nums[hi]: hi = mid

elif nums[mid] < nums[hi]:
    hi = mid

`mid` and `hi` are in the same sorted run, so the minimum is `mid` or to its left; `mid` must stay.

else: hi -= 1

else:
    hi -= 1

A tie cannot say which run `mid` is in. Drop only `hi`: `nums[mid]` holds the same value, so the minimum value is still in range.

return nums[lo]

return nums[lo]

`lo == hi` is the one index left, and it holds the minimum value.