Last updated on March 1st, 2025 at 09:59 pm
Here, we see a Sliding Window Median LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Level of Question
Hard
Sliding Window Median LeetCode Solution
Table of Contents
1. Problem Statement
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.
- For examples, if
arr = [2,3,4], the median is3. - For examples, if
arr = [1,2,3,4], the median is(2 + 3) / 2 = 2.5.
You are given an integer array nums and an integer k. 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. Answers within 10-5 of the actual value will be accepted.
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
Example 2:
Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Two Heaps. This pattern is commonly used to solve problems where we need to efficiently find the median of a sliding window or maintain the median of a dynamically changing dataset. The Two Heaps pattern leverages a max-heap and a min-heap to keep track of the smaller and larger halves of the dataset, respectively.
3. Code Implementation in Different Languages
3.1 Sliding Window Median C++
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> medians;
unordered_map<int, int> hashTable;
priority_queue<int> lo;
priority_queue<int, vector<int>, greater<int>> hi;
int i = 0;
while(i < k){
lo.push(nums[i++]);
}
for(int j = 0; j < k / 2; ++j){
hi.push(lo.top());
lo.pop();
}
while(true){
medians.push_back(k & 1 ? lo.top() : ((double)lo.top() + (double)hi.top()) * 0.5);
if(i >= nums.size()) break;
int outNum = nums[i - k];
int inNum = nums[i++];
int balance = 0;
balance += outNum <= lo.top() ? -1 : 1;
hashTable[outNum]++;
if(!lo.empty() && inNum <= lo.top()){
balance++;
lo.push(inNum);
}
else{
balance--;
hi.push(inNum);
}
if(balance < 0){
lo.push(hi.top());
hi.pop();
balance++;
}
if(balance > 0){
hi.push(lo.top());
lo.pop();
balance--;
}
while(hashTable[lo.top()]){
hashTable[lo.top()]--;
lo.pop();
}
while(!hi.empty() && hashTable[hi.top()]){
hashTable[hi.top()]--;
hi.pop();
}
}
return medians;
}
};
3.2 Sliding Window Median Java
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0)
return new double[0];
Node root = null;
for (int i = 0; i < k; i++) {
root = insert(root, nums[i]);
}
double[] r = new double[nums.length - k + 1];
boolean even = k % 2 == 0;
int j = 0;
for (int i = k; i <= nums.length; i++) {
double sum = 0.0;
if (even)
sum = (findSmallest(root, k/2).val + findSmallest(root, k/2 + 1).val) / 2.0;
else
sum = findSmallest(root, k/2 + 1).val;
r[j++] = sum;
if (i < nums.length) {
root = insert(root, nums[i]);
root = delete(root, nums[i - k]);
}
}
return r;
}
private Node findSmallest(Node root, int k) {
int s = countWith(root.left) + 1;
if (s == k)
return root;
if (s > k) {
return findSmallest(root.left, k);
}
return findSmallest(root.right, k - s);
}
private Node delete(Node root, long val) {
if (root == null)
return null;
else if (val > root.val)
root.right = delete(root.right, val);
else if (val < root.val)
root.left = delete(root.left, val);
else {
if (root.left == null)
root = root.right;
else if (root.right == null)
root = root.left;
else {
Node t = findMin(root.right);
root.val = t.val;
root.right = delete(root.right, t.val);
}
}
return updateNode(root);
}
private Node findMin(Node root) {
if (root.left != null)
return findMin(root.left);
return root;
}
private Node insert(Node root, long val)
{
if (root == null)
{
return new Node(val);
}
if (val >= root.val)
{
root.right = insert(root.right, val);
}
else
{
root.left = insert(root.left, val);
}
return updateNode(root);
}
private Node updateNode(Node root) {
int b = balance(root);
if (b == 2 && balance(root.left) < 0)
{
root.left = leftRotate(root.left);
root = rightRotate(root);
}
else if (b == -2 && balance(root.right) > 0)
{
root.right = rightRotate(root.right);
root = leftRotate(root);
}
else if (b == 2)
{
root = rightRotate(root);
}
else if (b == -2)
{
root = leftRotate(root);
}
update(root);
return root;
}
private Node leftRotate(Node n)
{
Node r = n.right;
n.right = r.left;
r.left = n;
update(n);
update(r);
return r;
}
private Node rightRotate(Node n)
{
Node l = n.left;
n.left = l.right;
l.right = n;
update(n);
update(l);
return l;
}
private int balance(Node n)
{
if (n==null)return 0;
return height(n.left) - height(n.right);
}
private void update(Node n)
{
if (n==null)return;
n.height = Math.max(height(n.left), height(n.right)) + 1;
n.count = n.left != null ? n.left.count + 1 : 0;
n.count += n.right != null ? n.right.count + 1 : 0;
}
private int height(Node n)
{
return n != null ? n.height : 0;
}
private int countWith(Node n)
{
return n != null ? n.count + 1 : 0;
}
static class Node
{
Node left;
Node right;
long val;
int count;
int height;
Node(long val)
{
this.val = val;
}
}
}
3.3 Sliding Window Median JavaScript
var medianSlidingWindow= function (nums, k){
let arr = []
let output = []
let isEven = k % 2 === 0
let m = k >> 1
for (let i = 0; i < nums.length; i++) {
binaryInsertion(arr, nums[i])
if (arr.length > k) {
binaryDeletion(arr, nums[i - k])
}
if (arr.length === k) {
output.push(isEven ? (arr[m - 1] + arr[m]) / 2 : arr[m])
}
}
return output
}
function binaryInsertion(arr, target) {
let left = 0
let right = arr.length
while (left < right) {
const mid = (left + right) >> 1
if (target > arr[mid]) {
left = mid + 1
} else {
right = mid
}
}
arr.splice(left, 0, target)
}
function binaryDeletion(arr, target) {
let left = 0
let right = arr.length
while (left < right) {
const mid = (left + right) >> 1
if (target === arr[mid]) {
arr.splice(mid, 1)
break
} else if (target > arr[mid]) {
left = mid + 1
} else {
right = mid
}
}
}
3.4 Sliding Window Median Python
class Solution(object):
def medianSlidingWindow(self, nums, k):
arr = []
i = j = 0
ans = []
while j < len(nums):
arr.append(nums[j])
if j < k-1:
j += 1
elif j-i+1 == k:
array = sorted(arr)
value = 0
if k % 2 == 0:
m = k // 2
value = (array[m-1] + array[m]) / 2
else:
value = array[k//2]
ans.append(value)
if nums[i] in arr:
arr.pop(0)
i += 1
j += 1
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * log(k)) | O(k) |
| Java | O(n * log(k)) | O(k) |
| JavaScript | O(n * k) | O(k) |
| Python | O(n * k * log(k)) | O(k) |
where, k is the size of sliding window and n is the number of elements.