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

The entire core curriculum of 13 patterns and 225 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.

4. Search in Rotated Sorted Array • Invariant Proof & Speed-Run

Theory Context•Binary Search Boundary

MediumLC 33

Search in Rotated Sorted Array (LeetCode 33)

Target Frequency:MetaAmazonGoogleMicrosoft

Before: arrange the unique integers from smallest to largest.

Change: the list may stay untouched, or undergo a left rotation. A rotation cuts it at an undisclosed position k (1 <= k < nums.length) and moves the prefix behind the suffix without changing the order inside either piece.

Received: nums contains that final arrangement. A cut at 3 takes the prefix [0, 1, 2] off [0, 1, 2, 4, 5, 6, 7] and places it after [4, 5, 6, 7], giving [4, 5, 6, 7, 0, 1, 2]. An unrotated list is also a valid input.

Locate the integer target in the received list. Report its zero-based index if present; report -1 otherwise. The required running time is O(log n), where n is the length of nums.

Worked Examples

Example 1

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

Output:4

Explanation: 0 is at index 4 in the rotated array.

Example 2

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

Output:-1

Explanation: 3 is not in the array.

Example 3

Input:nums = [1], target = 0

Output:-1

Explanation: The array [1] does not contain 0.

⚖️Formal Constraints & Bounds

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Deep-Dive & Conceptual Insights

Core Insight

The first value nums[0] tells which run an index is in, so one Lower Bound finds the pivot. Read from the pivot, the array is sorted, so a second Lower Bound on the positions (pivot + v) % n finds the target.

Real-World Scenario & Production Applications

Ring buffers and circular logs (like distributed event streams) wrap around when full. To find a record by its counter value, you find the oldest entry, the pivot, and then search the sorted order that starts there, both in logarithmic time.

Subproblems & Recurrence Decomposition4 Phases

🧩Subproblem 1: The Pivot Check And The Trim

The first value nums[0] tells which run an index is in: values in the first run are at least nums[0], and values in the second run are smaller. So the check nums[i] < nums[0] is False and then True. Copies of nums[0] at the end of the array look like the first run, so the trim removes them first.

Mathematical Recurrence / Code Invariant

n = len(nums)
hi = n
while hi > 1 and nums[hi - 1] == nums[0]:
    hi -= 1                       # ignore tail copies of nums[0]
def smaller_than_first(i):
    return nums[i] < nums[0]

Step-by-Step Execution Trace Table

Step	Search	Range `[lo, hi)`	mid	Check	Decision	New range `[lo, hi)`
1	Pivot	`[0, 7)`	3	`nums[3] < nums[0]`: `7 < 4` → False	`7` is in the first run, so the pivot is to its right: `lo = mid + 1`	`[4, 7)`
2	Pivot	`[4, 7)`	5	`1 < 4` → True	`1` is in the second run, so keep `mid`: `hi = mid`	`[4, 5)`
3	Pivot	`[4, 5)`	4	`0 < 4` → True	keep `mid`: `hi = mid`	`[4, 4)`
	Pivot	`[4, 4)`			The range is empty, so `pivot = 4 % 7 = 4`.
4	Target	`[0, 7)`	3	position 3 is index `(4 + 3) % 7 = 0`, `nums[0] = 4 >= 0` → True	keep `mid`: `hi = mid`	`[0, 3)`
5	Target	`[0, 3)`	1	index 5, `nums[5] = 1 >= 0` → True	`hi = mid`	`[0, 1)`
6	Target	`[0, 1)`	0	index 4, `nums[4] = 0 >= 0` → True	`hi = mid`	`[0, 0)`
	Target	`[0, 0)`			The range is empty: `v = 0`, index `(4 + 0) % 7 = 4`, `nums[4] == 0`. Return 4.

The trace for nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, step by step:

The array has no repeated values, so the trim does nothing and hi = 7.
Steps 1 to 3 find the pivot: the first index whose value is smaller than nums[0] = 4. It is index 4.
Steps 4 to 6 search the sorted order that starts at index 4. Position 0 is index 4, and it holds 0, the first value that is at least 0.
The look: v < n and nums[4] == 0, so the answer is index 4.

Code Shape

Archetype Code Shape

Python

1	n = len(nums)
2	hi = n
3	while hi > 1 and nums[hi - 1] == nums[0]:
4	hi -= 1
5	pivot = binary_search_lower_bound(0, hi, smaller_than_first) % n
6	v = binary_search_lower_bound(0, n, at_least_target)
7	if v < n and nums[(pivot + v) % n] == target:
8	return (pivot + v) % n
9	return -1

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

