Using Monotonic Queue
1. Understanding Monotonic Queue Technique
A monotonic queue is a data structure that maintains elements in either strictly increasing or decreasing order. It's particularly useful for solving problems involving sliding windows, maximum/minimum values, and optimization tasks where elements need to be efficiently tracked in a specific order.
| Property | Description | Usage |
|---|---|---|
| Monotonic Increasing | Elements are maintained in ascending order from left to right | Used for finding minimums in sliding windows |
| Monotonic Decreasing | Elements are maintained in descending order from left to right | Used for finding maximums in sliding windows |
Example: Basic Monotonic Queue Implementation
class MonotonicQueue {
constructor(isIncreasing = true) {
this.queue = [];
this.isIncreasing = isIncreasing;
}
push(val) {
while (this.queue.length &&
((this.isIncreasing && this.queue[this.queue.length - 1] > val) ||
(!this.isIncreasing && this.queue[this.queue.length - 1] < val))) {
this.queue.pop();
}
this.queue.push(val);
}
pop(val) {
if (this.queue.length && this.queue[0] === val) {
this.queue.shift();
}
}
front() {
return this.queue.length ? this.queue[0] : null;
}
}
// Example usage:
const mq = new MonotonicQueue(false); // Decreasing
mq.push(3);
mq.push(1);
mq.push(5);
console.log(mq.front()); // 5
Note: The monotonic property ensures that elements are always in order, making it efficient to access the minimum or maximum element at any time.
Key Characteristics
- Elements are maintained in a specific order (increasing or decreasing)
- Efficient insertion and removal operations
- Supports quick access to extremal values (min/max)
2. Finding Sliding Window Maximum
Use a monotonic queue to efficiently find the maximum value in each sliding window of size k over an array.
| Property | Description | Example |
|---|---|---|
| Input | Array of integers and window size k |
[1, 3, -1, -3, 5, 3, 6, 7], k = 3 |
| Output | Array of maximum values for each window | [3, 3, 5, 5, 6, 7] |
Example: Sliding Window Maximum
const maxSlidingWindow = (nums, k) => {
const deque = [];
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove indices that are out of the current window
while (deque.length && deque[0] <= i - k) {
deque.shift();
}
// Remove indices whose values are less than current element
while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
deque.pop();
}
deque.push(i);
// Start adding results once the first window is processed
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
};
// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k)); // [3, 3, 5, 5, 6, 7]
Note: The deque stores indices of array elements in decreasing order of their values.
Algorithm Summary
- Maintain a deque storing indices of elements in decreasing order.
- For each new element, remove indices from the front if they are out of window.
- Remove indices from the back if their values are less than current element.
- Add current index to deque.
- Once the first window is formed, record the front element's value as maximum.
3. Finding Sliding Window Minimum
Use a monotonic queue to efficiently find the minimum element in each sliding window of size k over an array.
| Property | Description | Values |
|---|---|---|
| Array | Input array of integers | [1, 3, -1, -3, 5, 3, 6, 7] |
| Window Size | Size of the sliding window | k = 3 |
| Output | Array of minimums for each window | [-1, -3, 3, 3] |
Example: Sliding Window Minimum
const slidingWindowMinimum = (nums, k) => {
const result = [];
const deque = []; // stores indices
for (let i = 0; i < nums.length; i++) {
// Remove indices that are out of the current window
while (deque.length > 0 && deque[0] <= i - k) {
deque.shift();
}
// Remove indices whose values are greater than current element
while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
deque.pop();
}
deque.push(i);
// Start adding results once the first window is processed
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
};
// Example usage
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(slidingWindowMinimum(nums, k)); // [-1, -3, 3, 3]
Note: The deque maintains indices in increasing order of their corresponding values, ensuring the front of the deque always holds the index of the minimum element in the current window.
4. Finding Shortest Subarray with Sum ≥ K
Use a monotonic queue to efficiently find the shortest subarray with sum greater than or equal to a target value.
| Property | Description | Notes |
|---|---|---|
| Input | Array of integers, target sum K | |
| Output | Length of shortest subarray with sum ≥ K | Returns -1 if no such subarray exists |
Example: Finding Shortest Subarray with Sum ≥ K
function shortestSubarrayWithSum(arr, k) {
let prefixSum = 0;
let minLen = Infinity;
let deque = [];
for (let i = 0; i < arr.length; i++) {
prefixSum += arr[i];
if (prefixSum >= k) {
minLen = Math.min(minLen, i + 1);
}
while (deque.length > 0 && prefixSum - deque[0][1] >= k) {
minLen = Math.min(minLen, i - deque[0][0]);
deque.shift();
}
while (deque.length > 0 && deque[deque.length - 1][1] >= prefixSum) {
deque.pop();
}
deque.push([i, prefixSum]);
}
return minLen === Infinity ? -1 : minLen;
}
// Example usage:
const arr = [2, 1, 3, -1, 4];
const k = 5;
console.log(shortestSubarrayWithSum(arr, k)); // Output: 2 (subarray [1,3] or [3,-1,4])
Note: The deque stores pairs of indices and prefix sums to maintain a monotonic property for efficient subarray length calculation.
5. Finding Jump Game VI Solution
The Jump Game VI problem involves finding the maximum score achievable by jumping through an array, where each jump can move at most k positions forward. The solution uses a monotonic queue to efficiently maintain the maximum score in a sliding window.
| Property | Description | Value |
|---|---|---|
| Array | Input array of integers representing scores at each position | [1, -1, 4, 2, 3] |
| k | Maximum number of positions to jump forward | 2 |
| Result | Maximum score achievable from index 0 to end | 7 |
Example: Jump Game VI Solution
function maxScore(nums, k) {
const n = nums.length;
const dq = [];
const dp = new Array(n).fill(-Infinity);
dp[0] = nums[0];
dq.push(0);
for (let i = 1; i < n; i++) {
// Remove indices out of window
while (dq.length && dq[0] <= i - k) {
dq.shift();
}
// Current max score
dp[i] = nums[i] + dp[dq[0]];
// Maintain monotonic decreasing queue
while (dq.length && dp[dq[dq.length - 1]] <= dp[i]) {
dq.pop();
}
dq.push(i);
}
return dp[n - 1];
}
// Example usage:
const nums = [1, -1, 4, 2, 3];
const k = 2;
console.log(maxScore(nums, k)); // Output: 7
Note: The monotonic queue ensures that we always have the maximum score in the valid window of size
k at the front, allowing efficient computation.6. Finding Constrained Subset Sum
Monotonic queues can be used to efficiently find subsets of an array that satisfy certain constraints, particularly when the constraint involves maintaining a property like sum or count within bounds.
| Property | Description | Notes |
|---|---|---|
| Constraint Type | Sum of elements in subset | Used to find a contiguous subarray with sum within a range |
| Queue Type | Monotonic Increasing Deque | Used to maintain minimum prefix sums for efficient range queries |
| Time Complexity | O(n) | Each element is pushed and popped at most once |
| Space Complexity | O(n) | Storage for the deque and auxiliary arrays |
Example: Finding Subarray with Sum in Range
function findSubarrayWithSumInRange(arr, minSum, maxSum) {
let prefixSum = 0;
let minPrefix = 0;
let maxPrefix = 0;
let result = [];
// Using a monotonic increasing deque to store prefix sums
const deque = [];
deque.push(0); // Initial prefix sum
for (let i = 0; i < arr.length; i++) {
prefixSum += arr[i];
// Remove elements from front if they violate the constraint
while (deque.length > 0 && prefixSum - deque[0] > maxSum) {
deque.shift();
}
// Check if current prefix sum satisfies the constraint
while (deque.length > 0 && prefixSum - deque[0] < minSum) {
deque.shift();
}
if (deque.length > 0 && prefixSum - deque[0] <= maxSum &&
prefixSum - deque[0] >= minSum) {
result.push([deque[0], i]);
}
// Maintain monotonic property of deque
while (deque.length > 0 && deque[deque.length - 1] > prefixSum) {
deque.pop();
}
deque.push(prefixSum);
}
return result;
}
// Example usage:
const arr = [1, 2, 3, -1, 4];
const minSum = 3;
const maxSum = 6;
console.log(findSubarrayWithSumInRange(arr, minSum, maxSum)); // [[0, 2], [1, 3]]
Note: The monotonic queue helps in efficiently maintaining prefix sums to find subarrays that meet the sum constraint.
7. Implementing Moving Average with Window
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| addValue(value) | Adds a new value to the sliding window | O(1) | O(W) |
| getAverage() | Calculates and returns the current average | O(1) | O(1) |
Example: Moving Average Implementation
class MovingAverage {
constructor(windowSize) {
this.windowSize = windowSize;
this.values = [];
this.sum = 0;
}
addValue(value) {
if (this.values.length === this.windowSize) {
this.sum -= this.values.shift();
}
this.values.push(value);
this.sum += value;
}
getAverage() {
return this.values.length === 0 ? 0 : this.sum / this.values.length;
}
}
// Usage Example
const ma = new MovingAverage(3);
ma.addValue(10);
ma.addValue(20);
ma.addValue(30);
console.log(ma.getAverage()); // 20
ma.addValue(40);
console.log(ma.getAverage()); // 30
Note: The window size determines how many recent values are considered in the average calculation. Values outside the window are discarded.
8. Finding Continuous Subarrays
Monotonic queues are useful for finding continuous subarrays that satisfy specific conditions, such as having a maximum or minimum within a given range. This is particularly effective when the condition can be maintained through a monotonic property.
| Property | Description | Usage |
|---|---|---|
| Monotonic Queue | A deque that maintains elements in increasing or decreasing order. | Used to efficiently find subarrays with specific properties. |
| Sliding Window | A technique where a window of fixed size slides over the array. | Used in conjunction with monotonic queues to find subarrays efficiently. |
Example: Finding Subarrays with Maximum Value
function maxSubarray(arr, k) {
const dq = [];
const result = [];
for (let i = 0; i < arr.length; i++) {
// Remove elements out of the window
while (dq.length > 0 && dq[0] <= i - k) {
dq.shift();
}
// Maintain monotonic property (decreasing)
while (dq.length > 0 && arr[dq[dq.length - 1]] <= arr[i]) {
dq.pop();
}
dq.push(i);
// Add result once window is full
if (i >= k - 1) {
result.push(arr[dq[0]]);
}
}
return result;
}
// Example usage
const arr = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSubarray(arr, k)); // [3, 3, 5, 5, 6, 7]
Note: The monotonic queue helps in efficiently tracking the maximum element in each sliding window of size k.
9. Finding Longest Continuous Subarray
| Property | Description | Usage |
|---|---|---|
| Monotonic Queue | Used to efficiently find the longest continuous subarray with specific properties (e.g., maximum or minimum element within a window) | Used in sliding window problems where maintaining order is crucial |
| Time Complexity | O(n) | Each element is pushed and popped at most once |
| Space Complexity | O(n) | Storage for the queue elements |
Example: Finding Longest Subarray with Maximum Element
function longestSubarrayWithMax(arr, k) {
const dq = [];
let maxLen = 0;
let left = 0;
for (let right = 0; right < arr.length; right++) {
while (dq.length && arr[dq[dq.length - 1]] <= arr[right]) {
dq.pop();
}
dq.push(right);
while (arr[dq[0]] - arr[left] > k) {
if (dq[0] === left) dq.shift();
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Example usage:
const arr = [1, 3, 2, 4, 5];
const k = 2;
console.log(longestSubarrayWithMax(arr, k)); // Output: 3
Note: The monotonic queue maintains indices of array elements in a way that ensures the maximum element in any window is at the front.
10. Optimizing DP Transitions with Queue
Monotonic queues are often used to optimize dynamic programming (DP) transitions by maintaining a decreasing or increasing order of states, allowing efficient retrieval of the optimal state at each step.
| State | Description | Optimization |
|---|---|---|
| State Representation | Each state in DP is represented by a value (e.g., cost, index, or score) | Use monotonic queue to maintain optimal states in sorted order |
| Transition | Transitions depend on previous states, often requiring a scan over valid prior states | Use queue to efficiently retrieve the best previous state in O(1) or O(log n) |
Example: Sliding Window Maximum with Monotonic Queue
function maxSlidingWindow(nums, k) {
const dq = [];
const result = [];
for (let i = 0; i < nums.length; i++) {
// Remove indices that are out of the window
while (dq.length && dq[0] <= i - k) {
dq.shift();
}
// Maintain monotonic decreasing order
while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) {
dq.pop();
}
dq.push(i);
// Add result once window is formed
if (i >= k - 1) {
result.push(nums[dq[0]]);
}
}
return result;
}
// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(maxSlidingWindow(nums, k)); // [3, 3, 5, 5, 6, 7]
Note: The monotonic queue ensures that the front of the queue always holds the index of the maximum element in the current window.