Algorithm {Find Minimum in Rotated Sorted ArrayII}

I’ve solved next task Find Minimum in Rotated Sorted ArrayII. The main difference between two solutions is duplication. So, task description:

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array 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.

OK, original algorithm:

public int findMin(int[] num) {
        if (num.length == 0)
            return 0;
        return findMin(num, 0, num.length - 1);
    }
 
    int findMin(int[] A, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A[m] > A[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return A[l];
    }

We can see just two conditions middle more than right or not,

            if (A[m] > A[r]) {
                l = m + 1;
            } else {
                r = m;
            }

OK, now we should handle one more condition, and yes, you are right equal ==. Generally we have to check if A[l] (left one) equals to A[m] (middle one) and equals to A[r] (right one) if yes, increase left index, or decrease right 🙂 and it would work. Yes, complexity will be O(N).

But what will be if we try to check recursively left and right part of array, if middle element equals to right one:

if (A[m] == A[r])

It should work and complexity should be better. OK, let’s go to implement this algorithm:

    public int findMin(int[] num) {
        if (num.length == 0)
            return 0;
        return findMin(num, 0, num.length - 1);
    }
 
    int findMin(int[] A, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A[m] > A[r]) {
                l = m + 1;
            } else if (A[m] == A[r]){
                return findMin(A, l, r, m);
            }else{
                r = m;
            }
        }
        return A[l];
    }
 
    private int findMin(int[] A, int l, int r, int m) {
        int rightMin = findMin(A, m+1, r);
        int leftMin = findMin(A, l, m-1);
        if(rightMin > leftMin ){
            return leftMin;
        }else {
            return rightMin;
        }
    }

We can see one additional condition and method. What is happening ? If middle element equals to right we try to recursively run into right side:

findMin(A, m+1, r);

and into left side

findMin(A, l, m-1);

after that just check what is bigger and return result. That is very good, but what is the complexity ? Of course we will have the same O(N), but actually twice faster, because real  complexity will be O(N/2) but constants are ignoring in big O notation.

So, this is all leetcode accepted solution 🙂