{"id":1790,"date":"2021-05-26T15:19:17","date_gmt":"2021-05-26T09:49:17","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=1790"},"modified":"2021-07-31T23:09:50","modified_gmt":"2021-07-31T17:39:50","slug":"deque-stl-cpp-solution","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/","title":{"rendered":"Deque-STL in C++ | HackerRank Solution"},"content":{"rendered":"\n<p>Hello coders, today we are going to solve <strong>Deque-STL HackerRank Solution in C++<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" width=\"1200\" height=\"675\" src=\"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/05\/deque-stl-c-solution-codingbroz.png\" alt=\"Deque-STL\" class=\"wp-image-1792\" srcset=\"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/05\/deque-stl-c-solution-codingbroz.png 1200w, https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/05\/deque-stl-c-solution-codingbroz-768x432.png 768w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><\/figure>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 ez-toc-wrap-left counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<label for=\"ez-toc-cssicon-toggle-item-662eaffde729d\" class=\"ez-toc-cssicon-toggle-label\"><label class=\"ez-toc-title\">Table of Contents<\/label>\n<span class=\"ez-toc-cssicon\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #0090ff;color:#0090ff\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #0090ff;color:#0090ff\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-662eaffde729d\" checked \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#Problem\" title=\"Problem\">Problem<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#Input_Format\" title=\"Input Format\">Input Format<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#Constraints\" title=\"Constraints\">Constraints<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#Output_Format\" title=\"Output Format\">Output Format<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#Explanation\" title=\"Explanation\">Explanation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#Solution_%E2%80%93_Deque-STL_in_C\" title=\"Solution &#8211; Deque-STL in C++\">Solution &#8211; Deque-STL in C++<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.codingbroz.com\/deque-stl-cpp-solution\/#C\" title=\"C++\">C++<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Problem\"><\/span><strong>Problem<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>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:<\/p>\n\n\n\n<ul><li><em>Deque Template:<\/em><\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>std::deque&lt;value_type&gt;\n<\/code><\/pre>\n\n\n\n<ul><li><em>Declaration:<\/em><\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>deque&lt;int&gt; mydeque; \/\/Creates a double ended queue of deque of int type<\/code><\/pre>\n\n\n\n<ul><li><em>Size<\/em><\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>int length = mydeque.size(); \/\/Gives the size of the deque<\/code><\/pre>\n\n\n\n<ul><li><em>Push<\/em><\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>mydeque.push_back(1); \/\/Pushes element at the end\nmydeque.push_front(2); \/\/Pushes element at the beginning<\/code><\/pre>\n\n\n\n<ul><li><em>Pop<\/em><\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>mydeque.pop_back(); \/\/Pops element from the end\nmydeque.pop_front(); \/\/Pops element from the beginning<\/code><\/pre>\n\n\n\n<ul><li><em>Empty<\/em><\/li><\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>mydeque.empty() \/\/Returns a boolean value which tells whether the deque is empty or not<\/code><\/pre>\n\n\n\n<p>Given a set of arrays of size&nbsp;<strong><em>N<\/em><\/strong>&nbsp;and an integer&nbsp;<strong><em>K<\/em><\/strong>, you have to find the maximum integer for each and every contiguous subarray of size&nbsp;<strong><em>K<\/em><\/strong>&nbsp;for each of the given arrays.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Input_Format\"><\/span><strong>Input Format<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>First line of input will contain the number of test cases&nbsp;<em>T<\/em>. For each test case, you will be given the size of array&nbsp;<em>N<\/em>&nbsp;and the size of subarray to be used&nbsp;<em>K<\/em>. This will be followed by the elements of the array&nbsp;<em>A<sub>i<\/sub><\/em>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Constraints\"><\/span><strong>Constraints<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul><li><strong>1 &lt;= <em>T<\/em> &lt;= 1000<\/strong><\/li><li><strong>1 &lt;= <em>N<\/em> &lt;= 10000<\/strong><\/li><li><strong>1 &lt;= <em>K<\/em> &lt;= <em>N<\/em><\/strong> <\/li><li><strong>1 &lt;= <em>A<\/em><sub><em>i<\/em><\/sub> &lt;= 10000<\/strong>, where <strong><em>A<\/em><sub><em>i<\/em><\/sub><\/strong> is the <strong><em>i<\/em><sup><em>th<\/em><\/sup><\/strong> element in the Array <em><strong>A<\/strong><\/em>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Output_Format\"><\/span><strong>Output Format<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>For each of the contiguous subarrays of size&nbsp;<strong><em>K<\/em><\/strong>&nbsp;of each array, you have to print the maximum integer.<\/p>\n\n\n\n<p><strong>Sample Input<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>2\n5 2\n3 4 6 3 4\n7 4\n3 4 5 8 1 4 10<\/code><\/pre>\n\n\n\n<p><strong>Sample Output<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>4 6 6 4\n8 8 8 10<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Explanation\"><\/span><strong>Explanation<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>For the first case, the contiguous subarrays of size 2 are {3,4},{4,6},{6,3} and {3,4}. The 4 maximum elements of subarray of size 2 are: 4 6 6 4.<\/p>\n\n\n\n<p>For the second case,the contiguous subarrays of size 4 are {3,4,5,8},{4,5,8,1},{5,8,1,4} and {8,1,4,10}. The 4 maximum element of subarray of size 4 are: 8 8 8 10.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution_%E2%80%93_Deque-STL_in_C\"><\/span><strong>Solution &#8211; Deque-STL in C++<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"C\"><\/span><strong>C++<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">#include &lt;iostream>\n#include &lt;deque> \nusing namespace std;\n\nvoid printKMax(int arr[], int n, int k){\n\t\/\/Write your code here.\n    std::deque&lt;int>  dq(k);\n    int i;\n    for (i = 0; i &lt; k; ++i) {\n        while ( (!dq.empty()) &amp;&amp; arr[i] >= arr[dq.back()])\n            dq.pop_back();\n \n        dq.push_back(i);\n    }\n \n    for ( ; i &lt; n; ++i) {\n        cout &lt;&lt; arr[dq.front()] &lt;&lt; \" \";\n \n        while ( (!dq.empty()) &amp;&amp; dq.front() &lt;= i - k)\n            dq.pop_front();\n \n        while ( (!dq.empty()) &amp;&amp; arr[i] >= arr[dq.back()])\n            dq.pop_back();\n \n        dq.push_back(i);\n    }\n \n    cout &lt;&lt; arr[dq.front()] &lt;&lt; endl;\n}\n\nint main(){\n  \n\tint t;\n\tcin >> t;\n\twhile(t>0) {\n\t\tint n,k;\n    \tcin >> n >> k;\n    \tint i;\n    \tint arr[n];\n    \tfor(i=0;i&lt;n;i++)\n      \t\tcin >> arr[i];\n    \tprintKMax(arr, n, k);\n    \tt--;\n  \t}\n  \treturn 0;\n}<\/pre>\n\n\n\n<script async=\"\" src=\"https:\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script>\n<ins class=\"adsbygoogle\" style=\"display:block; text-align:center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-5246141430412355\" data-ad-slot=\"8798433565\"><\/ins>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script>\n\n\n\n<p><strong>Disclaimer:<\/strong> The above Problem <strong>(<a href=\"https:\/\/www.hackerrank.com\/challenges\/deque-stl\/problem\" target=\"_blank\" rel=\"noreferrer noopener\" class=\"rank-math-link\">Deque-STL<\/a>)<\/strong> is generated by <strong>Hacker Rank<\/strong> but the Solution is Provided by <strong>CodingBroz<\/strong>. This tutorial is only for <strong>Educational<\/strong> and <strong>Learning<\/strong> Purpose.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello coders, today we are going to solve Deque-STL HackerRank Solution in C++.<\/p>\n","protected":false},"author":1,"featured_media":1792,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[9,159],"tags":[80,81,18],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/05\/deque-stl-c-solution-codingbroz.png","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/1790"}],"collection":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/comments?post=1790"}],"version-history":[{"count":4,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/1790\/revisions"}],"predecessor-version":[{"id":3884,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/1790\/revisions\/3884"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media\/1792"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=1790"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=1790"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=1790"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}