Problem link : Richie’s Mountain
Contest : RECode 9.0
Author : Abhishek
Tester : Shivansh
Editorialist : Abhishek
Difficulty : Easy
Prerequisites : Basic DP
Problem : You are given the height of a mountain at n points. Given m queries
having two integers l , r , find whether the range (l,r) has exactly one peak.
A range consisting of a peak will look like a_i < a_{i+1} < a_{i+2} ..... < a_{x} > a_{x+1} > a_{x+2} .... > a_{j} . (i≤x≤j)
Explanation : Simple DP approach.
Maintain two arrays left and right. Left[i] denotes the number of integers which form an continuous strictly increasing sequence starting from Arr[i] and right[i] denotes the number integers which form a continuous strictly decreasing sequence ending at Arr[i].
For a given query (l , r), we have the values of both, the length of increasing sequence from arr[l] and the length of decreasing sequence ending at arr[r]. Adding the length of increasing and decreasing sequence starting at l and ending at r respectively should be greater than or equal to length of the interval +1(as the top most point or the peak will be counted twice, both for increasing and decreasing sequence), i.e. (r-l+1)+1.
Time Complexity : O(n)
Setter’s Solution : Solution