HackerRank Queries with Fixed Length problem solution

In this HackerRank Queries with Fixed Length problem we have given an array and q queries and we need to return a list of answers to each query.

Problem solution in Python programming.

n,q = [int(number) for number in input().split()]

mylist = [int(number) for number in input().split()]

for step in range(q):
    minmax = 0
    d = int(input())
    maxnumber = 0
    for i in range(n):
        if mylist[i] >= maxnumber:
            maxnumber = mylist[i]
        elif i >= d:
            if mylist[i-d] == maxnumber:
                maxnumber = max(mylist[i-d+1:i+1])
        if i >= d-1:
            if minmax == 0 or minmax > maxnumber:
                minmax = maxnumber

    print(minmax)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] ar = new int[n];
        for (int i=0; i<n; i++) ar[i] = sc.nextInt();

        for (int i=0; i<q; i++) {
            System.out.println(minMax(ar, sc.nextInt()));
        }
    }

    public static int minMax(int[] ar, int d) {
        Deque<Integer> deque = new ArrayDeque<>(d);
        // Initial filling of the deque
        for (int i=0; i<d; i++) {
            addNewElement(deque, ar[i]);
        }
        int min = deque.peekFirst();

        for (int i=d; i<ar.length; i++) {
            if (ar[i-d] == deque.peekFirst()) deque.removeFirst();

            addNewElement(deque, ar[i]);

            int max = deque.peekFirst();
            if (max < min) min = max;
        }

        return min;
    }

    // Always put el at the end because it might be the most important el for the series that starts with el itself.
    // Remove all previous el's from the queue that were smaller.
    private static void addNewElement(Deque<Integer> deque, int newEl) {
        while (!deque.isEmpty() && deque.peekLast() < newEl) {
            deque.removeLast();
        }
        deque.offerLast(newEl);
    }
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, q;
    cin >> n >> q;
    int* a = new int[n];
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    
    deque<int> maxima;
    
    for (int i = 0; i < q; ++i)
    {
        int d;
        cin >> d;
        maxima.clear();
        
        int currentMax = 0;
        for (int j = d - 1; j >= 0; --j)
        {
            if (a[j] > currentMax)
                currentMax = a[j];
            maxima.push_front(currentMax);
        }
        int smallestMax = currentMax;
        int end = n - d;
        for (int j = 0; j < end; ++j)
        {
            maxima.pop_front();
            int next = a[j + d];
            for (deque<int>::reverse_iterator ri = maxima.rbegin();
                 ri != maxima.rend() && *ri < next; ++ri)
                *ri = next;
            maxima.push_back(next);
            if (maxima.front() != currentMax)
            {
                currentMax = maxima.front();
                if (currentMax < smallestMax)
                    smallestMax = currentMax;
            }
        }
        cout << smallestMax << endl;
    }
    
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int a[100000],ans[100000],stack1[100000],stack2[100000],left[100000],right[100000],c[100000];

int main(){
  int N,Q,x,p,min,i,j;
  scanf("%d%d",&N,&Q);
  for(i=0;i<N;i++)
    scanf("%d",a+i);
  for(i=p=0;i<N;i++){
    while(p && stack1[p-1]<=a[i])
      p--;
    stack1[p]=a[i];
    stack2[p++]=i;
    if(p==1)
      left[i]=0;
    else
      left[i]=stack2[p-2]+1;
  }
  for(i=N-1,p=0;i>=0;i--){
    while(p && stack1[p-1]<=a[i])
      p--;
    stack1[p]=a[i];
    stack2[p++]=i;
    if(p==1)
      right[i]=N-1;
    else
      right[i]=stack2[p-2]-1;
  }
  for(i=0;i<N;i++)
    c[i]=right[i]-left[i]+1;
  sort_a2(c,a,N);
  for(i=N,j=N-1,min=-1;i>0;i--){
    for(;c[j]==i;j--)
      if(min==-1 || a[j]<min)
        min=a[j];
    ans[i-1]=min;
  }
  while(Q--){
    scanf("%d",&x);
    printf("%dn",ans[x-1]);
  }
  return 0;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}

Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the solve function below.
function solve(arr, queries) {
  const result = [];
  for (let i = 0; i < queries.length; i++) {
    const windowSize = queries[i];
    const tempArr = [];
    let isMaxAtBeginning = false;
    let max = 0;
    for (let j = 0; j < arr.length; j++) {
      let window;
      if (windowSize + j <= arr.length) {
        if (j === 0 || isMaxAtBeginning) {
          window = arr.slice(j, j + windowSize);
          max = window.reduce((a, b) => (a >= b ? a : b));
        }
        else {
          max = Math.max(max, arr[j + windowSize - 1]);
        }
        tempArr.push(max);
        isMaxAtBeginning = max === arr[j];
      }
    }
    result.push(tempArr.reduce((a, b) => (a <= b ? a : b)));
  }
  return result;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nq = readLine().split(' ');

    const n = parseInt(nq[0], 10);

    const q = parseInt(nq[1], 10);

    const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

    let queries = [];

    for (let queriesItr = 0; queriesItr < q; queriesItr++) {
        const queriesItem = parseInt(readLine(), 10);
        queries.push(queriesItem);
    }

    let result = solve(arr, queries);

    ws.write(result.join("n") + "n");

    ws.end();
}