Sliding Window Maximum

Finds the maximum in each k-sized sliding window of an array

Problem Overview

📊 The Real-Time Analytics Champion
Sliding Window Maximum efficiently finds the maximum value in every k-sized window as it slides through an array. This technique is essential for real-time data processing, streaming analytics, and time-series analysis!

🧠 The Window Strategy:

Window Movement: Fixed-size window slides one position at a time
Maximum Tracking: Find peak value in current window efficiently
Continuous Processing: Handle streaming data without recomputation
Optimal Complexity: Achieve O(n) time using clever data structures
Two Strategic Approaches:
Monotonic Deque: Advanced O(n) solution using double-ended queue
Brute Force: Simple O(n*k) approach examining each window directly
Real-World Applications:
Stock Trading: Track maximum prices in sliding time windows
System Monitoring: Find peak CPU/memory usage in time intervals
Signal Processing: Detect maximum amplitude in audio/video streams
Gaming Analytics: Track highest scores in rolling time periods
IoT Sensors: Monitor maximum temperature/pressure readings

💡 Learning Value:

Advanced sliding window technique for optimization
Monotonic deque data structure and its applications
Amortized time complexity analysis
Stream processing algorithm design patterns

Concepts

sliding windowdequebrute-force

Complexity Analysis

Time:O(n) for deque, O(n*k) for brute force

Space:O(n)

Performance Notes:

- Time: O(n) with deque approach, O(nk) brute force - Space: O(k) for deque storage, O(1) for brute force

Solutions

slidingWindowMax

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

export function slidingWindowMax(nums: number[], k: number): number[] {
  if (!Array.isArray(nums) || !nums.every(Number.isFinite)) throw new Error("Input must be an array of finite numbers");
  if (!Number.isInteger(k) || k <= 0) throw new Error("Window size must be a positive integer");
  if (nums.length === 0) return [];
  if (k > nums.length) k = nums.length;

  const result: number[] = [];
  const deque: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    if (deque.length && deque[0] < i - k + 1) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }

  return result;
}

// Alternative implementation (brute force)

Examples & Test Cases

#1Standard sliding window

Input:

Output:

[
  3,
  3,
  5,
  5,
  6,
  7
]

#2Single element window

Input:

[
  [
    1
  ],
  1
]

Output:

[
  1
]

#3Window size 1

Input:

[
  [
    1,
    -1
  ],
  1
]

Output:

[
  1,
  -1
]

#4Empty array

Input:

[
  [],
  3
]

Output:[]

#5Decreasing array

Input:

Output:

[
  9,
  8,
  7
]

#6k > length (adjusted to max)

Input:

Output:

[
  4
]