Overview

Monotonic Queue is a deque (double-ended queue) that maintains elements in monotonic order while supporting efficient insertion and deletion from both ends. It's an extension of monotonic stack, optimized for sliding window problems.

The key insight: maintain a deque where elements are ordered, and remove elements that fall outside the window or violate the monotonic property. This enables O(1) access to min/max in sliding windows.

Monotonic queue is particularly useful for:

Sliding window maximum/minimum
Range queries in sliding windows
Optimizing DP with sliding window
Finding min/max in subarrays
Constrained optimization problems

Pattern 1: Sliding Window Maximum

Find maximum in each sliding window of size K.

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices with smaller values (maintain decreasing order)
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add maximum to result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time: O(n), Space: O(k)

Explanation: Deque stores indices in decreasing order of values. Front always has maximum.

Pattern 2: Sliding Window Minimum

Find minimum in each sliding window of size K.

function minSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices with larger values (maintain increasing order)
    while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add minimum to result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time: O(n), Space: O(k)

Pattern 3: Constrained Subsequence Sum

Find maximum sum subsequence with at most K elements between consecutive picks.

function constrainedSubsetSum(nums: number[], k: number): number {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  const deque: number[] = [];
  
  let maxSum = -Infinity;
  
  for (let i = 0; i < n; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] < i - k) {
      deque.shift();
    }
    
    // DP: max sum ending at i
    dp[i] = nums[i] + (deque.length > 0 ? Math.max(0, dp[deque[0]]) : 0);
    maxSum = Math.max(maxSum, dp[i]);
    
    // Maintain decreasing order of dp values
    while (deque.length > 0 && dp[deque[deque.length - 1]] <= dp[i]) {
      deque.pop();
    }
    
    deque.push(i);
  }
  
  return maxSum;
}

Time: O(n), Space: O(n)

Pattern 4: Shortest Subarray with Sum at Least K

Find shortest subarray with sum >= K (handles negatives).

function shortestSubarray(nums: number[], k: number): number {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  
  // Build prefix sum
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  
  const deque: number[] = [];
  let minLen = Infinity;
  
  for (let i = 0; i <= n; i++) {
    // Remove indices where prefix[i] <= prefix[deque.back()]
    // (no point keeping larger prefix sums)
    while (deque.length > 0 && prefix[i] <= prefix[deque[deque.length - 1]]) {
      deque.pop();
    }
    
    // Check for valid subarray
    while (deque.length > 0 && prefix[i] - prefix[deque[0]] >= k) {
      minLen = Math.min(minLen, i - deque[0]);
      deque.shift();
    }
    
    deque.push(i);
  }
  
  return minLen === Infinity ? -1 : minLen;
}

Time: O(n), Space: O(n)

Key insight: Maintain increasing prefix sums. If current prefix is smaller, previous larger ones are useless.

Pattern 5: Jump Game VI

Maximum score with at most K steps.

function maxResult(nums: number[], k: number): number {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  
  const deque: number[] = [0];
  
  for (let i = 1; i < n; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] < i - k) {
      deque.shift();
    }
    
    // DP: max score to reach i
    dp[i] = dp[deque[0]] + nums[i];
    
    // Maintain decreasing order of dp values
    while (deque.length > 0 && dp[deque[deque.length - 1]] <= dp[i]) {
      deque.pop();
    }
    
    deque.push(i);
  }
  
  return dp[n - 1];
}

Time: O(n), Space: O(n)

Pattern 6: Maximum Number of Robots Within Budget

Find maximum robots that can run within budget.

function maximumRobots(chargeTimes: number[], runningCosts: number[], budget: number): number {
  const n = chargeTimes.length;
  const deque: number[] = [];
  let left = 0;
  let sum = 0;
  let maxRobots = 0;
  
  for (let right = 0; right < n; right++) {
    // Add current robot
    sum += runningCosts[right];
    
    // Maintain decreasing order of charge times
    while (deque.length > 0 && chargeTimes[deque[deque.length - 1]] <= chargeTimes[right]) {
      deque.pop();
    }
    deque.push(right);
    
    // Shrink window if exceeds budget
    while (left <= right && 
           chargeTimes[deque[0]] + sum * (right - left + 1) > budget) {
      sum -= runningCosts[left];
      
      // Remove indices outside window
      if (deque[0] === left) {
        deque.shift();
      }
      
      left++;
    }
    
    maxRobots = Math.max(maxRobots, right - left + 1);
  }
  
  return maxRobots;
}

