## Algorithm

Problem Name: Data Structures - Queries with Fixed Length

In this HackerRank in Data Structures - Queries with Fixed Length solutions

Consider an n-integer sequence, A = {a0 , a1, ... , an-1}. We perform a query on A by using an integer, d, to calculate the result of the following expression:

min (maxa j)

0 <= i <= n - d      i <= j <= i + d

In other words, if we let mi = max(ai, ai + 1,ai + 2, .... , ai+d-1), then you need to calculate min(m0 , m1, ... , mn-d)

Given arr and q queries, return a list of answers to each query.

Example

arr = [2,3,4,5,6]

queries = [2,3]

The first query uses all of the subarrays of length 2: [2,3],[3,4],[4,5],[5,6]. The maxima of the subarrays are [3,4,5,6]. The minimum of these is 3.

The second query uses all of the subarrays of length 3: [2,3,4],[3,4,5],[4,5,6]. The maxima of the subarrays are [4,5,6].  The minimum of these is 4.

Return [3,4].

Function Description

Complete the solve function below.

solve has the following parameter(s):

• int arr[n]: an array of integers
• int queries[q]: the lengths of subarrays to query

Returns

• int[q]: the answers to each query

Input Format

The first line consists of two space-separated integers, n and q.

The second line consists of n space-separated integers, the elements of arr.

Each of the q subsequent lines contains a single integer denoting the value of d for that query.

Constraints

• 1 <= n <= 10**5
• 0 <= arr[i] <= 10**6
• 1 <= q <= 100
• 1 <= d <= n

Sample Input 0

5 5
33 11 44 11 55
1
2
3
4
5


Sample Output 0

11
33
44
44
55


## Code Examples

### #1 Code Example with C Programming

Code - 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("%d\n",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;
}

Copy The Code &

### #2 Code Example with C++ Programming

Code - 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;
}

Copy The Code &

### #3 Code Example with Java Programming

Code - 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++) {
}
int min = deque.peekFirst();

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

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);
}
}

Copy The Code &

### #4 Code Example with Javascript Programming

Code - 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();
});

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 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++) {
queries.push(queriesItem);
}

let result = solve(arr, queries);

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

ws.end();
}

Copy The Code &

### #5 Code Example with Python Programming

Code - 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)

Copy The Code &