Validate Array Is a Mountain Array & Peak Index: This Java program checks if the input array is a valid mountain array or not. A valid mountain array is an array that represents a mountain-like pattern, i.e., it first strictly increases, reaches a peak, and then strictly decreases.
Validate Given Array Is A Valid Mountain Array
package com.softwaretestingo.interviewprograms;
import java.util.Scanner;
public class InterviewPrograms89
{
public static boolean validMountArray(int[] Arr)
{
int i = 0;
int j = Arr.length - 1;
int n = Arr.length - 1;
while (i + 1 < n && Arr[i] < Arr[i+1])
{
i++;
}
while (j > 0 && Arr[j] < Arr[j-1])
{
j--;
}
return (i > 0 && i == j && j < n);
}
public static void main(String[] args)
{
int num,i;
// taking the inputs
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of elements : ");
num = sc.nextInt();
int arr[]=new int[num];
System.out.print ("Enter the array elements : ");
for (i=0; i<num; i++ )
{
arr[i] = sc.nextInt();
}
System.out.println(validMountArray(arr));
}
}
Output
Enter the number of elements : 3 Enter the array elements : 1 2 1 true
Let’s understand the program step by step:
- The program defines a class named InterviewPrograms89.
- Inside the class, there is a method named validMountArray, which takes an integer array Arr as input and returns a boolean value (true or false) indicating whether the array is a valid mountain array or not.
- The validMountArray method starts by declaring three variables: i, j, and n.
- It sets the initial value of i to 0 and j to the last index of the array (Arr.length – 1). The variable n is set to the last index of the array minus 1 (Arr.length – 1).
- The method uses two while loops to find the peak of the mountain in the array.
- The first while loop (i loop) runs as long as i + 1 is less than n (the last index before the peak) and Arr[i] is less than Arr[i + 1] (the array is strictly increasing). It increments i to move forward in the array until the increasing pattern continues.
- The second while loop (j loop) runs as long as j is greater than 0 and Arr[j] is less than Arr[j – 1] (the array is strictly decreasing). It decrements j to move backward in the array until the decreasing pattern continues.
- After finding the peak of the mountain (if it exists), the method checks whether the peak is not at the start or end of the array, and whether i and j are equal (i.e., the mountain has a single peak), and whether the peak is not at the first or last index of the array.
- If all the conditions in the return statement (i > 0 && i == j && j < n) are satisfied, it means the array is a valid mountain array, and the method returns true. Otherwise, it returns false.
- The main method is used to execute the program.
- Inside the main method, the program reads the number of elements and the array elements from the user.
- It takes the user input using the Scanner class and stores the array elements in the integer array arr.
- The program then calls the validMountArray method, passing the arr as an argument, to check whether the array is a valid mountain array.
- Finally, the result (true or false) is printed on the console using System.out.println(validMountArray(arr)).
In summary, this Java program determines whether the given array is a valid mountain array or not. It does this by finding the peak in the array and checking certain conditions to ensure that the array has a mountain-like pattern. The program provides a simple and efficient way to validate mountain arrays, making it useful for various applications.
Alternative Way 1:
This Java program checks whether a subarray of the given array is in the form of a mountain or not. A subarray is considered to be in the form of a mountain if there exists an element within the subarray such that all elements to its left are in strictly increasing order and all elements to its right are in strictly decreasing order.
package com.softwaretestingo.interviewprograms;
public class InterviewPrograms89_1
{
// Find Whether A Subarray Is In Form Of A Mountain Or Not
static void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
{
arrayL[0] = 0;
int increasingNumber = 0;
for (int i = 1; i < N; i++)
{
if (arr[i] > arr[i - 1])
increasingNumber = i;
arrayL[i] = increasingNumber;
}
arrayR[N - 1] = N - 1;
int decreasingNumber = N - 1;
for (int i = N - 2; i >= 0; i--)
{
if (arr[i] > arr[i + 1])
decreasingNumber = i;
arrayR[i] = decreasingNumber;
}
}
static boolean solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
{
return (arrayR[Left] >= arrayL[Right]);
}
public static void main(String[] args)
{
int arr[] = {3,4,5,6,1,5,1,2,1};
int N = arr.length;
int arrayL[] = new int[N];
int arrayR[] = new int[N];
buildArrays(arr, N, arrayL, arrayR);
int L = 0;
int R = 3;
if (solveQuery(arr, arrayL, arrayR, L, R))
System.out.println("Mountain form");
else
System.out.println("Not a mountain form");
L = 5;
R = 7;
if (solveQuery(arr, arrayL, arrayR, L, R))
System.out.println("Mountain form");
else
System.out.println("Not a mountain form");
}
}
Output
Mountain form Not a mountain form
Let’s understand the program step by step:
- The program defines a class named InterviewPrograms89_1.
- Inside the class, there are three static methods: buildArrays, solveQuery, and the main method.
- The buildArrays method takes the input integer array arr, its length N, and two arrays arrayL and arrayR as parameters. These two arrays will store information about the increasing and decreasing parts of the subarray for each element.
- The buildArrays method initializes arrayL[0] to 0 because the first element in the array always has no elements to its left in the subarray. Then it iterates through the array from index 1 to N-1 (exclusive) and keeps track of the index of the element where the increasing part starts. It does this by comparing the current element with the previous element and updating the increasingNumber variable accordingly. For each index, it stores the value of increasingNumber in the arrayL array.
- The buildArrays method then initializes arrayR[N-1] to N-1 because the last element in the array always has no elements to its right in the subarray. Then it iterates through the array from index N-2 to 0 (inclusive) and keeps track of the index of the element where the decreasing part starts. It does this by comparing the current element with the next element and updating the decreasingNumber variable accordingly. For each index, it stores the value of decreasingNumber in the arrayR array.
- The solveQuery method takes the input integer array arr, the two arrays arrayL and arrayR, and the left and right indices Left and Right of the subarray as parameters. It checks whether the subarray defined by indices Left and Right is in the form of a mountain or not. It does this by comparing the arrayR value of the left index (arrayR[Left]) with the arrayL value of the right index (arrayL[Right]). If arrayR[Left] >= arrayL[Right], it means there exists an element in the subarray such that all elements to its left are in strictly increasing order and all elements to its right are in strictly decreasing order, and the method returns true. Otherwise, it returns false.
- The main method is used to execute the program.
- Inside the main method, the program initializes the input integer array arr with some values.
- The program then creates two arrays arrayL and arrayR, both of length N, to store the information about the increasing and decreasing parts of the subarray.
- The program calls the buildArrays method, passing the arr, N, arrayL, and arrayR as arguments, to build the two arrays.
- The program then checks two subarrays defined by the left and right indices (L and R) using the solveQuery method. If the subarray is in the form of a mountain, it prints “Mountain form”; otherwise, it prints “Not a mountain form”.
In summary, this Java program checks whether a subarray of the given array is in the form of a mountain or not. It uses two separate arrays (arrayL and arrayR) to store the information about the increasing and decreasing parts of the subarray and efficiently determines whether a subarray satisfies the mountain-like pattern. The program is useful for analyzing and identifying mountain subarrays in a given array efficiently.
Find the Peak Element Index Of the Mountain Array
This Java program is designed to find the index of the peak element in a given mountain array. A mountain array is an array that initially increases and then decreases. The peak element in a mountain array is the element that is greater than its adjacent elements.
package com.softwaretestingo.interviewprograms;
public class InterviewPrograms89_2
{
//Find the Peak Element Index Of the Mountain Array
public static int getPeakIndex(int[] array)
{
int low = 0;
int high = array.length - 1;
int mid;
while (low<high)
{
mid = low + (high - low) / 2;
if (array[mid] >= array[mid + 1])
{
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
public static void main(String[] args)
{
int mountainArray[] = { 4, 8, 16, 32, 27, 9, 3 };
int peak = getPeakIndex(mountainArray);
System.out.println("Peak index is:" + peak);
}
}
Output
Peak index is:3
Let’s go through the program step by step:
- The program defines a class named InterviewPrograms89_2.
- Inside the class, there are two static methods: getPeakIndex and the main method.
- The getPeakIndex method takes an integer array array as a parameter and returns the index of the peak element in the array.
- Inside the getPeakIndex method, two variables low and high are initialized to the first and last indices of the array, respectively. The method uses binary search to find the peak element.
- In each iteration of the while loop, the method calculates the middle index mid as the average of low and high. If the element at index mid is greater than or equal to the element at index mid + 1, it means the peak element is either at index mid or to the left of it. So, the high is updated to mid to search for the peak element in the left half of the array.
- If the element at index mid is less than the element at index mid + 1, it means the peak element is to the right of mid. So, the low is updated to mid + 1 to search for the peak element in the right half of the array.
- The binary search continues until low is less than high, which means the search space has not been reduced to a single element.
- When the binary search finishes, low will point to the index of the peak element in the mountain array, and the method returns low.
- The main method is used to execute the program.
- Inside the main method, the program initializes the mountain array mountainArray with some values.
- The program calls the getPeakIndex method, passing the mountainArray as an argument, to find the index of the peak element in the array.
- The program then prints the index of the peak element using the System.out.println statement.
In summary, this Java program uses binary search to find the index of the peak element in a given mountain array. The binary search algorithm efficiently narrows down the search space by comparing the middle element with its adjacent elements until the peak element is found. The program is useful for quickly locating the peak element in a mountain array, which can be helpful in various applications such as optimization problems or finding maximum values in data sets.
