Sliding Window Median LeetCode Solution

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

Sliding Window Median LeetCode Solution

Sliding Window Median LeetCode Solution

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 is 3.
  • 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]

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;
    }
};Code language: PHP (php)

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;
        }
    }
}Code language: PHP (php)

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
        }
    }
}Code language: JavaScript (javascript)

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
Scroll to Top