Find Mountain Top

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A of N integers, such that till a point these integers are strictly increasing and after that strictly decreasing, find the element present at that point.

See original problem statement here

For Example:

Input : A = [10, 12, 14, 15, 8, 7, 6]

Output : 15

Explanation : 15 is the top point. As before 15 all elements are strictly increasing and after 15 all elements are strictly decreasing.

Can we use Binary Search here ?

Given that half of the array is sorted in increasing order and the other half in decreasing order and we need to find an element that is greater than both elements, one on the left and one on the right. So after going through some online programming courses, Binary Search could be an efficient alternative to quickly search for that element in Logarithmic Time Complexity.

OBSERVATION:

The desired element would be the Maximum element of the array.

SOLVING APPROACH:

  1. The idea is to use Binary Search.

  2. Initialize start and end as starting and ending indexes of the array.

  3. Calculate, mid = start + (end - start) / 2.

  4. For every such mid calculated check if the element at mid is greater than both of its left and right element. If Yes return this element.

  5. Else if element at mid is only greater than left element, then go on searching in the right half.

  6. Else, go on searching in the left half till the element is found.

ILLUSTRATION:

A = [12, 14, 15, 8, 7, 6, 5]

i = 0
j = 6
mid = (0 + 6) / 2 = 3
Since, A[3] < A[2]
j = mid - 1 = 2

i = 0
j = 2
mid = (0 + 2) / 2 = 1
Since, A[1] < A[2]
i = mid + 1 = 2

i = 2
j = 2
mid = (2 + 2) / 2 = 2
Since, A[2] > A[1] and A[2] > A[3]

Therefore, A[2] = 15 is our required top point. 

SOLUTIONS:


#include <stdio.h>

/* function for find Mountain Top */
int MountainTop(int *arr, int start, int end){
  while(start <= end){
    int mid = start + (end - start) / 2;

    /*if mid index element is greater than both of 
    its adjacent elements, this is our top element*/
    if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
      return arr[mid];

    /* if mid indexed element is only greater than left element
      this implies top is in the right half */
    else if(arr[mid] > arr[mid - 1])
      start = mid + 1;

    /* if mid indexed element is only greater than right element
      this implies top is in the left half */
    else
      end = mid - 1;
  }
}

int main()
{
  int t; scanf("%d", &t);
  while(t--){
    int n; scanf("%d", &n);
    int arr[n];
    for(int i=0; i<n; i++)
      scanf("%d", &arr[i]);
    printf("%d\n", MountainTop(arr, 0, n-1));
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

/* function for find Mountain Top */
int MountainTop(int *arr, int start, int end){
  while(start <= end){
    int mid = start + (end - start) / 2;

    /*if mid index element is greater than both of 
    its adjacent elements, this is our top element*/
    if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
      return arr[mid];

    /* if mid indexed element is only greater than left element
      this implies top is in the right half */
    else if(arr[mid] > arr[mid - 1])
      start = mid + 1;

    /* if mid indexed element is only greater than right element
      this implies top is in the left half */
    else
      end = mid - 1;
  }
}

int main()
{
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    int arr[n];
    for(int i=0; i<n; i++)
      cin>>arr[i];
    cout<<MountainTop(arr, 0, n-1)<<"\n";
  }
  return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  /* function for find Mountain Top */
  static int MountainTop(int []arr, int start, int end){
    while(start <= end){
      int mid = start + (end - start) / 2;

      /*if mid index element is greater than both of 
      its adjacent elements, this is our top element*/
      if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
        return arr[mid];

      /* if mid indexed element is only greater than left element
        this implies top is in the right half */
      else if(arr[mid] > arr[mid - 1])
        start = mid + 1;

      /* if mid indexed element is only greater than right element
        this implies top is in the left half */
      else
        end = mid - 1;
    }
    // if no mountain top is present
    return 0;
  }

  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t != 0){
      int n = sc.nextInt();
      int arr[] = new int[n];
      for(int i=0; i<n; i++)
        arr[i] = sc.nextInt();
      System.out.println(MountainTop(arr, 0, n-1));
      t--;
    }
  }
}

Space Complexity: O(1)

Previous post Fair Distribution of Chocolates
Next post Majority Votes

Leave a Reply

Your email address will not be published. Required fields are marked *