We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
functionriddle(arr,n){consts=[]// Used to find previous and next smaller // Arrays to store previous and next smallerconstleft=[]constright=[]// Initialize elements of left[] and right[] for(leti=0;i<n;i++){left[i]=-1;right[i]=n;}// Fill elements of left[] (closer lower value on the left of i)for(leti=0;i<n;i++){while(s.length&&arr[s[s.length-1]]>=arr[i]){s.pop()}if(s.length){left[i]=s[s.length-1]}s.push(i)}// Empty the stack as stack is going to be used for right[] while(s.length){s.pop()}// Fill elements of right[] (closer lower value on the right of i)for(leti=n-1;i>=0;i--){while(s.length&&arr[s[s.length-1]]>=arr[i]){s.pop()}if(s.length){right[i]=s[s.length-1]}s.push(i)}// Create and initialize answer array constans=[]for(leti=0;i<=n;i++){ans[i]=0}// Fill answer array by comparing minimums of all // lengths computed using left[] and right[] for(leti=0;i<n;i++){// length of the interval constlen=right[i]-left[i]-1;// arr[i] is a possible answer for this length // 'len' interval, check if arr[i] is more than // max for 'len' ans[len]=Math.max(ans[len],arr[i]);}// Some entries in ans[] may not be filled yet. Fill // them by taking values from right side of ans[] for(leti=n-1;i>=1;i--){ans[i]=Math.max(ans[i],ans[i+1])}ans.shift()// The first 0 is uselessreturnans}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Min Max Riddle
You are viewing a single comment's thread. Return to all comments →
Javascript solution
As several people mentioned already, this is based on the least price stock problem (but this is two way)
If you are struggling (like I was), read this first: https://practice.geeksforgeeks.org/problems/stock-span-problem/0
and then: https://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/