Recycled array solution to Find minimum in Rotated sorted Array

Question

I am working on a hard but stupid bisect search problem and debugging for hours.

Find Minimum in Rotated Sorted Array II

Hard

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:
Input: [1,3,5]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
Note:

This is a follow up problem to Find Minimum in Rotated Sorted Array.

Would allow duplicates affect the run-time complexity? How and why?

The widely accepted answer takes O(n) time,

class SolutionK:
    def findMin(self, nums):
        lo, hi = 0, len(nums)-1
        while lo < hi:
            mid = (hi +lo) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            elif nums[mid] < nums[hi]:
                hi = mid 
            else:
                hi -= 1      
        return nums[lo] 
    # why not min(nums)  or brute force

I think the problem might be solved by a recycled array.

Since there are duplicates, we can find the rightmost max, then max + 1 is the minimal.

#the mid
lo = 0
hi = len(nums)
mid = (lo+hi) // 2
mid = mid % len(nums)

and the terminating condition

if nums[mid-1] <= nums[mid] > nums[mid+1]: return mid as the peak.

Unfortunately I cannot design the decreasing conditions.

Could you please give some hints?

Worst case is a rotated array like [1,1,1,1,1,0,1,1,1] which requires an O(n) search to find the 0. — user3386109
– user3386109, Commented Apr 13, 2019 at 0:33
Yes, 3 major distinct cases * 2 position : duplicates are max, duplicates are min, duplicates are between. Two Positions: duplicates on edge or in the middle. — Wizard
– Wizard, Commented Apr 13, 2019 at 2:09
Yup, and all three require a brute force O(n) search in the worst case. Non-duplicates at the ends of the array allow the problem to be solved in less than O(n) time. — user3386109
– user3386109, Commented Apr 13, 2019 at 2:10

a_guest · Accepted Answer · 2019-04-13 00:17:44Z

You can indeed use bisection. In case the array consists of only unique numbers and has been rotated either the leftmost or the rightmost value will be out of order with respect to the middle point. That is array[0] <= array[len(array) // 2] <= array[-1] will be False. On the other hand this condition may hold if:

the array is not rotated at all,
or there are duplicates such as [1, 1, 1, 1, 2] => (rotate left 1) [1, 1, 1, 2, 1].

So we can separately check the left and right part of the condition (array[0] and array[-1] respectively) and in case one of them is invalidated check the corresponding sub-array (the left and right sub-array respectively). In case neither condition is invalidated we need to check both sides and compare.

The following is an example implementation (it only uses min where there are less than three elements involved, i.e. a simple comparison could be made as well):

def minimum(array):
    if len(array) <= 2:
        return min(array)
    midpoint = len(array) // 2
    if array[0] > array[midpoint]:
        return minimum(array[:midpoint+1])
    elif array[midpoint] > array[-1]:
        return minimum(array[midpoint+1:])
    else:  # Possibly dealing with duplicates.
        return min(minimum(array[:midpoint]),
                   minimum(array[midpoint:]))

from collections import deque
from random import randint, choices

for test in range(1000):
    l = randint(10, 100)
    array = deque(sorted(choices(list(range(l // 2)), k=l)))
    array.rotate(randint(-len(array), len(array)))
    array = list(array)
    assert min(array) == minimum(array)

Thakar Sahil · Accepted Answer · 2023-06-15 07:21:42Z

The easiest solution you can find is here. All you need to focus on mid-element. and other condition you can think of.

  public int findMin(int[] nums) {

        if(nums.length == 1) {
            return nums[0];
        }

        if (nums[0] < nums[nums.length - 1]){
            return nums[0];
        }

        int index = pivotRotatedIndex(nums);

        if (index == nums.length - 1) {
           return nums[0];
        }

        return nums[index+1];
    }

   static int pivotRotatedIndex(int[] nums)  {

        int l = 0;
        int r = nums.length - 1;


        while (l <= r) {

            int m = l + (r - l)/2;

            if (nums[l] > nums[l+1]){
                return l;
            }

            if (nums[m] > nums[m+1]) {
                return m;
            }

            if (nums[m-1] > nums[m]) {
                return m-1;
            }
            
      
            if (nums[m] < nums[l]) {
                r = m;
            }else {
                l = m;
            }


        }
        return  -1;

    }

Collectives™ on Stack Overflow

Recycled array solution to Find minimum in Rotated sorted Array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related