Monotonic Queue

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

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

Common Mistakes

1. Wrong order - Using increasing when need decreasing
2. Index errors - Not removing expired indices correctly
3. Window size - Off-by-one in window size check
4. Empty deque - Not handling empty deque cases
5. 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.