Minimum in Rotated Sorted Array
MediumTake the min of the sorted half
The smallest number is where the list wraps around; halve toward the dip.
The idea
Whichever half of mid is sorted contributes its smallest element; discard it and keep searching the other half for a smaller candidate.
4
5
6
7
0
1
2
0
1
2
3
4
5
6
min4
Step 1 of 8. Brute force: scan the whole array, remembering the smallest. Values: 4, 5, 6, 7, 0, 1, 2. min 4.
1/8
Brute force
timeO(n)spaceO(1)
Scan for the min.
1let min = nums[0];2for (let i = 1; i < n; i++)3 if (nums[i] < min) min = nums[i];4return min;Input
- array
- [4, 5, 6, 7, 0, 1, 2]
Memory
- i
- —
Output
- min
- 4
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [3, 4, 5, 1, 2]
- Output:
- 1
- Explanation:
- The rotation point holds the min, 1.
Example 2
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2]
- Output:
- 0
- Explanation:
- 0 is the smallest.
Example 3
- Input:
- nums = [11, 13, 15, 17]
- Output:
- 11
- Explanation:
- Not rotated → first element.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.