HackerRank C++ Deque-STL




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 K for each of the given arrays.



  1. #include<bits/stdc++.h>
  2. #include <deque>
  3. using namespace std;
  4. void printKMax(int arr[], int n, int k)
  5. {
  6. deque<int> De_que;
  7. int i;
  8. for(i=0; i<k; i++)
  9. {
  10. while(!De_que.empty() && arr[i]>=arr[De_que.back()])
  11. {
  12. De_que.pop_back();
  13. }
  14. De_que.push_back(i);
  15. }
  16. for(i=k; i<n; i++)
  17. {
  18. cout<<arr[De_que.front()]<<" ";
  19. while(!De_que.empty() && De_que.front()<=i-k)
  20. {
  21. De_que.pop_front();
  22. }
  23. while(!De_que.empty() && arr[i]>=arr[De_que.back()])
  24. {
  25. De_que.pop_back();
  26. }
  27. De_que.push_back(i);
  28. }
  29. cout<<arr[De_que.front()]<<endl;
  30. }
  31. int main()
  32. {
  33. int t;
  34. scanf("%d",&t);
  35. while(t--)
  36. {
  37. int n,k;
  38. cin>>n>>k;
  39. int i;
  40. int * arr=new int [n];
  41. for(i=0;i<n;i++)
  42. cin>>arr[i];
  43. printKMax(arr, n, k);
  44. }
  45. return 0;
  46. }




codesadda.com

Codesadda.com is your home of programming solutions, tutorials, video tutorials and much more. Sign Up for our weekly newsletter to get update about new content.

Like us on Facebook | Connect with us on LinkedIn | Subscribe our Channel on Youtube