Find in Mountain Array

Find in Mountain Array

You may recall that an array A is a mountain array if and only if:

• A.length >= 3
• There exists some i with 0 < i < A.length - 1 such that:
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target.  If such an index doesn't exist, return -1.

You can't access the mountain array directly.  You may only access the array using a MountainArray interface:

• MountainArray.get(k) returns the element of the array at index k (0-indexed).
• MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

 

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

 

Constraints:

• 3 <= mountain_arr.length() <= 10000
• 0 <= target <= 10^9
• 0 <= mountain_arr.get(index) <= 10^9

Approach

Intuition

Algo

1. Binary find peak in the mountain. 852. Peak Index in a Mountain Array
2. Binary find the target in strict increasing array
3. Binary find the target in strict decreasing array
   
   

Tip

Personally,
If I want find the index, I always use while (left < right)
If I may return the index during the search, I'll use while (left <= right)

Complexity

Time O(logN) Space O(1)

Some Improvement

1. Cache the result of get, in case we make the same calls.
   In sacrifice of O(logN) space for the benefit of less calls.
2. Binary search of peak is unnecessary, just easy to write.
   
   

Java

    int findInMountainArray(int target, MountainArray A) {
        int n = A.length(), l, r, m, peak = 0;
        // find index of peak
        l  = 0;
        r = n - 1;
        while (l < r) {
            m = (l + r) / 2;
            if (A.get(m) < A.get(m + 1))
                l = peak = m + 1;
            else
                r = m;
        }
        // find target in the left of peak
        l = 0;
        r = peak;
        while (l <= r) {
            m = (l + r) / 2;
            if (A.get(m) < target)
                l = m + 1;
            else if (A.get(m) > target)
                r = m - 1;
            else
                return m;
        }
        // find target in the right of peak
        l = peak;
        r = n - 1;
        while (l <= r) {
            m = (l + r) / 2;
            if (A.get(m) > target)
                l = m + 1;
            else if (A.get(m) < target)
                r = m - 1;
            else
                return m;
        }
        return -1;
    }

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

 Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

 Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

 

Follow up: The overall run time complexity should be O(log (m+n)).

Solution:

double findMedianSortedArrays(int A[], int m, int B[], int n) {
        /* A[0, 1, 2, ..., n-1, n] */
        /* A[0, 1, 2, ..., m-1, m] */
        int k = (m + n + 1) / 2;
        double v = (double)FindKth(A, 0, m - 1, B, 0, n - 1, k);
        
        if ((m+n) % 2 == 0) {
            int k2 = k+1;
            double v2 = (double)FindKth(A, 0, m - 1, B, 0, n - 1, k2);
            v = (v + v2) / 2;
        }
        
        return v;
    }
    
    // find the kth element int the two sorted arrays
    // let us say: A[aMid] <= B[bMid], x: mid len of a, y: mid len of b, then wen can know
    // 
    // (1) there will be at least (x + 1 + y) elements before bMid
    // (2) there will be at least (m - x - 1 + n - y) = m + n - (x + y +1) elements after aMid
    // therefore
    // if k <= x + y + 1, find the kth element in a and b, but unconsidering bMid and its suffix
    // if k > x + y + 1, find the k - (x + 1) th element in a and b, but unconsidering aMid and its prefix
    int FindKth(int A[], int aL, int aR, int B[], int bL, int bR, int k) {
        if (aL > aR) return B[bL + k - 1];
        if (bL > bR) return A[aL + k - 1];
        
        int aMid = (aL + aR) / 2;
        int bMid = (bL + bR) / 2;
        
        if (A[aMid] <= B[bMid]) {
            if (k <= (aMid - aL) + (bMid - bL) + 1) 
                return FindKth(A, aL, aR, B, bL, bMid - 1, k);
            else
                return FindKth(A, aMid + 1, aR, B, bL, bR, k - (aMid - aL) - 1);
        }
        else { // A[aMid] > B[bMid]
            if (k <= (aMid - aL) + (bMid - bL) + 1) 
                return FindKth(A, aL, aMid - 1, B, bL, bR, k);
            else
                return FindKth(A, aL, aR, B, bMid + 1, bR, k - (bMid - bL) - 1);
        }
    }

Find Minimum in Rotated Sorted Array

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.

You may assume no duplicate exists in the array.

Solution:

public int findMin(int[] nums) {

      return findMinRec(nums, 0, nums.length-1);

    }

    

    public int findMinRec(int[] a, int start, int end) {

        while(start<end) {

            if(a[start]<a[end])

                return a[start];

            int mid = start+(end-start)/2;

            if(a[start]<=a[mid]) {

                start=mid+1;

            } else {

                end=mid;

            } 

        }

        return a[start];

    }

Replace every element with the next greatest

Question:

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it with -1. For example, if the array is {16, 17, 4, 3, 5, 2}, then it should be modified to {17, 5, 5, 5, 2, -1}.

Solution1:

A naive method is to run two loops. The outer loop will one by one pick array elements from left to right. The inner loop will find the greatest element present after the picked element. Finally the outer loop will replace the picked element with the greatest element found by inner loop. The time complexity of this method will be O(n*n).

Solution2:

A better approach is to replace all elements using one traversal of the array. The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element. The time complexity of this method will be O(n).

public int[] ReplaceNextGreatest(int[] a) {

           int len = a.length;

           int maxNum=a[len-1];

           // Replace right most number with -1

           a[len-1]=-1;

           for(int i=len-2; i>=0; i--) {             

                int temp = a[i];

                a[i] = maxNum;

                if(temp>maxNum) {

                     maxNum = temp;

                }

           }

           return a;

}

Arrange given numbers to form the biggest number

Problem: Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

Approach:

The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers.

Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

Majority Element

Question: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Algo:
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

Step#1:
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count–;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]

Step#2:
Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print “NONE”

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

int findMajority(int[] a)     {         int count, major;               count=0;         major=0;                for(int i=0; i<a.length; i++){             if(count==0){                 major=a[i];                 count=1;             }             else if(a[i] == major){                 count++;             }             else{                 count--;             }         }               return major;     }           boolean isMajority(int[] a, int majNum) {                   int count=0, size=a.length;         for(int i=0; i<size; i++) {             if(a[i]==majNum) {                 count++;             }         }         return (count>size/2)?true:false;     }