{"id":2672,"date":"2021-10-14T11:00:00","date_gmt":"2021-10-14T05:30:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2672"},"modified":"2021-10-13T18:05:36","modified_gmt":"2021-10-13T12:35:36","slug":"sliding-window-maximum","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/sliding-window-maximum\/","title":{"rendered":"Sliding Window Maximum"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#brute-force-approach\">Brute Force Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java--implementation\">Java <meta charset=\"utf-8\">Implementation<\/a><\/li><li><a href=\"#python--implementation\">Python <meta charset=\"utf-8\">Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-using-deque\">Efficient Approach: Using Deque<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-deque-method\">C++ Code for Deque Method<\/a><\/li><li><a href=\"#java-code-for-deque-method\">Java Code for Deque Method<\/a><\/li><li><a href=\"#python-code-for-deque-method\">Python Code for Deque Method<\/a><\/li><\/ul><li><a href=\"#dynamic-programming-approach\">Dynamic Programming Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-dp-approach\">C++ Code for DP Approach<\/a><\/li><li><a href=\"#java--code-for-dp-approach\">Java <meta charset=\"utf-8\">Code for DP Approach<\/a><\/li><li><a href=\"#python--code-for-dp-approach\">Python <meta charset=\"utf-8\">Code for DP Approach<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions:<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an array of integers A.&nbsp; There is a sliding window of size K which is moving from the very left of the array to the very right.&nbsp;<\/p>\n\n\n\n<p>You can only see the <strong>w<\/strong> numbers in the window. Each time the sliding window moves rightwards by one position. You have to find the maximum for each window.<br>Return an array C, where C[i] is the maximum value from <strong>A[i]<\/strong> to <strong>A[i+K-1]<\/strong>.<br>Note: If <strong>k &gt; length<\/strong> of the array, return <strong>1<\/strong> element with the max of the array.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><br><strong>Input: <\/strong>A[] = {1, 3, -1, -3, 5, 3, 6, 7}, K = 3<br><strong>Output: <\/strong>{3, 3, 5, 5, 6, 7}<br><strong>Explanation:<\/strong><br><\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td>Window position<\/td><td>Max<\/td><\/tr><tr><td>[1 3 -1] -3 5 3 6 7<\/td><td>3<\/td><\/tr><tr><td>1 [3 -1 -3] 5 3 6 7<\/td><td>3<\/td><\/tr><tr><td>1 3 [-1 -3 5] 3 6 7<\/td><td>5<\/td><\/tr><tr><td>1 3 -1 [-3 5 3] 6 7<\/td><td>5<\/td><\/tr><tr><td>1 3 -1 -3 [5 3 6] 7<\/td><td>6<\/td><\/tr><tr><td>1 3 -1 -3 5 [3 6 7]<\/td><td>7<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Input: <\/strong>A[] = {1, -1}, k = 1<br><strong>Output:<\/strong> {1, -1}<\/p>\n\n\n\n<h2 id=\"brute-force-approach\">Brute Force Approach<\/h2>\n\n\n\n<p>The simplest approach to solve this problem is to iterate over all possible sliding windows and find the maximum for each window.<br>There can be a total of N &#8211; K + 1 sliding window and there are <strong>K<\/strong> elements in each window.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Run a loop <strong>i<\/strong> from <strong>0<\/strong> to <strong>N &#8211; K + 1<\/strong>, denoting the current window.<\/li><li>Initialise a variable <strong>max <\/strong>to <strong>INT_MIN <\/strong>to find the maximum value of each window.<\/li><li>Run a nested loop from <strong>j<\/strong> from <strong>i<\/strong> to <strong>i + K<\/strong> to iterate over the elements of the current window and maximize <strong>max<\/strong>.<\/li><li>Store the value of <strong>max<\/strong> for each window and return.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/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=\"\"> \n   vector&lt;int> SlidingWindowMaximum(int A[], int n, int K) {\n        if (n * K == 0){\n             return {};\n        }\n        vector&lt;int> output(n - K + 1, 0);\n        for (int i = 0; i &lt; n - K + 1; i++) {\n            int max = INT_MIN;\n            for(int j = i; j &lt; i + K; j++) \n                max = max(max, A[j]);\n            output[i] = max;\n        }\n        return output;\n    }<\/pre>\n\n\n\n<h3 id=\"java--implementation\"><span id=\"java-implementation\">Java <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int[] SlidingWindowMaximum(int[] A, int K) {\n        int n = nums.length;\n        if (n * K == 0) return new int[0]; \n        int [] output = new int[n - K + 1];\n        for (int i = 0; i &lt; n - K + 1; i++) {\n            int max = Integer.MIN_VALUE;\n            for(int j = i; j &lt; i + K; j++) \n                max = Math.max(max, A[j]);\n            output[i] = max;\n        }\n        return output;\n }<\/pre>\n\n\n\n<h3 id=\"python--implementation\"><span id=\"python-implementation\">Python <meta charset=\"utf-8\">Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> \ndef SlidingWindowMaximum(A, K):\n        n = len(nums)\n        if n * K == 0:\n            return []\n        \n        return [max(A[i:i + K]) for i in range(n - K + 1)]\n \n \n \n<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N * K) where N is the size of the array <strong>A[]<\/strong>.<br><strong>Space Complexity:<\/strong>O(N &#8211; K + 1), as extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-using-deque\">Efficient Approach: Using Deque<\/h2>\n\n\n\n<p>The previous approach takes O(N * K) time, which would give a Time Limit Exceeded error for large values of <strong>K.<\/strong><\/p>\n\n\n\n<p>One of the ideas to reduce the time complexity could be to use a max heap, since the maximum element is always present at the top of the heap, but an insertion in a <strong>max heap <\/strong>of size <strong>K <\/strong>takes O(log K) time. Therefore, the time complexity becomes O(N log K), which is efficient. Can we reduce it further?<\/p>\n\n\n\n<p>The idea is to use a <strong>deque<\/strong> i.e. <strong>double ended queue<\/strong> which performs the <strong>push()<\/strong> and <strong>pop()<\/strong> operations in <strong>O(1)<\/strong> <strong>constant <\/strong>time.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"653\"  height=\"803\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Deque Approach\"  class=\"wp-image-2764 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 653px) 100vw, 653px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Deque-Approach.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Deque-Approach.png 653w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Deque-Approach-244x300.png 244w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Deque-Approach-380x467.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Deque-Approach-550x676.png 550w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:&nbsp;<\/strong><\/p>\n\n\n\n<ul><li>Initialise the first <strong>K<\/strong> elements of the array into the <strong>deque.<\/strong><\/li><li>Iterate over the input array and for each step:<ul><li>Consider only the indices of the elements in the current window.<\/li><li>Pop-out all the indices of elements smaller than the current element, since their value will be less than the current element.<\/li><li>Push the current element into the deque.<\/li><li>Push the first element of the deque i.e. <strong>deque[0] <\/strong>into the output array.<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-deque-method\">C++ Code for Deque Method<\/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=\"\">vector&lt;int> SlidingWindowMaximum(vector&lt;int>&amp; A, int K) {\n        deque&lt;int> dq;\n        vector&lt;int> ans;\n        for (int i=0; i&lt;nums.size(); i++) {\n            if (!dq.empty() &amp;&amp; dq.front() == i-K) dq.pop_front();\n            while (!dq.empty() &amp;&amp; A[dq.back()] &lt; A[i])\n                dq.pop_back();\n            dq.push_back(i);\n            if (i>=K-1) ans.push_back(nums[dq.front()]);\n        }\n        return ans;\n    }\n \n \n<\/pre>\n\n\n\n<h3 id=\"java-code-for-deque-method\">Java Code for Deque Method<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">ArrayDeque&lt;Integer> deq = new ArrayDeque&lt;Integer>();\n  int [] A;\n \n  public void clean_deque(int i, int K) {\n    if (!deq.isEmpty() &amp;&amp; deq.getFirst() == i - K)\n      deq.removeFirst();\n \n \n    while (!deq.isEmpty() &amp;&amp; nums[i] > A[deq.getLast()]){\n\t\tdeq.removeLast();\n\t}\n  }\n \n  public int[] SlidingWindowMaximum(int[] A, int K) {\n    int n = A.length;\n    if (n * B=K == 0) return new int[0];\n    if (K == 1) return A;\n \n    this.A = A;\n    int max_idx = 0;\n    for (int i = 0; i &lt; K; i++) {\n      clean_deque(i, K);\n      deq.addLast(i);\n      if (A[i] > A[max_idx]) max_idx = i;\n    }\n    int [] output = new int[n - K + 1];\n    output[0] = A[max_idx];\n \n    for (int i  = K; i &lt; n; i++) {\n      clean_deque(i, K);\n      deq.addLast(i);\n      output[i - K + 1] = A[deq.getFirst()];\n    }\n    return output;\n  }\n \n <\/pre>\n\n\n\n<h3 id=\"python-code-for-deque-method\">Python Code for Deque Method<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> from collections import deque\n \n    def SlidingWindowMaximum(A, K):\n        n = len(A)\n        if n * K == 0:\n            return []\n        if K == 1:\n            return A\n        \n        def clean_deque(i):\n            if deq and deq[0] == i - K:\n                deq.popleft()\n                \n            while deq and A[i] > A[deq[-1]]:\n                deq.pop()\n        \n        deq = deque()\n        max_idx = 0\n        for i in range(B):\n            clean_deque(i)\n            deq.append(i)\n            if A[i] > A[max_idx]:\n                max_idx = i\n        output = [A[max_idx]]\n        \n        for i in range(K, n):\n            clean_deque(i)          \n            deq.append(i)\n            output.append(A[deq[0]])\n        return output\n \n<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N) where N is the size of the array <strong>A[]<\/strong>.<br><strong>Space Complexity:<\/strong>O(N), as extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"dynamic-programming-approach\">Dynamic Programming Approach<\/h2>\n\n\n\n<p>The problem can be solved using <strong>Dynamic Programming<\/strong>. The approach is to divide the given array into different blocks each containing <strong>K<\/strong> elements. Let us understand the illustration with the below example.<\/p>\n\n\n\n<p><strong>A[]<\/strong> = {1, 3, -1, -3, 5, 3, 6, 7}<br><strong>K<\/strong> = 3<\/p>\n\n\n\n<p>The given array has been divided into parts, each containing <strong>K <\/strong>elements. SInce, the size of the array is not divisible by <strong>K<\/strong>, the last block contains elements less than <strong>K<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"array\"  class=\"wp-image-2765 pk-lazyload\"  width=\"700\"  height=\"196\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 700px) 100vw, 700px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/array-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/array-1.png 702w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/array-1-300x84.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/array-1-380x107.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/array-1-550x154.png 550w\" ><\/figure>\n\n\n\n<p>Two elements can be placed into two different sliding windows, while iterating as follows:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"two elements\"  class=\"wp-image-2766 pk-lazyload\"  width=\"700\"  height=\"322\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 700px) 100vw, 700px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sliding-windows.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sliding-windows.png 702w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sliding-windows-300x138.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sliding-windows-380x175.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/sliding-windows-550x253.png 550w\" ><\/figure>\n\n\n\n<p>To solve <strong>problem<\/strong> <strong>1<\/strong>, consider an auxiliary array <strong>left[]<\/strong> which denotes the maximum element obtained so far until index <strong>j<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"702\"  height=\"534\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"auxiliary array left\"  class=\"wp-image-2767 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 702px) 100vw, 702px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array.png 702w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-300x228.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-380x289.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-550x418.png 550w\" ><\/figure>\n\n\n\n<p>Similarly to solve <strong>problem 2<\/strong>, consider an auxiliary array <strong>right[]<\/strong> which denotes the maximum element obtained so far until index <strong>j<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"702\"  height=\"491\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"auxiliary array right\"  class=\"wp-image-2768 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 702px) 100vw, 702px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-right.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-right.png 702w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-right-300x210.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-right-380x266.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-right-550x385.png 550w\" ><\/figure>\n\n\n\n<p>Now, since we have obtained all the maximum integers uptil <strong>index i<\/strong> from both directions, the maximum element in the sliding window from <strong>index i <\/strong>to <strong>index j<\/strong> is <strong>max(left[i], right[i]).<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"702\"  height=\"650\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"auxiliary array left and right\"  class=\"wp-image-2769 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 702px) 100vw, 702px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-left-and-right.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-left-and-right.png 702w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-left-and-right-300x278.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-left-and-right-380x352.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/auxiliary-array-left-and-right-550x509.png 550w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Construct an array <strong>left[]<\/strong>, which contains the maximum element till index <strong>i<\/strong> iterating from <strong>left <\/strong>to <strong>right.<\/strong><\/li><li>Construct an array <strong>right[]<\/strong>, which contains the maximum element till index <strong>i<\/strong> iterating from <strong>right <\/strong>to <strong>left.<\/strong><\/li><li>For each window size of <strong>N &#8211; K + 1<\/strong>, the maximum element will be <strong>max(left[i], right[N &#8211; i + 1])<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-dp-approach\">C++ Code for DP Approach<\/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=\"\">vector&lt;int> SlidingWindowMaximum(vector&lt;int>&amp; A, int K) {\n        deque&lt;int> dq;\n        vector&lt;int> ans;\n        for (int i=0; i&lt;nums.size(); i++) {\n            if (!dq.empty() &amp;&amp; dq.front() == i-K) dq.pop_front();\n            while (!dq.empty() &amp;&amp; A[dq.back()] &lt; A[i])\n                dq.pop_back();\n            dq.push_back(i);\n            if (i>=K-1) ans.push_back(nums[dq.front()]);\n        }\n        return ans;\n    }\n \n\n<\/pre>\n\n\n\n<h3 id=\"java--code-for-dp-approach\"><span id=\"java-code-for-dp-approach\">Java <meta charset=\"utf-8\">Code for DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int[] SlidingWindowMaximum(int[] A, int K) {\n    int n = A.length;\n    if (n * K == 0) return new int[0];\n    if (K == 1) return nums;\n \n    int [] left = new int[n];\n    left[0] = nums[0];\n    int [] right = new int[n];\n    right[n - 1] = nums[n - 1];\n    for (int i = 1; i &lt; n; i++) {\n      if (i % K == 0) left[i] = nums[i];  \n      else left[i] = Math.max(left[i - 1], A[i]);\n \n      int j = n - i - 1;\n      if ((j + 1) % K == 0) right[j] = A[j];  \/\/ block_end\n      else right[j] = Math.max(right[j + 1], A[j]);\n    }\n \n    int [] output = new int[n - K + 1];\n    for (int i = 0; i &lt; n - K + 1; i++)\n      output[i] = Math.max(left[i + K - 1], right[i]);\n \n    return output;\n  }\n<\/pre>\n\n\n\n<h3 id=\"python--code-for-dp-approach\"><span id=\"python-code-for-dp-approach\">Python <meta charset=\"utf-8\">Code for DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> \ndef SlidingWindowMaximum(A, K):\n        n = len(A)\n        if n * K == 0:\n            return []\n        if K == 1:\n            return A\n        \n        left = [0] * n\n        left[0] = A[0]\n        right = [0] * n\n        right[n - 1] = A[n - 1]\n        for i in range(1, n):\n            # from left to right\n            if i % k == 0:\n                left[i] = A[i]\n            else:\n                left[i] = max(left[i - 1], A[i])\n            j = n - i - 1\n            if (j + 1) % K == 0:\n                right[j] = A[j]\n            else:\n                right[j] = max(right[j + 1], A[j])\n        \n        output = []\n        for i in range(n - K + 1):\n            output.append(max(left[i + K - 1], right[i]))\n            \n        return output\n \n<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong>O(N) where N is the size of the array <strong>A[]<\/strong>.<br><strong>Space Complexity:<\/strong>O(N), as extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions:<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/sliding-window-maximum\/\" target=\"_blank\" rel=\"noreferrer noopener\">Sliding Window Maximum<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What is the time complexity of finding maximum for each window of size K<br><\/strong>The time complexity is <strong>O(N)<\/strong> using a dynamic programming approach.<\/p>\n\n\n\n<p><strong>Can we use a heap to solve the problem?<br><\/strong>Yes, a max heap can be used to solve the problem, but in that case, the time complexity would be O(N log K), since insertion in a max heap takes log(K) time. Here K denotes the size of the sliding window.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array of integers A.&nbsp; There is a sliding window of size K which is&hellip;\n","protected":false},"author":4,"featured_media":2756,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[399,460],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2672"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2672"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2672\/revisions"}],"predecessor-version":[{"id":2770,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2672\/revisions\/2770"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2756"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2672"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2672"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2672"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}