Algorithm


Problem Name: Data Structures - Queries with Fixed Length

Problem Link: https://www.hackerrank.com/challenges/queries-with-fixed-length/problem?isFullScreen=true

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 & Try With Live Editor

#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 & Try With Live Editor

#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);
    }
}
Copy The Code & Try With Live Editor

#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();
}
Copy The Code & Try With Live Editor

#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 & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Truck Tour solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Super Maximum Cost Queries solution in Hackerrank - Hacerrank solution C, C++, java,js, Python