HackerRank Solution For Deque-STL in C/C++

Problem:- Deque-STL Discussion | C++ Question | HackerRank solution or deque-stl hackerrank solution or deque c++ example or deque-stl hacker rank program in c++ or double ended queue in c++ using arrays or hackerrank stl or deque hackerrank solution or double ended queue c++ solution or hackerrank c++ solutions or hackerrank c++ domain solutions or c++ practice online or Deque-STL Hacker Rank Solution 

Introduction

Double ended queue or Deque(part of C++ STL) are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back). The member functions of deque that are mainly used are:

Deque Template:

std::deque<value_type>

Declaration:

deque<int> mydeque; //Creates a double-ended queue of deque of int type

Size

int length = mydeque.size(); //Gives the size of the deque

Push

mydeque.push_back(1); //Pushes element at the end
mydeque.push_front(2); //Pushes element at the beginning

Pop

mydeque.pop_back(); //Pops element from the end
mydeque.pop_front(); //Pops element from the beginning

Empty

mydeque.empty() //Returns a boolean value which tells whether the deque is empty or not

Task

Given a set of arrays of size N and an integer K, you have to find the maximum integer for each and every contiguous subarray of size N for each of the given arrays.

Explanation:- Deque-STL is a double-ended queue. Logic is a very simple first number denotes the number of test case's given after that size of an array N and size of a sub-array K is given. Now we have to print the greatest number formed by sub-array. and print the greatest number each time. Let's take an example and try to understand the problem in a simple step. 

Example:-

1
7 4
3 4 5 8 1 4 10

here 1 is the total number of test cases and 7 is the size of an array and 4 is a size of sub-array formed by array, so for a given array sub-array will be {3, 4, 5, 8 }, {4, 5, 8, 1 }, {5, 8, 1, 4 }, {8, 1, 4, 10 }. Now our task is to print the largest number of these sub-array, So finally our output should be {8, 8, 8, 10 }.

Submit Your Solution Here:- Click Here

Solution:-  Deque-STL Hacker Rank Solution in C/C++

#include<bits/stdc++.h>
#include <deque>
using namespace std;

void printKMax(int arr[], int n, int k)
{
    deque<int> De_que;
    int i;
    
    for(i=0; i<k; i++)
    {
        while(!De_que.empty() && arr[i]>=arr[De_que.back()])
{
            De_que.pop_back();
        }
        De_que.push_back(i);
    }
    
    for(i=k; i<n; i++)
{
        cout<<arr[De_que.front()]<<" ";
        
        while(!De_que.empty() && De_que.front()<=i-k)
{
            De_que.pop_front();
        }
        while(!De_que.empty() && arr[i]>=arr[De_que.back()])
{
            De_que.pop_back();
        }
        De_que.push_back(i);
        
    }
    cout<<arr[De_que.front()]<<endl;
}

int main()
{

   int t;
   scanf("%d",&t);
   while(t--) 
   {
      int n,k;
      cin>>n>>k;
       int i;
      int * arr=new int [n];
       for(i=0;i<n;i++)
           cin>>arr[i];
       printKMax(arr, n, k);
       
     }
     return 0;
}

Output:-

You May Also See

1. Geeksforgeeks Solution For " Count Squares "

2. Geeksforgeeks Solution For " Square Divisors "

3. Geeksforgeeks Solution For " Sum of divisors "

4. Geeksforgeeks Solution For " Different ways to Spell a Number "

5. Geeksforgeeks Solution For " Maximize sum after K negations "