It’s day 25 of the Leetcode July Challenge, and we’re working on a tricky little problem, Find Minimum in Rotated Sorted Array II. We’re given a sorted array of integers that has been rotated by an unkown factor and asked to find the minimum. An important problem constraint is that the array may contain duplicates. It’s a simple premise, so let’s look at some test cases.

// No absolute rotation.
Input: [1,2,3,4,5]
// Minimum rotated into first half of array.
Input: [5,1,2,3,4]
// Minimum rotated into last half of array.
Input: [3,4,5,1,2]

From these test cases, we can write a O(log n) binary search function to find the minimum–but!–but we have to also consider the tougher constraint edge cases where the array contains duplicates.

// Minimum is rotated among duplicates, particulary the algorithm needs to distinguish these cases.
Input: [2,1,2,2,2] // duplicate case 1
Input: [2,2,1,2,2]
Input: [2,2,2,1,2] // duplicate case 3

Considering these edge cases, I think it will be difficult to differentiate, particulary between duplicate case 1 and 3 in binary search conditions. Thinking through the binary search, we’ll be comparing the left, right, and midpoint array values and adjusting the search window left or right depending on the result. However, duplicate cases 1 and 3 have an identical state on the first iteration and moving arbitrarily from that point won’t work. The only option would be to reduce the search window linearly from the left or right. This becomes even more apparent looking at a worst case edge case.

// All duplicates, arbitrary rotation.
Input: [2,2,2,2,2]

With that in mind, I’m convinced we’re looking at a linear lower bound complexity for this problem. We can still try out a linear bounds binary search. This algorithm would be preferable in domains where we anticipated inputs to be large and duplicates to be rare, as it would tend towards a logarithmic average case complexity.

int findMin(vector<int>& nums) {
   int left = 0, right = nums.size()-1;
   while(left < right) {
	  int mid = left+(right - left)/2;

	  // typical binary conditions
	  if(nums[mid] < nums[right]) {
		 right = mid;
	  }
	  else if(nums[mid] > nums[right]) {
		 left = mid+1;
	  }
	  // special case linear search window reduction.
	  else {
		 right--;
	  }
   }
   return nums[left];
}

It’s a good algorithm, but by understanding the bounds of the problem, we can write a much simpler and highly performant linear algorithm with an early return optimization that would be ideal for input domains where the frequency of duplicates is common or unknown.

int findMin(vector<int>& nums) {
   int minNum = nums[0];
   for(auto num : nums) {
	  if(num < minNum) return num;
   }
   return nums[0];
}

Some people will be disappointed in going through a lot of work to arrive at such a simple algorithm, but I enjoy it. Applying algorithm analysis to arrive at optimal design options is a key aspect of software engineering. I hope you enjoyed it too!