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("%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;
}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();
}
0 Comments