Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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;
}
#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++) {
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);
}
}
#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();
});
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();
}
#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)