Minimum in Rotated Sorted Array with Duplicates

Prerequisites: 🎞️Check if an array is sorted and rotated, ⁉️Thought Experiment, Does an array need to be sorted to run Binary Search? 📉The Minimum in a Rotated Sorted Array

Question

Input: nums = [1,3,5]
Output: 1

Input: nums = [2,2,2,0,1]
Output: 0

Intuition + Solution

1. For solving these questions we are going to build up on 📉The Minimum in a Rotated Sorted Array. Make sure you are familiar on.
1. What is a sorted and rotated array?
2. How rotating a sorted array gives us two sorted arrays, an upper half and the lower half.
3. Identify where the minimum occurs in a sorted and rotated array(the first value in the lower half)
4. How to find the minimum in a sorted rotated array with unique elements.
1. How do we know we are in the upper half or the lower half
2. In the question 📉The Minimum in a Rotated Sorted Array
1. We used the True/False Framework to know which array we were in.
1. True = lowerhalf
2. False = upperhalf
2. Simply return the first value in the lower half which happened to be 🔑Find the First True in a Sorted Boolean Array .

3. In this question, having duplicates makes our previous framework unusable. We can't confidently return the first value in the lower half, as we are uncertain whether we are in the lower half accurately. Let's imagine the midpoint is on 3 at index 3.

4. What will happen as a result?
1. When we rotate a sorted array we get two halves.

2. Previously
1. We determined which half we were in by comparing it to the last element.
2. If our midpoint was in the lower half, we would consider it a possible value and discard the value on the right side.
1. code
Copy

#3(mid) ≤ 3(last)
InLowerHalf = nums[mid] <= nums[-1]
if InLowerHalf:
    possibleMin = mid
    right = mid - 1

2. Illustration
1. Step 1 identify which half.

