Medium · Binary search · spoken drill
Free AI LeetCode Communication Coach — Search in Rotated Sorted Array
Rotated sorted array: at mid, one side is sorted — decide which half can hold the target.
The problem
nums is sorted then rotated. Search for target in O(log n). Return index or -1.
Example: nums = [4,5,6,7,0,1,2], target = 0 → 4
Sorted-half decision is the key sentence.
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1How to explain it
1. Restate
Say the problem in your own words.
One or two sentences. Show you understood the input, the output, and the goal — not that you memorised the prompt.
2. Approach
Name the method before you code.
Brute force first if you need it, then the structure you will use: hash map, two pointers, stack, binary search.
3. Example
Walk one concrete input.
Pick small numbers. Say what you store, what you compare, and what you return. Interviewers follow an example more easily than abstract talk.
4. Time and space
One sentence each.
After the example, before you claim you are done. “Time is O(n) because we scan once. Space is O(n) for the map.”
5. Edge cases
Name at least one unusual input.
Empty input, duplicates, already sorted, overflow. Invite a follow-up: “I would also check …”
- “I check which half is sorted.”
- “Then I ask if the target is inside that range.”
Practise out loud
3 free scored runs left this hour.
Problem · Medium
nums is sorted then rotated. Search for target in O(log n). Return index or -1.
Example: nums = [4,5,6,7,0,1,2], target = 0 → 4
- 1Restate — Say the problem in your own words.
- 2Approach — Name the method before you code.
- 3Example — Walk one concrete input.
- 4Time and space — One sentence each.
- 5Edge cases — Name at least one unusual input.
Hit record. Short countdown, then 60–90 seconds. We score the five-step script — never pronunciation.
Recording needs Chrome or Edge. You can still type below.
Model spoken script (~75s)
1. Restate
The sorted array was rotated. I still need the index of target in logarithmic time.
2. Approach
I binary search, but at mid I check which half is sorted. Then I see if the target lies in that sorted half; otherwise I search the other half.
3. Example
On 4,5,6,7,0,1,2 target 0 — mid might be 7; the right half is not fully sorted, the left is. Target is not in 4..7, so I search right and find 0.
4. Time and space
Time is O(log n). Space is O(1).
5. Edge cases
I would check a non-rotated array and a single-element array.
How to explain Search in Rotated Sorted Array out loud, step by step
In one sentence: A sorted list of distinct numbers has been cut at an unknown point and the two parts swapped, and you must still find a value's position in logarithmic time.
What to say, in order
- “The array was sorted and then rotated, so it's two sorted runs back to back, and I need O(log n), which means binary search.”
- “The key fact is that when I split at mid, at least one half is still fully sorted.”
- “I check which one: if the value at low is less than or equal to the value at mid, the left half is sorted. Otherwise the right half is.”
- “If the left half is sorted and the target is between the value at low and the value at mid, I search left. Otherwise I search right.”
- “If the right half is sorted and the target is between the value at mid and the value at high, I search right. Otherwise I search left.”
- “I repeat until I find the target or the range is empty, and then I return minus one.”
Key English phrases for Search in Rotated Sorted Array
- rotated at a pivot
- — the point where the order 'wraps around'
- the sorted half
- — the side of mid whose values are in order
- falls within the range
- — the target lies between that half's endpoints
- two sorted runs
- — a plain way to describe the rotated array
- discard the other half
- — what you do once you know where the target can't be
How to say the time and space complexity
“Time is O(log n), because every step still throws away half of the range. Space is O(1), since I only keep low, high and mid.”
Mention that this relies on the values being distinct; that sets up the duplicates follow-up.
Communication mistakes on Search in Rotated Sorted Array
- Mistake: Saying 'I find the pivot first' and then never explaining how. Instead: Either describe the one-pass 'which half is sorted' check or the two-pass pivot search clearly — not a mix.
- Mistake: Saying 'the target is on the left' without the range check. Instead: Say 'the left half is sorted, and the target is between its first value and mid, so I go left.'
- Mistake: Using 'rotated' and 'reversed' as if they mean the same thing. Instead: Rotated means shifted around; reversed means descending. Use 'rotated'.
Likely follow-up questions
Interviewer: “What if the array can contain duplicates?”
You: “When the values at low, mid and high are all equal, I can't tell which half is sorted, so I shrink the range by one from each side. That makes the worst case O(n), for example when almost every value is the same.”
Interviewer: “How would you find the minimum element instead?”
You: “Binary search comparing mid with high: if the value at mid is greater than the value at high, the minimum is to the right of mid; otherwise it's at mid or to the left. O(log n).”
Common mistakes when explaining Search in Rotated Sorted Array
- Not saying which half is sorted.
- Treating it as plain binary search without the rotation case.
Other problems
Easy · Hash map
Two Sum
Classic hash-map scan. Name brute force, then the map, walk [2,7,11,15] target 9, finish with O(n).
Medium · Hash map
Group Anagrams
Group strings by anagram signature — sorted key or 26-letter count — then walk one bucket.
Easy · Two pointers
Valid Palindrome
Two pointers from both ends; skip junk characters; compare lowercase letters.
Medium · Two pointers
3Sum
Sort, fix i, then two pointers for the pair that sums to −nums[i]. Deduplicate out loud.
Medium · Sliding window
Longest Substring Without Repeating Characters
Grow a window; when a duplicate appears, move the left edge past its last index.
Easy · Stack
Valid Parentheses
Stack story: push openers, pop on matching closer, empty stack at the end.
FAQ
Questions
More questions? Email us at contact@mocklyenglish.com.
Course: How to explain a LeetCode solution · Think out loud · Explain code out loud