A rotated sorted array is a sorted list that was cut at one place and joined again with the two pieces swapped. The first value, nums[0], tells which piece an index is in: the first piece holds values that are at least nums[0], and the second piece holds smaller values. So one Lower Bound search finds the pivot, the start of the sorted order. Then a second Lower Bound search runs on the sorted order that starts at the pivot.

🕰️ The Analogy: A Clock That Was Turned

Imagine the numbers 0 to 11 on a clock face, but someone turned the clock, so the smallest number is not at the top. You can still read the numbers in order: start at the smallest number and go around the face. The pivot is that start. Position v in the sorted order is the number v steps around from the pivot, which is index (pivot + v) % n.

🔑 Why It Works

The pivot is the start of the sorted order, and the map (pivot + v) % n visits every index once, in sorted order. So the check "is the value at position v at least target?" is False and then True, and its first True is where target would be. When values repeat, copies of nums[0] at the end look like the first run, so the trim removes them first. The trim costs O(N) in the worst case, when every value is equal.

Setting pivot = 0 when no value is smaller
Forgetting % n in the position map
Skipping the trim when values repeat
Writing <= instead of < in the pivot check
Returning the position without checking the value
Reading nums[v] instead of nums[(pivot + v) % n]

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

A sorted array was rotated by an unknown amount, and you need a target's index in O(log N) time. That points to Rotated Array: the first value tells which run an index is in.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: read from the pivot, the array is sorted, and position v is index (pivot + v) % n. The check nums[i] < nums[0] is False in the first run and True in the second run, so Lower Bound finds the pivot. The check nums[(pivot + v) % n] >= target is False and then True, so a second Lower Bound finds the target.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Resetting the pivot to 0 when no value is smaller than nums[0]: the first search returns hi, and % n takes it back to an index (nums = [0, 1, 0, 0], target = 1 returns -1 with the reset).
Forgetting % n in the position map: nums[pivot + v] goes past the end of the list and raises an IndexError (nums = [4, 5, 6, 7, 0, 1, 2], target = 0).

The 60-Second Interview Pitch

Say this out loud before you type a single line

"This is Rotated Array. It runs Lower Bound twice. The first value, nums[0], tells me which run an index is in: values in the first run are at least nums[0], and values in the second run are smaller. So the check nums[i] < nums[0] is False and then True, and its first True is the pivot. I take the pivot modulo n, because when no value is smaller the search returns hi. Read from the pivot, the array is sorted, so position v is index (pivot + v) % n. A second Lower Bound finds the first position whose value is at least target, and one look tells me if it is target. If values can repeat, I first ignore the copies of nums[0] at the end of the array. The trap is resetting the pivot to 0 instead of taking it modulo n. That is O(log n) time with distinct values, O(n) worst case with repeated values, and O(1) space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log N)

Look at the two calls of Lower Bound: each runs while lo < hi: and keeps at most half of its range on every pass, so each takes at most ⌊log2 N⌋ + 1 passes with O(1) work per pass. Two searches are O(log N) in total. The trim loop while hi > 1 and nums[hi - 1] == nums[0] does no work when values are distinct, and walks the whole array when every value is equal, so with repeated values the worst case is O(N).

SPACE COMPLEXITY

O(1)

Look at the memory used: both searches are iterative, so the call stack holds a few frames. We store only the integers n, hi, pivot, v, lo and mid. Auxiliary space is O(1).

Formal Recurrence Relation

$T(N) = T(N/2) + O(1) ⟹ O(\log N)$

Derivation Progression

One Comparison per Pass

nums[i] < nums[0] or nums[(pivot + v) % n] >= target

Each pass computes mid and asks one check once: O(1) work per pass.

Window Contraction

lo = mid + 1 or hi = mid

Each search removes half of its remaining candidates per pass.

Convergence

lo == hi ⟹ O(log N)

Halving N candidates down to none takes at most floor(log2 N) + 1 passes, for each of the two searches.

Variable Definitions

$N$

Total number of elements in the rotated sorted array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative while loop with zero recursion frames

🔵 Auxiliary Heap

O(1) Only scalar pointers (lo, hi, mid) in CPU registers

🟢 Output Space

O(1) Returns an index

Boundary Best / Worst Cases

Best Case

$O(\log N)$ for distinct elements: the trim does no work.

Average Case

$O(\log N)$ .

Worst Case

$O(N)$ when every value is equal: the trim loop walks the whole array. With distinct values the worst case is $O(\log N)$ .

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

The statement gives an array "sorted in ascending order with unique values" that was "rotated at an unknown pivot", and asks for a target's index "in O(log n) time". This is Rotated Array: the first value nums[0] tells which run an index is in, so Lower Bound finds the pivot, and a second Lower Bound searches the sorted order that starts there.

CONSTRAINTS & BOUNDS

The array length is $1 \le N \le 5000$ , and all integers are guaranteed unique, so the trim loop does nothing. The first search runs over [0, n) and returns n when no value is smaller than nums[0]; % n takes it back to the pivot 0. The second search runs over the sorted positions [0, n).

FAANG PRODUCTION TRAPS & EDGE CASES

The card's trap is resetting the pivot to 0 when no value is smaller than nums[0]: take it modulo n instead. Another is forgetting % n in the position map. At scale there is one more: if the array is a live circular log that keeps being written while you search, the wrap point moves between reads, so search a snapshot (or hold the writers off) or the answer can land on a record that is no longer the oldest.

Theory Context•Binary Search Boundary

MediumLC 33

Search in Rotated Sorted Array (LeetCode 33)

Target Frequency:MetaAmazonGoogleMicrosoft

Before: arrange the unique integers from smallest to largest.

Locate the integer target in the received list. Report its zero-based index if present; report -1 otherwise. The required running time is O(log n), where n is the length of nums.

Worked Examples

Example 1

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

Output:4

Explanation: 0 is at index 4 in the rotated array.

Example 2

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

Output:-1

Explanation: 3 is not in the array.

Example 3

Input:nums = [1], target = 0

Output:-1

Explanation: The array [1] does not contain 0.

⚖️Formal Constraints & Bounds

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Subproblems & Recurrence Decomposition4 Phases

🧩Subproblem 1: The Pivot Check And The Trim

Mathematical Recurrence / Code Invariant

n = len(nums)
hi = n
while hi > 1 and nums[hi - 1] == nums[0]:
    hi -= 1                       # ignore tail copies of nums[0]
def smaller_than_first(i):
    return nums[i] < nums[0]

Step-by-Step Execution Trace Table

Step	Search	Range `[lo, hi)`	mid	Check	Decision	New range `[lo, hi)`
1	Pivot	`[0, 7)`	3	`nums[3] < nums[0]`: `7 < 4` → False	`7` is in the first run, so the pivot is to its right: `lo = mid + 1`	`[4, 7)`
2	Pivot	`[4, 7)`	5	`1 < 4` → True	`1` is in the second run, so keep `mid`: `hi = mid`	`[4, 5)`
3	Pivot	`[4, 5)`	4	`0 < 4` → True	keep `mid`: `hi = mid`	`[4, 4)`
	Pivot	`[4, 4)`			The range is empty, so `pivot = 4 % 7 = 4`.
4	Target	`[0, 7)`	3	position 3 is index `(4 + 3) % 7 = 0`, `nums[0] = 4 >= 0` → True	keep `mid`: `hi = mid`	`[0, 3)`
5	Target	`[0, 3)`	1	index 5, `nums[5] = 1 >= 0` → True	`hi = mid`	`[0, 1)`
6	Target	`[0, 1)`	0	index 4, `nums[4] = 0 >= 0` → True	`hi = mid`	`[0, 0)`
	Target	`[0, 0)`			The range is empty: `v = 0`, index `(4 + 0) % 7 = 4`, `nums[4] == 0`. Return 4.

The trace for nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, step by step:

The array has no repeated values, so the trim does nothing and hi = 7.
Steps 1 to 3 find the pivot: the first index whose value is smaller than nums[0] = 4. It is index 4.
Steps 4 to 6 search the sorted order that starts at index 4. Position 0 is index 4, and it holds 0, the first value that is at least 0.
The look: v < n and nums[4] == 0, so the answer is index 4.

Code Shape

Archetype Code Shape

Python

1	n = len(nums)
2	hi = n
3	while hi > 1 and nums[hi - 1] == nums[0]:
4	hi -= 1
5	pivot = binary_search_lower_bound(0, hi, smaller_than_first) % n
6	v = binary_search_lower_bound(0, n, at_least_target)
7	if v < n and nums[(pivot + v) % n] == target:
8	return (pivot + v) % n
9	return -1

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🕰️ The Analogy: A Clock That Was Turned

🔑 Why It Works

Setting pivot = 0 when no value is smaller
Forgetting % n in the position map
Skipping the trim when values repeat
Writing <= instead of < in the pivot check
Returning the position without checking the value
Reading nums[v] instead of nums[(pivot + v) % n]

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

A sorted array was rotated by an unknown amount, and you need a target's index in O(log N) time. That points to Rotated Array: the first value tells which run an index is in.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Resetting the pivot to 0 when no value is smaller than nums[0]: the first search returns hi, and % n takes it back to an index (nums = [0, 1, 0, 0], target = 1 returns -1 with the reset).
Forgetting % n in the position map: nums[pivot + v] goes past the end of the list and raises an IndexError (nums = [4, 5, 6, 7, 0, 1, 2], target = 0).

The 60-Second Interview Pitch

Say this out loud before you type a single line

"This is Rotated Array. It runs Lower Bound twice. The first value, nums[0], tells me which run an index is in: values in the first run are at least nums[0], and values in the second run are smaller. So the check nums[i] < nums[0] is False and then True, and its first True is the pivot. I take the pivot modulo n, because when no value is smaller the search returns hi. Read from the pivot, the array is sorted, so position v is index (pivot + v) % n. A second Lower Bound finds the first position whose value is at least target, and one look tells me if it is target. If values can repeat, I first ignore the copies of nums[0] at the end of the array. The trap is resetting the pivot to 0 instead of taking it modulo n. That is O(log n) time with distinct values, O(n) worst case with repeated values, and O(1) space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(log N)

SPACE COMPLEXITY

O(1)

Look at the memory used: both searches are iterative, so the call stack holds a few frames. We store only the integers n, hi, pivot, v, lo and mid. Auxiliary space is O(1).

Formal Recurrence Relation

$T(N) = T(N/2) + O(1) ⟹ O(\log N)$

Derivation Progression

One Comparison per Pass

nums[i] < nums[0] or nums[(pivot + v) % n] >= target

Each pass computes mid and asks one check once: O(1) work per pass.

Window Contraction

lo = mid + 1 or hi = mid

Each search removes half of its remaining candidates per pass.

Convergence

lo == hi ⟹ O(log N)

Halving N candidates down to none takes at most floor(log2 N) + 1 passes, for each of the two searches.

Variable Definitions

$N$

Total number of elements in the rotated sorted array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative while loop with zero recursion frames

🔵 Auxiliary Heap

O(1) Only scalar pointers (lo, hi, mid) in CPU registers

🟢 Output Space

O(1) Returns an index

Boundary Best / Worst Cases

Best Case

$O(\log N)$ for distinct elements: the trim does no work.

Average Case

$O(\log N)$ .

Worst Case

$O(N)$ when every value is equal: the trim loop walks the whole array. With distinct values the worst case is $O(\log N)$ .

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Step

Search

Range [lo, hi)

mid

Check

Decision

New range [lo, hi)

Pivot

[0, 7)

nums[3] < nums[0]: 7 < 4 → False

7 is in the first run, so the pivot is to its right: lo = mid + 1

[4, 7)

Pivot

[4, 7)

1 < 4 → True

1 is in the second run, so keep mid: hi = mid

[4, 5)

Pivot

[4, 5)

0 < 4 → True

keep mid: hi = mid

[4, 4)

Pivot

[4, 4)

The range is empty, so pivot = 4 % 7 = 4.

Target

[0, 7)

position 3 is index (4 + 3) % 7 = 0, nums[0] = 4 >= 0 → True

keep mid: hi = mid

[0, 3)

Target

[0, 3)

index 5, nums[5] = 1 >= 0 → True

hi = mid

[0, 1)

Target

[0, 1)

index 4, nums[4] = 0 >= 0 → True

hi = mid

[0, 0)

Target

[0, 0)

The range is empty: v = 0, index (4 + 0) % 7 = 4, nums[4] == 0. Return 4.

🧭 Conceptual Foundation & Pattern Intuition

🕰️ The Analogy: A Clock That Was Turned

🔑 Why It Works

Step

Search

Range [lo, hi)

mid

Check

Decision

New range [lo, hi)

Pivot

[0, 7)

nums[3] < nums[0]: 7 < 4 → False

7 is in the first run, so the pivot is to its right: lo = mid + 1

[4, 7)

Pivot

[4, 7)

1 < 4 → True

1 is in the second run, so keep mid: hi = mid

[4, 5)

Pivot

[4, 5)

0 < 4 → True

keep mid: hi = mid

[4, 4)

Pivot

[4, 4)

The range is empty, so pivot = 4 % 7 = 4.

Target

[0, 7)

position 3 is index (4 + 3) % 7 = 0, nums[0] = 4 >= 0 → True

keep mid: hi = mid

[0, 3)

Target

[0, 3)

index 5, nums[5] = 1 >= 0 → True

hi = mid

[0, 1)

Target

[0, 1)

index 4, nums[4] = 0 >= 0 → True

hi = mid

[0, 0)

Target

[0, 0)

The range is empty: v = 0, index (4 + 0) % 7 = 4, nums[4] == 0. Return 4.