Sliding Window Maximum
Find the maximum element in every sliding window of size k as it moves from left to right through an array. The naive O(nk) solution checks each window independently. The optimal solution uses a monotonic decreasing deque to maintain potential maximums, achieving O(n) time. This technique is fundamental for many sliding window problems and demonstrates advanced data structure usage.
Visualization
Interactive visualization for Sliding Window Maximum
Sliding Window Maximum
Array:
• Time: O(n) using deque
• Efficient sliding window technique
• Maintains max in each window
Interactive visualization with step-by-step execution
Implementation
1function maxSlidingWindow(nums: number[], k: number): number[] {
2 const result: number[] = [];
3 const deque: number[] = [];
4
5 for (let i = 0; i < nums.length; i++) {
6 while (deque.length && deque[0] < i - k + 1) {
7 deque.shift();
8 }
9
10 while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
11 deque.pop();
12 }
13
14 deque.push(i);
15
16 if (i >= k - 1) {
17 result.push(nums[deque[0]]);
18 }
19 }
20
21 return result;
22}Deep Dive
Theoretical Foundation
Sliding Window Maximum uses a deque (double-ended queue) to maintain indices of elements in decreasing order of their values. The key insight: smaller elements that come after larger elements can never be the maximum while the larger element is in the window. The deque stores potential candidates for window maximum. Front of deque always contains the current window's maximum. For each element: (1) remove indices outside window from front, (2) remove smaller elements from back (they're now useless), (3) add current index to back, (4) front is window max. Each element enters and leaves deque at most once, giving O(n) time.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(k)
Applications
Industry Use
Stock price analysis (maximum in time windows)
Network traffic monitoring (peak bandwidth)
Image processing (local maximum filter)
Real-time data stream analysis
Game leaderboards (rolling rankings)
Sensor data analysis (peak detection)
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.