Time: O(n), Space: O(n)

Pattern 7: Longest Continuous Subarray with Absolute Diff <= Limit

Find longest subarray where max - min <= limit.

function longestSubarray(nums: number[], limit: number): number {
  const maxDeque: number[] = []; // Decreasing order
  const minDeque: number[] = []; // Increasing order
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < nums.length; right++) {
    // Maintain max deque (decreasing)
    while (maxDeque.length > 0 && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
      maxDeque.pop();
    }
    maxDeque.push(right);
    
    // Maintain min deque (increasing)
    while (minDeque.length > 0 && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
      minDeque.pop();
    }
    minDeque.push(right);
    
    // Shrink window if diff exceeds limit
    while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
      if (maxDeque[0] === left) maxDeque.shift();
      if (minDeque[0] === left) minDeque.shift();
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(n)

Explanation: Use two deques to track max and min in window.

Pattern 8: Sliding Window Median

Find median in each sliding window (using two heaps + lazy deletion).

class SlidingWindowMedian {
  private maxHeap: number[]; // Lower half
  private minHeap: number[]; // Upper half
  private removed: Map<number, number>;
  private balance: number;
  
  constructor() {
    this.maxHeap = [];
    this.minHeap = [];
    this.removed = new Map();
    this.balance = 0;
  }
  
  addNum(num: number): void {
    if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) {
      this.maxHeap.push(-num);
      this.heapifyUp(this.maxHeap, true);
      this.balance++;
    } else {
      this.minHeap.push(num);
      this.heapifyUp(this.minHeap, false);
      this.balance--;
    }
    
    this.rebalance();
    this.lazyDelete();
  }
  
  removeNum(num: number): void {
    this.removed.set(num, (this.removed.get(num) || 0) + 1);
    
    if (num <= -this.maxHeap[0]) {
      this.balance--;
    } else {
      this.balance++;
    }
    
    this.rebalance();
    this.lazyDelete();
  }
  
  findMedian(): number {
    this.lazyDelete();
    
    if (this.balance === 0) {
      return (-this.maxHeap[0] + this.minHeap[0]) / 2;
    } else {
      return -this.maxHeap[0];
    }
  }
  
  private rebalance(): void {
    if (this.balance > 1) {
      const val = -this.maxHeap[0];
      this.maxHeap[0] = this.maxHeap[this.maxHeap.length - 1];
      this.maxHeap.pop();
      this.heapifyDown(this.maxHeap, true);
      
      this.minHeap.push(val);
      this.heapifyUp(this.minHeap, false);
      this.balance -= 2;
    } else if (this.balance < -1) {
      const val = this.minHeap[0];
      this.minHeap[0] = this.minHeap[this.minHeap.length - 1];
      this.minHeap.pop();
      this.heapifyDown(this.minHeap, false);
      
      this.maxHeap.push(-val);
      this.heapifyUp(this.maxHeap, true);
      this.balance += 2;
    }
  }
  
  private lazyDelete(): void {
    while (this.maxHeap.length > 0 && this.removed.get(-this.maxHeap[0]) > 0) {
      const val = -this.maxHeap[0];
      this.removed.set(val, this.removed.get(val)! - 1);
      this.maxHeap[0] = this.maxHeap[this.maxHeap.length - 1];
      this.maxHeap.pop();
      this.heapifyDown(this.maxHeap, true);
    }
    
    while (this.minHeap.length > 0 && this.removed.get(this.minHeap[0]) > 0) {
      const val = this.minHeap[0];
      this.removed.set(val, this.removed.get(val)! - 1);
      this.minHeap[0] = this.minHeap[this.minHeap.length - 1];
      this.minHeap.pop();
      this.heapifyDown(this.minHeap, false);
    }
  }
  
  private heapifyUp(heap: number[], isMax: boolean): void {
    let i = heap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if ((isMax && heap[parent] >= heap[i]) || (!isMax && heap[parent] <= heap[i])) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }
  
  private heapifyDown(heap: number[], isMax: boolean): void {
    let i = 0;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      
      if (left < heap.length && ((isMax && heap[left] > heap[largest]) || (!isMax && heap[left] < heap[largest]))) {
        largest = left;
      }
      if (right < heap.length && ((isMax && heap[right] > heap[largest]) || (!isMax && heap[right] < heap[largest]))) {
        largest = right;
      }
      
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  }
}

function medianSlidingWindow(nums: number[], k: number): number[] {
  const medianFinder = new SlidingWindowMedian();
  const result: number[] = [];
  
  // Initialize first window
  for (let i = 0; i < k; i++) {
    medianFinder.addNum(nums[i]);
  }
  result.push(medianFinder.findMedian());
  
  // Slide window
  for (let i = k; i < nums.length; i++) {
    medianFinder.removeNum(nums[i - k]);
    medianFinder.addNum(nums[i]);
    result.push(medianFinder.findMedian());
  }
  
  return result;
}

Time: O(n log k), Space: O(k)

Pattern 9: Maximum Score from Removing Substrings

Maximize score by removing substrings.

function maximumGain(s: string, x: number, y: number): number {
  let score = 0;
  const stack: string[] = [];
  
  // Remove higher value substring first
  const first = x > y ? 'ab' : 'ba';
  const second = x > y ? 'ba' : 'ab';
  const firstScore = Math.max(x, y);
  const secondScore = Math.min(x, y);
  
  // First pass: remove first substring
  for (const char of s) {
    if (stack.length > 0 && stack[stack.length - 1] + char === first) {
      stack.pop();
      score += firstScore;
    } else {
      stack.push(char);
    }
  }
  
  // Second pass: remove second substring
  const remaining: string[] = [];
  for (const char of stack) {
    if (remaining.length > 0 && remaining[remaining.length - 1] + char === second) {
      remaining.pop();
      score += secondScore;
    } else {
      remaining.push(char);
    }
  }
  
  return score;
}

Time: O(n), Space: O(n)

Pattern 10: Minimum Cost to Make Array Equal

Minimize cost to make all elements equal.

function minCost(nums: number[], cost: number[]): number {
  const n = nums.length;
  const indices = Array.from({ length: n }, (_, i) => i);
  
  // Sort by value
  indices.sort((a, b) => nums[a] - nums[b]);
  
  // Prefix sum of costs
  const prefixCost = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefixCost[i + 1] = prefixCost[i] + cost[indices[i]];
  }
  
  // Find median (weighted by cost)
  const totalCost = prefixCost[n];
  let medianIndex = 0;
  
  for (let i = 0; i < n; i++) {
    if (prefixCost[i + 1] >= totalCost / 2) {
      medianIndex = i;
      break;
    }
  }
  
  const target = nums[indices[medianIndex]];
  
  // Calculate cost
  let minCost = 0;
  for (let i = 0; i < n; i++) {
    minCost += Math.abs(nums[i] - target) * cost[i];
  }
  
  return minCost;
}

Time: O(n log n), Space: O(n)

When to Use Monotonic Queue

Use monotonic queue when:

Sliding window problems with min/max queries
Need O(1) access to window min/max
DP optimization with sliding window constraint
Range queries in moving windows
Constrained optimization problems

Key distinction: Monotonic queue supports both ends (deque), while monotonic stack only supports one end.

Template (Sliding Window Maximum)

function slidingWindowMaxTemplate(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Maintain monotonic decreasing order
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Template (Sliding Window Minimum)

function slidingWindowMinTemplate(nums: number[], k: number): number[] {
  const result: number[] = [];
  const deque: number[] = []; // Store indices
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Maintain monotonic increasing order
    while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time and Space Complexity Summary

Sliding window max/min: O(n) time, O(k) space
Constrained subsequence: O(n) time, O(n) space
Shortest subarray: O(n) time, O(n) space
Jump game: O(n) time, O(n) space
Longest subarray with diff: O(n) time, O(n) space
Sliding window median: O(n log k) time, O(k) space

Practice Tips

Store indices - Usually store indices, not values
Maintain order - Keep deque in monotonic order
Remove expired - Remove indices outside window
Two deques - Use two deques for min and max
DP optimization - Combine with dynamic programming

Common Mistakes

Wrong order - Using increasing when need decreasing
Index errors - Not removing expired indices correctly
Window size - Off-by-one in window size check
Empty deque - Not handling empty deque cases
Balance - Not maintaining proper balance in two-deque problems

Related Concepts

Monotonic Stack - Similar but single-ended
Sliding Window - Core application area
Dynamic Programming - Often combined
Deque - Core data structure

Monotonic queue is essential for sliding window optimization. Master this technique, and you'll efficiently solve sliding window min/max problems and related DP optimizations in coding interviews.

Binary Search