480. Sliding Window Median LeetCode Solution

In this guide, you will get 480. Sliding Window Median LeetCode Solution with the best time and space complexity. The solution to Sliding Window Median problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sliding Window Median solution in C++
Sliding Window Median solution in Java
Sliding Window Median solution in Python
Additional Resources

480. Sliding Window Median LeetCode Solution image

Problem Statement of Sliding Window Median

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]

Constraints:

1 <= k <= nums.length <= 105
-231 <= nums[i] <= 231 – 1

Complexity Analysis

Time Complexity: O((n – k + 1)\log k)
Space Complexity: O(k)

480. Sliding Window Median LeetCode Solution in C++

class Solution {
 public:
  vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    vector<double> ans;
    multiset<double> window(nums.begin(), nums.begin() + k);
    auto it = next(window.begin(), (k - 1) / 2);

    for (int i = k;; ++i) {
      const double median = k % 2 == 0 ? (*it + *next(it)) / 2.0 : *it;
      ans.push_back(median);
      if (i == nums.size())
        break;
      window.insert(nums[i]);
      if (nums[i] < *it)
        --it;
      if (nums[i - k] <= *it)
        ++it;
      window.erase(window.lower_bound(nums[i - k]));
    }

    return ans;
  }
};
/* code provided by PROGIEZ */