101 Logo
onenoughtone

Code Implementation

Dynamic Window Statistics Implementation

Below is the implementation of the dynamic window statistics:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
/**
 * Brute Force Approach
 * Time Complexity: O(n * k log k) - For each window, we sort k elements
 * Space Complexity: O(k) - We need space to store the current window
 *
 * @param {number[]} nums - The input array
 * @param {number} k - The size of the sliding window
 * @return {number[]} - The median of each sliding window
 */
function medianSlidingWindowBruteForce(nums, k) {
  const result = [];
 
  for (let i = 0; i <= nums.length - k; i++) {
    // Extract the current window
    const window = nums.slice(i, i + k).sort((a, b) => a - b);
 
    // Calculate the median
    let median;
    if (k % 2 === 1) {
      // Odd window size
      median = window[Math.floor(k / 2)];
    } else {
      // Even window size
      median = (window[k / 2 - 1] + window[k / 2]) / 2;
    }
 
    result.push(median);
  }
 
  return result;
}
 
/**
 * Two Heaps Approach
 * Time Complexity: O(n log k) - For each element, we perform heap operations
 * Space Complexity: O(k) - We need space to store the elements in the heaps
 *
 * @param {number[]} nums - The input array
 * @param {number} k - The size of the sliding window
 * @return {number[]} - The median of each sliding window
 */
function medianSlidingWindow(nums, k) {
  const result = [];
 
  // Create max heap for smaller half and min heap for larger half
  const maxHeap = new MaxHeap();
  const minHeap = new MinHeap();
 
  // Hash map to track delayed elements (elements to be removed)
  const delayed = new Map();
 
  // Process the first k-1 elements
  for (let i = 0; i < k - 1; i++) {
    addNum(nums[i]);
  }
 
  // Process the rest of the elements
  for (let i = k - 1; i < nums.length; i++) {
    // Add the current element
    addNum(nums[i]);
 
    // Calculate the median and add it to the result
    result.push(findMedian());
 
    // Remove the element that's no longer in the window
    removeNum(nums[i - k + 1]);
  }
 
  return result;
 
  // Helper function to add a number to the heaps
  function addNum(num) {
    // Add to the appropriate heap
    if (maxHeap.size() === 0 || num <= maxHeap.peek()) {
      maxHeap.offer(num);
    } else {
      minHeap.offer(num);
    }
 
    // Rebalance the heaps
    rebalance();
  }
 
  // Helper function to find the median
  function findMedian() {
    if (k % 2 === 1) {
      // Odd window size
      return maxHeap.peek();
    } else {
      // Even window size
      return (maxHeap.peek() + minHeap.peek()) / 2;
    }
  }
 
  // Helper function to remove a number from the heaps
  function removeNum(num) {
    // Mark the number as delayed
    delayed.set(num, (delayed.get(num) || 0) + 1);
 
    // Update the heap sizes
    if (num <= maxHeap.peek()) {
      // The number is in the max heap
      if (num === maxHeap.peek()) {
        // Remove delayed elements from the top of the heap
        prune(maxHeap);
      }
    } else {
      // The number is in the min heap
      if (num === minHeap.peek()) {
        // Remove delayed elements from the top of the heap
        prune(minHeap);
      }
    }
 
    // Rebalance the heaps
    rebalance();
  }
 
  // Helper function to remove delayed elements from the top of a heap
  function prune(heap) {
    while (heap.size() > 0 && delayed.has(heap.peek())) {
      const num = heap.peek();
      const count = delayed.get(num);
 
      if (count === 1) {
        delayed.delete(num);
      } else {
        delayed.set(num, count - 1);
      }
 
      heap.poll();
    }
  }
 
  // Helper function to rebalance the heaps
  function rebalance() {
    // Ensure the max heap has either the same number of elements as the min heap
    // or one more element (for odd window size)
    if (maxHeap.size() > minHeap.size() + 1) {
      minHeap.offer(maxHeap.poll());
      prune(maxHeap);
    } else if (maxHeap.size() < minHeap.size()) {
      maxHeap.offer(minHeap.poll());
      prune(minHeap);
    }
  }
}
 
// Max Heap implementation
class MaxHeap {
  constructor() {
    this.heap = [];
  }
 
  size() {
    return this.heap.length;
  }
 
  peek() {
    return this.heap[0];
  }
 
  offer(val) {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  poll() {
    if (this.heap.length === 0) return null;
 
    const max = this.heap[0];
    const last = this.heap.pop();
 
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
 
    return max;
  }
 
  siftUp(index) {
    let parent = Math.floor((index - 1) / 2);
 
    while (index > 0 && this.heap[parent] < this.heap[index]) {
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }
 
  siftDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let largest = index;
 
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
      largest = left;
    }
 
    if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
      largest = right;
    }
 
    if (largest !== index) {
      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      this.siftDown(largest);
    }
  }
}
 
// Min Heap implementation
class MinHeap {
  constructor() {
    this.heap = [];
  }
 
  size() {
    return this.heap.length;
  }
 
  peek() {
    return this.heap[0];
  }
 
  offer(val) {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  poll() {
    if (this.heap.length === 0) return null;
 
    const min = this.heap[0];
    const last = this.heap.pop();
 
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
 
    return min;
  }
 
  siftUp(index) {
    let parent = Math.floor((index - 1) / 2);
 
    while (index > 0 && this.heap[parent] > this.heap[index]) {
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }
 
  siftDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;
 
    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }
 
    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }
 
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.siftDown(smallest);
    }
  }
}

Step-by-Step Explanation

Let's break down the implementation:

  1. 1. Understand the Problem: First, understand that we need to find the median of each sliding window of size k in an array.
  2. 2. Implement the Brute Force Approach: For each window position, extract the k elements, sort them, and calculate the median.
  3. 3. Implement the Two Heaps Approach: Use two heaps to maintain the smaller half and larger half of elements in the window, with a mechanism to handle element removal.
  4. 4. Implement the Ordered Set Approach: Use a self-balancing binary search tree to maintain the sorted order of elements in the window.
  5. 5. Handle Edge Cases: Consider edge cases such as k = 1, or when the array contains duplicate elements.
  6. 6. Optimize for Performance: Choose the most efficient approach based on the constraints of the problem.
  7. 7. Test the Solution: Verify the solution with the provided examples and additional test cases.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone