Code Destine

Problem Statement

A peak element is an element, which is greater than its neighbors.

You have given an array of integers N, where N[i] != N[i+1], Write a program to find out the peak element in the given array and return its index. In the case of multiple peaks, return the index of any one of the peak elements.

Note: N[-1] and N[n] can be considered as negative infinity, which means they are always smaller than their neighbors.

Example 

Input :- [1, 2, 3, 1]
Output :- 2 (index)

Input :- [3, 4, 5, 2, 4, 1, 0]
Output :- 4 (index)

Solution – Linear Search

In the Linear Search approach, we will iterate through the given input array N and at each iteration, if the current integer is greater 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.findPeakElement(new int[] {3, 4, 5, 2, 4, 1, 0});
		System.out.print(result);						
	}
	
	/* Solution */    
	public int findPeakElement(int[] nums) {
        for (int i=0; i<nums.length-1; i++) { 
            if (nums[i] > nums[i + 1]) {
            	return i;
            }   
        }
        return nums.length - 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 N.
2. If the middle element is on the descending sequence of elements (N[mid] > N[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 (N[mid] < N[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.findPeakElement(new int[] {3, 4, 5, 2, 4, 1, 0});
		System.out.print(result);						
	}
	
	/* Solution */    
	public int findPeakElement(int[] nums) {		
        int left = 0;
        int right = nums.length - 1;
        int mid;
        
        while (left < right) { mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1]) {
            	right = mid;
            }else {
            	left = mid + 1;
            }
        }
        return left;
    }
}

Result

4

Similar Post

1. Implement Queue using Stacks
2. Design Stack using Linked List
3. Design Queue using Linked List

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