HackerRank Min Max Riddle problem solution

In this HackerRank Min Max Riddle problem solution, you are given an integer array of size n, find the maximum of the minimum(s) of every window size in the array. The window size varies from 1 to n.

Function Description

Complete the riddle function in the editor below. It must return an array of integers representing the maximum minimum value for each window size from 1 to n.

riddle has the following parameter(s):

• arr: an array of integers

HackerRank Min Max Riddle problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the riddle function below.
def riddle(arr):
    n = len(arr)
    max_mins = [None]*n
    stack = [] # will store (num, index)
    for i in range(n):
        #print('stack', stack)
        #print('max_mins', max_mins)
        # remember to "push back"
        _m = i
        while len(stack) > 0 and stack[-1][0] > arr[i]:
            _v, _i = stack.pop(-1)
            w = i - _i
            for _w in range(w): # note that it's zero indexed and shifted down
                if max_mins[_w] is None:
                    max_mins[_w] = _v
                else:
                    max_mins[_w] = max(max_mins[_w], _v)
            _m = _i # get the smallest index at which we could start
        stack.append((arr[i],_m))

    # these were the minima for all this time
    while len(stack) > 0:
        #print('stack', stack)
        #print('max_mins', max_mins)
        _v, _i = stack.pop(-1)
        w = n - _i
        for _w in range(w):
            if max_mins[_w] is None:
                max_mins[_w] = _v
            else:
                max_mins[_w] = max(max_mins[_w], _v)
    return max_mins

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = list(map(int, input().rstrip().split()))

    res = riddle(arr)

    fptr.write(' '.join(map(str, res)))
    fptr.write('n')

    fptr.close()

Min Max Riddle problem solution in C++.

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

int main()
{
    int n,i;
    cin>>n;

    int a[n];
    for(i=0;i<n;++i) {
        cin>>a[i];
    }

    stack<int> s;
    int left[n],right[n],ans[n+1],len;

    for(i=0;i<n;++i) {
        left[i]=-1,right[i]=n;
    }

    for(i=0;i<n;++i) {
        while(!s.empty() && a[s.top()] >= a[i]) {
            s.pop();
        }
        if(!s.empty()) {
            left[i]=s.top();
        }
        s.push(i);
    }

    while(!s.empty()) {
        s.pop();
    }

    for(i=n-1;i>=0;--i) {
        while(!s.empty() && a[s.top()] >= a[i]) {
            s.pop();
        }
        if(!s.empty()) {
            right[i]=s.top();
        }
        s.push(i);
    }

    memset(ans, 0, sizeof ans);
    for(i=0;i<n;++i) {
        len = right[i]-left[i]-1;
        ans[len]=max(ans[len], a[i]);
    }

    for(i=n-1;i>=1;--i) {
        ans[i]=max(ans[i], ans[i+1]);
    }

    for(i=1;i<=n;++i) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}