Sliding Window Median - Leetcode Solution

Problem: Sliding Window Median (https://leetcode.com/problems/sliding-window-median/)

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the median array for each window in the original array.

Note: The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

Example 1: Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

Explanation: Window position Median

---

[1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6

Solution:

Approach: We can use a min-max heap approach for solving this problem. We will maintain two heaps: one min-heap and one max-heap. In the min-heap, we will keep the larger half of the window and in the max-heap, we will keep the smaller half of the window. This way, we can get the median in O(1) time by looking at the top elements of both the heaps.

Algorithm:

1. Initialize two heaps. One min-heap and one max-heap.
2. For each element in the window, do the following: a. If the min-heap is empty or if the current element is greater than the top element of the min-heap, then add the element to the min-heap. Otherwise, add the element to the max-heap. b. Balance the heaps such that the difference in size between the two heaps is not greater than one. If the size of the heaps differs by more than one, then we will remove the top element from the larger heap and add it to the smaller heap. c. If the size of the window is greater than or equal to k, then we can get the median of the current window and add it to the result array. To get the median, we need to look at the top elements of both the heaps and calculate the median accordingly.
3. Return the result array.

Complexity Analysis: Time Complexity: O(n*log(k)) where n is the size of the array and k is the size of the window. We are iterating through the array once and at each element, we are doing log(k) operations to balance the heaps and get the median. Space Complexity: O(k) as we are keeping k elements in the heaps.

Code:

class Solution { public: vector<double> medianSlidingWindow(vector<int>& nums, int k) { vector<double> result; priority_queue<int> maxHeap; priority_queue<int, vector<int>, greater<int>> minHeap; unordered_map<int, int> removeMap; int currentIndex = 0; for (int i = 0; i < nums.size(); i++) { // Step 1: Add the current element to the heaps if (minHeap.empty() || nums[i] >= minHeap.top()) { minHeap.push(nums[i]); } else { maxHeap.push(nums[i]); } // Step 2: Balance the heaps if (minHeap.size() > maxHeap.size() + 1) { maxHeap.push(minHeap.top()); minHeap.pop(); } else if (maxHeap.size() > minHeap.size()) { minHeap.push(maxHeap.top()); maxHeap.pop(); } // Step 3: Calculate median and add it to the result array if (i >= k - 1) { double median; if (minHeap.size() == maxHeap.size()) { median = ((double)minHeap.top() + (double)maxHeap.top()) / 2; } else { median = (double)minHeap.top(); } result.push_back(median); // Remove the current element from the heaps int removeIndex = removeMap[currentIndex - k + 1]; if (nums[removeIndex] >= minHeap.top()) { minHeap.erase(minHeap.find(nums[removeIndex])); } else { maxHeap.erase(maxHeap.find(nums[removeIndex])); } // Balance the heaps if (minHeap.size() > maxHeap.size() + 1) { maxHeap.push(minHeap.top()); minHeap.pop(); } else if (maxHeap.size() > minHeap.size()) { minHeap.push(maxHeap.top()); maxHeap.pop(); } currentIndex++; } // Add the current element's index to the removeMap removeMap[i] = i; } return result; } };

Note: This is just one of the possible solutions for this problem. There can be other approaches as well.

1