Last updated on July 21st, 2024 at 04:25 am
Here, We see Sliding Window Median LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Sliding-Window
Companies
Level of Question
Hard
Sliding Window Median LeetCode Solution
Table of Contents
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]
1. Sliding Window Median LeetCode Solution 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;
}
};
2. Sliding Window Median LeetCode Solution 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. Sliding Window Median LeetCode Solution 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
}
}
}
4. Sliding Window Median LeetCode Solution 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