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.
Get left limit and right limit of every number in the array. This will give temporary min-max for every window size. Calculate the index as per the formula
index = right - left.
Post this store the max of A[i] and res[index] into result[index]. Then, run a backward scan on result array to find min-max of left over window sizes.
Important Note: Min-max of a window size N will always be less than or equal to the window size of N-1.
static long[] riddle(long[] arr) {
// complete this function
int n= arr.Count();
long[] res = new long[n];
int[] left = new int[n];
int[] right = new int[n];
for(int i=0; i<n; i++){
res[i] = 0;
}
Stack<int> st= new Stack<int>();
for(int i=0; i<n; i++){
while(st.Count>0 && arr[st.Peek()]>=arr[i])
st.Pop();
if(st.Count>0) left[i] = st.Peek()+1;
else left[i]=0;
st.Push(i);
}
Stack<int> st2= new Stack<int>();
for(int i=n-1; i>=0; i--){
while(st2.Count>0 && arr[st2.Peek()]>=arr[i])
st2.Pop();
if(st2.Count>0) right[i] = st2.Peek()-1;
else right[i]=n-1;
st2.Push(i);
}
for(int i=0; i<n; i++){
int k = right[i]-left[i];
res[k]=Math.Max(res[k], arr[i]);
}
for(int i=n-2; i>=0; i--){
res[i]=Math.Max(res[i], res[i+1]);
}
return res;
}
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 →
Get left limit and right limit of every number in the array. This will give temporary min-max for every window size. Calculate the index as per the formula index = right - left.
Post this store the max of A[i] and res[index] into result[index]. Then, run a backward scan on result array to find min-max of left over window sizes.
Important Note: Min-max of a window size N will always be less than or equal to the window size of N-1.