{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiebjdgf5t3avp5uvmhds2cgvx22iyorgciichiz53esj2swmcscri",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mpbzn4ov7762"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreihj24lzds2pjmd7q44yp4lapzm4ut2er6z2ecbimv7g4d2o7qidcq"
    },
    "mimeType": "image/webp",
    "size": 58098
  },
  "path": "/jaspreet_singh_86ae1740ac/sliding-window-maximum-monotonic-deque-2h18",
  "publishedAt": "2026-06-27T17:22:36.000Z",
  "site": "https://dev.to",
  "tags": [
    "algorithms",
    "interview",
    "java",
    "leetcode",
    "leetcode.com"
  ],
  "textContent": "\nleetcode.com\n\n\n##  Problem Statement\n\nGiven an array `nums` and an integer `k`, return the maximum element for every sliding window of size `k`.\n\n##  Brute Force Intuition\n\nIn an interview, you can explain it like this:\n\n> For every window of size `k`, iterate through all its elements and find the maximum.\n\nSince every window is scanned completely, many elements are processed repeatedly.\n\n###  Complexity\n\n  * Time Complexity: **O(N × K)**\n  * Space Complexity: **O(1)**\n\n\n\n###  Brute Force Code\n\n\n    class Solution {\n\n        public int[] maxSlidingWindow(int[] nums, int k) {\n\n            int n = nums.length;\n\n            int[] ans = new int[n - k + 1];\n\n            int index = 0;\n\n            for (int i = 0; i <= n - k; i++) {\n\n                int max = nums[i];\n\n                for (int j = i; j < i + k; j++) {\n\n                    max = Math.max(max, nums[j]);\n                }\n\n                ans[index++] = max;\n            }\n\n            return ans;\n        }\n    }\n\n\n##  Moving Towards the Optimal Approach\n\nNotice that while moving the window:\n\n\n\n    One element leaves\n\n    One element enters\n\n\nDo we really need to calculate the maximum again?\n\nNo.\n\nWe only need to keep the **useful candidates** that can become the maximum.\n\nThis is where a **Monotonic Deque** comes in.\n\n##  Pattern Recognition\n\nWhenever you see:\n\n  * Sliding Window\n  * Maximum / Minimum in every window\n  * Fixed Window Size\n\n\n\nThink:\n\n**Monotonic Deque**\n\n##  Key Observation\n\nMaintain indices in a deque such that:\n\n\n\n    Elements remain in decreasing order.\n\n\nThen:\n\n\n\n    Front of deque\n\n    =\n\n    Maximum of current window\n\n\nWhenever a new element comes:\n\nRemove all smaller elements from the back.\n\nThey can never become the maximum.\n\n##  Optimal Approach\n\nFor every index:\n\n###  Step 1\n\nRemove indices outside the window.\n\n\n\n    deque.peekFirst() <= i - k\n\n\n###  Step 2\n\nRemove smaller elements from the back.\n\n\n\n    nums[deque.peekLast()] <= nums[i]\n\n\n###  Step 3\n\nInsert current index.\n\n###  Step 4\n\nOnce window size becomes `k`:\n\n\n\n    Front of deque\n    =\n    Maximum\n\n\n##  Optimal Java Solution\n\n\n    class Solution {\n\n        public int[] maxSlidingWindow(int[] nums, int k) {\n\n            int n = nums.length;\n\n            int[] ans = new int[n - k + 1];\n\n            Deque<Integer> dq = new ArrayDeque<>();\n\n            int index = 0;\n\n            for (int i = 0; i < n; i++) {\n\n                while (!dq.isEmpty() &&\n                       dq.peekFirst() <= i - k) {\n\n                    dq.pollFirst();\n                }\n\n                while (!dq.isEmpty() &&\n                       nums[dq.peekLast()] <= nums[i]) {\n\n                    dq.pollLast();\n                }\n\n                dq.offerLast(i);\n\n                if (i >= k - 1) {\n\n                    ans[index++] = nums[dq.peekFirst()];\n                }\n            }\n\n            return ans;\n        }\n    }\n\n\n##  Dry Run\n\n###  Input\n\n\n    nums = [1,3,-1,-3,5,3,6,7]\n\n    k = 3\n\n\n###  Window\n\n\n    [1 3 -1]\n\n\nDeque:\n\n\n\n    3\n\n\nMaximum:\n\n\n\n    3\n\n\n###  Window\n\n\n    [3 -1 -3]\n\n\nMaximum:\n\n\n\n    3\n\n\n###  Window\n\n\n    [-1 -3 5]\n\n\nRemove:\n\n\n\n    -3\n\n    -1\n\n\nDeque:\n\n\n\n    5\n\n\nMaximum:\n\n\n\n    5\n\n\nContinue similarly.\n\nFinal Answer:\n\n\n\n    [3,3,5,5,6,7]\n\n\n##  Why Monotonic Deque Works?\n\nEvery index:\n\n\n\n    Inserted once\n\n    Removed once\n\n\nSo each element is processed only one time.\n\nThe deque always maintains candidates in decreasing order.\n\nThe front always stores the maximum element of the current window.\n\n##  Complexity Analysis\n\nMetric | Complexity\n---|---\nTime Complexity | O(N)\nSpace Complexity | O(K)\n\n##  Interview One-Liner\n\n> Maintain a monotonic decreasing deque of indices so the front always represents the maximum element of the current sliding window.\n\n##  Pattern Learned\n\n\n    Sliding Window\n\n    +\n\n    Maximum / Minimum\n\n    ↓\n\n    Monotonic Deque\n\n\n###  Similar Problems\n\n  * Sliding Window Maximum\n  * Sliding Window Minimum\n  * First Negative Integer in Every Window\n  * Shortest Subarray with Sum at Least K\n  * Constrained Subsequence Sum\n\n\n\n##  Memory Trick\n\nThink:\n\n\n\n    New Element Arrives\n\n    ↓\n\n    Remove Smaller Elements\n\n    ↓\n\n    Insert Current Index\n\n    ↓\n\n    Front = Maximum\n\n\n###  Mental Model\n\n\n    Sliding Window\n\n    ↓\n\n    Useful Candidates Only\n\n    ↓\n\n    Deque\n\n    ↓\n\n    Front Always Maximum\n\n\nWhenever you hear:\n\n> \"Maximum in every sliding window\"\n\nyour brain should immediately think:\n\n**Monotonic Deque**",
  "title": "Sliding Window Maximum | Monotonic Deque"
}