2. Store mid as a possible value and get rid of all the values on the right. In doing that we lost our actual min. So sad :(

5. What is one thing we can be sure about the duplicates?
1. Only one duplicate can be in both halves, Having two duplicates in either half would disrupt the initial sorted property.

6. If there is a duplicate it will be on the very right side of the array. Can we remove the duplicates from the right and convert the problem back to 🔑Find the First True in a Sorted Boolean Array as our minimum.
7. Previously, we used our last element to determine which half of the array we were in. However, if our last element is a duplicate, our algorithm can be easily confused. Therefore, we will use the right pointer to make the comparison.
1. We will use the element at the right pointer as a hypothetical last element of comparison, to determine which half of the array we are currently in, as well as to cut the range from the right.
2. Since the minimum will be in the lower half and we are cutting the elements from the right, the last element we will cut from the right side in the lower half will be our minimum.
8. When we see a duplicate we update the right pointer by one step to the left, giving us a new hypothetical last element for comparison.
9. What are "circular duplicates" (my own term)? These are duplicates caused by the circular nature of the rotated sorted array, IMPORTANTLY where two elements can be in both halves, also includes duplicates that will be in the lower half and will be handled in the same way. Here is the code:
Copy

circularDuplicates = nums[mid] == nums[right]

elif circularDuplicates:
    right -= 1

1. Normallizing the array
1. Step 1 circularDuplicates = nums[mid] == nums[right] is True

2. Step 2 remove the right pointer(hypothetical last Element) by one to the left. Will keep doing this untill we are not at a duplicate.

3. Normallized array. The problem is again reduced to 🔑Find the First True in a Sorted Boolean Array

4. What if there are multiple duplicates in the lower half? That will give us a non normalized array. But that will not be a problem. Why?

1. We are removing the duplicates from the right side one by one from the upper half, in a case like this the midpoint will only move to the left. Since the array is circular, the elements on the left of the midpoint (in the upper half) will still be duplicates. The right and mid-pointers move in a circular manner until all the duplicates are eliminated.
Copy

[3,1,2,3,3,3,3,3,3,3]
           ^       ^
           M    <--R

[3,1,2,3,3,3,3,3,3,X]
         ^       ^
         M    <--R

[3,1,2,3,X,X,X,X,X,X] # all duplicates removed in the upper half
 ^     ^
 M  <--R

[3,1,2,3,X,X,X,X,X,X] # Now duplicates will be removed from the lower half
 ^     ^
 M  <--R
10. Lets run it with the change! Oh, It gave an error on [1,3,5].
1. Iteration 1: The midpoint is 3 and the right side is 5.
1. InLowerHalf = nums[mid] < nums[right]: The midpoint is in the lower half, so we keep this midpoint(3) as a possible minimum and get rid of all the elements on the right.
2. Iteration 2: The midpoint is 1 and the right side is 1.
1. CircularDuplicates = nums[mid] == nums[right]: The midpoint a circular duplicate, so we disregard it.
3. We get the answer as 3 instead of 1, which is incorrect.
11. We didn’t account for one thing. In 📉The Minimum in a Rotated Sorted Array the lower half included the case where the last element was equal to the mid. Which we fail to include as we made that alteration for circular duplicates.
1. What is one change we need to make to make sure that this test case [1,3,5], doesn’t give us an error?
Copy

#FROM Find the minumum in a sorted array (unique items)
if inLowerHalf:
  possibleMin = mid
  right = mid - 1


#TO Two Find the minumum in a sorted array (duplicate items)

if inLowerHalf:
    possibleMin = mid
    right = mid - 1

elif circularDuplicates: # didn't account this a possible minimum
    right -= 1

2. Simply change the circularDuplicates statement as that can also be a minimum.
Copy

elif circularDuplicates:
  possibleMin = mid #<-- change here :)
  right -= 1

12. Lets run it again to see if this works! IT DOES !!!

class Solution:
    def findMin(self, nums):
        
        left, right = 0, len(nums) - 1
        possibleMin = -1

        while left <= right:
            
            mid = left + (right - left) // 2

         
            inLowerHalf = nums[mid] < nums[right] 
            inUpperHalf = nums[mid] > nums[right]
            circularDuplicates = nums[mid] == nums[right]
            
            
						if inLowerHalf:
                possibleMin = mid
                right = mid  

            elif circularDuplicates:
                possibleMin = mid
                right -= 1
            # else
            elif inUpperHalf:
                left = mid + 1
            

        return nums[possibleMin]

class Solution:
    def findMin(self, nums):

        left, right = 0, len(nums) - 1
        possibleMin = -1

        while left <= right:
            
            mid = left + (right - left) // 2


	          inLowerHalf = nums[mid] <= nums[-1]
            



						if inLowerHalf:
                possibleMin = mid
                right = mid - 1

            
            

						else:
                left = mid + 1
            
       
        
					return nums[possibleMin]

This works on leetcode But…

1. We check for circular duplicates from the right and move the right pointer if a duplicate is found. When two duplicate elements are found, the pointer moves two indexes (ending on 2). When we compare the rightmost element to determine which part of the array (midpoint) we are in, we mistakenly assume it is the lower half, as 2 is greater than 1 (at index 3), indicating that we are in the lower half. We then move the right pointer to the edge of the half to find the minimum, missing the 1 at index 9.

2. Runs binary search assuming the minimum is to the left(Since 1 is smaller than 2 ), completely missing the actual minimum.

3. We know that if we are coming from the right the values are decreasing as that will normally be characteristic of a lower half. (3,1,0).

4. However, there is an increase in the values from 0 to 4, which is our cue that it was the rotation point or actual minimum in the sorted array.

5. The only time coming from the right we hit a value that starts to increase is at the place where the initial minimum was once that comes to pass; we simply return that as the PossibleMin.
Copy

elif circularDuplicates:

	if nums[right - 1] > nums[right]:
	    possibleMin = right
	    break

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(n) :(

Space Complexity: O(1)

This will not be a logarithmic time in the worst case.

[1,1,1,1,1,1,1,1,1,1,1,1,1,1] For a case like this we will start from the right and keep going to the right so we will have to go over every element so that will move our complexity to O(n)