Be the first user to complete this post

  • 0
 Add to List
Beginner

229. Find the increasing OR decreasing point in an array

Objec­tive:  Given an array of integers which is first increasing then decreasing. Find the element in the array from which point it starts decreasing.
OR
Given an array of integers that is first increasing and then decreasing. Find the maximum element in that array.
Similar Problem: Given an array of integers that is first decreasing and then increasing. Find the element in the array from which point it starts increasing.
OR
Given an array of integers that is first decreasing and then increasing. Find the minimum element in that array.
Example:

int [] a = {1,2,4,6,11,15,19,20,21,31,41,51,55,46,35,24,18,14,13,12,11,4,2,1};
output: 55

int [] a = {1,2,4};  //no deceasing element, so last element will be answer
output: 4

int [] a = {4,2,1};  //no deceasing element, so last element will be answer
output: 4

Approach 1: Linear Search:

  • Navigate the array and track the element from where the array starts decreasing.
  • Handle the edge cases.

Time Complexity: O(n)

Approach 2: Binary Search

  • Modify the binary search.
  • If the mid element is greater than both its left and right neighbors then we have found our element.
  • If the mid element is greater than its left neighbor and less than its right neighbor then the array is still increasing. Do a recursive call on the right half of the array (mid+1, end).
  • If the mid element is less than its left neighbor and greater than its right neighbor then the array is now decreasing. Do a recursive call on the left half of the array (start, mid).
  • Handle the base cases (see the code).

Time Complexity: O(logn)

Output:

(Binary Search) First Element from where elements starts decreasing: (index: 12) : 55

Related Problems: