At first, this problem seems trivial. Returning min(nums) gives you the right answer, but this is $O(n)$ TC. Some people in the solutions were talking about the solution being $\Omega(n)$ runtime, arguing you must check every single element to find the minimum. But that doesn’t quite use the sorted rotation part of the question… so that’s fishy!
My Initial Solution, Before I read the Comments
Linear search for the pivot point of the rotation. Break early, but still worst case $O(n)$.
class Solution:
def findMin(self, nums: List[int]) -> int:
for i in range(len(nums)):
if nums[i-1] > nums[i]:
return nums[i]
return nums[0]
I figured this wasn’t the most optimal solution, but since it passed beating 100% of submissions on runtime (though LeetCode is not granular enough for that to mean anything), I figured I’d read the comments to see what’s up. I was a little confused as to why this was a Hard difficulty, but as I read I figured out why.
LC 153: No Duplicates
Basically, in a rotated sorted array with no duplicates, the true minimum lies at some index i, and we want to find out where this is. We can use binary search:
- Take an input array. If its first element is strictly greater than its last element, then it must be rotated. If it’s not rotated then it’s just sorted, so return the first element.
- If the array is rotated, consider its left and right halves. Run the algorithm recursively on it.
Worst case, this is logarithmic in the length of the array, since we’re just recursing on one of the halves. We can find the minimum of the half that is sorted in $O(1)$ work.
The recurrence is $W(n) = W(n/2) + O(1) = O(n)$, like binary search! This wasn’t hard to think of once I saw that people were confused about LC154. But LC154 is a little trickier (hence the difficulty jump from Medium to Hard I guess).
LC 154: With Duplicates, now $\Omega(n)$ TC
Someone posted this adversarial proof, but tbh I wasn’t convinced because it was a bit too verbose. I saw this comment - Holy cracked LeetCode user btw top 0.01%????? - and I thought a $O(\log n)$ solution was possible, but upon further inspection there’s a trivial counterexample that makes any approach $\Omega(n)$.
Consider when the rotated sorted array is all the same number, e.g., $$[2, 2, 2, 2, 2, 2, 2, 2]$$ How can you know that 2 is the minimum for sure? Our splitting trick no longer works - at first, I tried to relax the strictly greater than comparison and turn it into greater than or equal to. However, relaxing this strictness means that if the geq succeeds, the half can only be said to be “potentially rotated”. In this case, our original array is “potentially rotated” (all rotations are the same) and if we split the array into halves, we get $$[2, 2, 2, 2]$$ for both the left and right half, leaving us with the same problem.
Why the initial silly solution isn’t the best
Funnily enough, cracked LeetCode user’s solution is also $O(n)$, but it manages to re-use the same trick from LC153 which gives better average case complexity.
The intuition is the exact same, except that when we get an input array with duplicates, we might run into the case where the first and last are the same element. Then we must advance one side (left or right, WLOG left I guess) until we get something different under the first and last. Once we get something different, we can make a decision about whether the subarray is rotated or not as we did in LC 153.
But notice that when the array is all the same number, we never get something different under first and last, so it becomes a linear scan. Taken from that user’s solution, the optimal divide and conquer approach is
class Solution:
def findMin(self, nums: List[int]) -> int:
def dnc(l: int, r: int) -> int:
if l == r:
return nums[l]
# this array is not rotated
if nums[l] < nums[r]:
return nums[l]
# divide
m = (l + r) // 2
# conquer
return min(dnc(l, m), dnc(m + 1, r))
return dnc(0, len(nums) - 1)