Quiz
Can you make this code cleaner?
@code
Answer
Time complexity
O(log N).
The code passes the test cases on LeetCode, but it's not clean.
First, the task is split across multiple if statements. According to the constraints,
we can assume this case is unique and triggered only once.
Constraints:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
Improvement
The array is sorted and rotated, so we just check whether nums[mid] is greater than nums[hi].
The array is rotated and elements are unique, so there are only two patterns.
- If high is higher than middle, move high pointer to the current middle for the next task.
- Else, move lower pointer to middle + 1.
A rotated sorted array has a strong property:
nums[mid] > nums[hi] -> the minimum is on the right.
Otherwise -> the minimum is on the left (including mid).
With this:
only one condition,
clear branching,
and an easy correctness proof.
So we are effectively checking where the rotation point is.
Case: nums[mid] > nums[hi]
index: 0 1 2 3 4 5 6 nums : [4, 5, 6, 7, 1, 2, 3] lo mid hi
Case: nums[mid] <= nums[hi]
index: 0 1 2 3 4 5 6 nums : [1, 2, 3, 4, 5, 6, 7] mid hi
index: 0 1 2 3 4 5 6 nums : [6, 7, 1, 2, 3, 4, 5] mid hi
Final code
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]