Leetcode 154: Find Minimum in Rotated Sorted Array II

Problem:

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.

Analysis:

Based on the previous analysis of Leetcode 154, we just need to specify the action if mid equals
to the left.
Leetcode 154: Find Minimum in Rotated Sorted Array

Code:

public class Solution {

   public int findMin(int[] num) {
       int left=0;
       int right=num.length-1;
       int min=Integer.MAX_VALUE;
       while(left<=right){
           int mid=(left+right)/2;
           min=Math.min(min,num[mid]);
           if(num[left]<num[mid]){ //A[left..mid] is sorted
               min=Math.min(min,num[left]);
               left=mid+1;
           }else if(num[left]>num[mid]){ //A[mid..right] is sorted
               right=mid-1;
           }else{
               left++;
           }
       }
       return min;
   }
}

Leetcode 153: Find Minimum in Rotated Sorted Array

Problem:
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.
You may assume no duplicate exists in the array.

Analysis:
Similarly, we can easily check which part of the array is sorted and we just compare the lowest
element. Then, we continue to search the other part.

Code:

public class Solution {
    public int findMin(int[] num) {//[1],[2,1], [3,1,2]
        int left=0;
        int right=num.length-1;
        int min=Integer.MAX_VALUE;
        while(left<=right){
            int mid=(left+right)/2;
            if(num[left]<=num[mid]){
                min=Math.min(min,num[left]);
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return min;
    }
}

Leetcode 81: Search in Rotated Sorted Array II

Problem:

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

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

Write a function to determine if a given target is in the array.

Analysis:

Based on the analysis of  "Search in Rotated Sorted Array", we are unable to make sure which part

is sorted only by comparing the mid with the left element. In this case, we need to increase the left

pointer until it is not equal to the mid.

Related questions:

Leetcode 33: Search in Rotated Sorted Array

Code:

public class Solution {
    public boolean search(int[] A, int target) {
        if(A==null || A.length==0 || A.length==1 && A[0]!=target){
            return false;
        }
        int left=0;
        int right=A.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(target==A[mid]){
                return true;
            }else if(A[left]<A[mid]){
                if(A[left]<=target && target<A[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else if(A[left]>A[mid]){
                if(A[mid]<target && target <=A[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }else{
                left++;
            }
        }
        return false;
    }
}

Leetcode 33: Search in Rotated Sorted Array

Problem:

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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Analysis:

Two conditions should be paid attention. One is that before rotated, the array is sorted and the other

is there is no duplicate. We can modify binary search to search rotated array. 

Suppose A is the rotated array.

left=0, right=A.length-1, mid=(right+left)/2

Case 1: if A[mid] >A[left], A[left .. mid] is in order. 

Case 2: if A[mid] < A[left], A[mid] is also smaller than A[right], therefore A[mid .. right] is in order.

We can easily verify whether the target is in the sorted part or not. 

Code:

public class Solution {
    public int search(int[] A, int target) {
        if(A==null || A.length==0 || A.length==1 && A[0]!=target){
            return -1;
        }
        int left=0;
        int right=A.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(A[mid]==target){
                return mid;
            }else if(A[mid]>=A[left]){ // A[left..mid] is sorted.
                if(A[left]<=target && target<A[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{//A[mid..right] is sorted.
               if(target<=A[right] && target>A[mid]){
                   left=mid+1;
               }else{
                   right=mid-1;
               }
            }
        }
        return -1;
    }
}

Leetcode 80: Remove Duplicates from Sorted Array II

Problem:

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3]. 

Analysis:

As duplicates are allowed at most twice, the first thought is to compare the current element with the

previous two elements. However, we must remember that the array is a sorted array, which implies

that if current element equals to the second previous element, it must equal to the first previous one.

If not equal, current element can be added to the list.

Code:

public class Solution {
    public int removeDuplicates(int[] A) {
       if(A.length<=2){
           return A.length;
       }
       int tail=2;
       for(int i=2;i<A.length;i++){
           if(A[i]!=A[tail-2]){
               A[tail++]=A[i];
           }
       }
       return tail;
    }
}

Leetcode 26: Remove Duplicates from Sorted Array

Problem:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Analysis:
As it is a sorted array, duplicated elements are neighboring with each other.
We can easily using two pointers to copy the first met element to the end of non-duplicated list.

Code:

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A==null){
            return -1;
        }else if(A.length<=1){
            return A.length;
        }
        int len=0;// the last element
        for(int i=1;i<A.length;i++){//i is another pointer
            if(A[i]!=A[len]){
                A[++len]=A[i];
            }
        }
        return len+1;
    }
}