Code Destine

Problem Statement

An array A is a mountain array, if the following properties hold true:

1. Length of an array is greater than equal to 3 (A.length >= 3).
2. Only one peak element exist in the array. Peak element at index i follows (A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length – 1]) arrangement of elements.

You have given a mountain array A, write a program to return the index of the peak element.

Example 

Input :- [0, 1, 2, 3, 4, 3, 2, 1, 0]
Output :- 3

Input :- [4, 6, 9, 11, 45, 40, 20, 1]
Output :- 4

Solution – Linear Search

In the Linear Search approach, we will iterate through the given input array A and at each iteration, if the current integer is greater than the previous integer and the current integer is smaller than the next integer then the current integer is the peak element.

Program

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int result = main.peakIndexInMountainArray(new int[] {4, 6, 9, 11, 45, 40, 20, 1});
		System.out.print(result);						
	}
	
	/* Solution */    
	public int peakIndexInMountainArray(int[] A) {
        
        if(A == null || A.length <3) return -1;
        
        int previous = A[0];
        for(int i=1; i<A.length-1; i++){            
            if(previous < A[i] && A[i+1] < A[i]){
                return i;
            }
        }
        return -1;
    }
}

Solution – Binary Search

The elements in the given input array are arranged in alternating ascending and descending sorting order and there are no duplicate elements, hence binary search can be used to find out the peak element in the input array.

The Binary Search algorithm is used to find out the required element in the sorted array of elements. At every step reduce the search space by half. In this case, we will modify our binary search program to find out the peak element in the array.

This problem can be solved in following steps :-

1. Find the middle element of the array A.
2. If the middle element is on the descending sequence of elements (A[mid] > A[mid+1]), then it means that the peak element will be on the left side of this middle element. Hence we will reduce the search space between the left and middle elements.
3. If the middle element is on the ascending sequence of elements (A[mid] < A[mid+1]), then it means that the peak element will be on the right side of this middle element. Hence we will reduce the search space between middle + 1 and the right element.
4. Repeat the 2nd and 3rd step recursively, until left is smaller than right.
5. Once left becomes greater than or equal to right, then the peak element will be at the left index.

Program

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int result = main.peakIndexInMountainArray(new int[] {4, 6, 9, 11, 45, 40, 20, 1});
		System.out.print(result);						
	}
	
	/* Solution */    
	public int peakIndexInMountainArray(int[] A) {		
        int left = 0;
        int right = A.length - 1;
        int mid;
        
        while (left < right) {        	
            mid = left + (right - left) / 2;
            if (A[mid] >= A[mid + 1]) {
            	right = mid;
            }else {
            	left = mid + 1;
            }
        }
        return left;
    }
}

Result

4 

Similar Post

1. Height Checker
2. Relative Ranks
3. Check if Coordinates make a Straight Line

That’s all for Peak Index in a Mountain Array in Java, If you liked it, please share your thoughts in a comments section and share it with others too.