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
#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:-
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 "
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 "
can't understand your logic. can you explain it step to step?
ReplyDelete#include
ReplyDelete#include
using namespace std;
void printKMax(int arr[], int n, int k){
//Write your code here.
int temp ;
int a= k-1 ;
int x = 0 ;
for (int j = k-1 ; j < n ; j++)
{
temp = arr[j] ;
for (int i = 1 ; i < k ; i++ )
{
a -= 1 ;
if(temp < arr[a]){
temp = arr[a] ;
}
}
cout << temp << " " ;
x+=1 ;
a = k-1+x ;
}
cout << endl ;
}
int main(){
int t;
cin >> t;
while(t>0) {
int n,k;
cin >> n >> k;
int i;
int arr[n];
for(i=0;i> arr[i];
printKMax(arr, n, k);
t--;
}
return 0;
}