101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Brute Force Approach - Complex approach
  2. Two Heaps Approach - Complex approach
  3. Ordered Set Approach - Complex approach

Approach 1: Brute Force Approach

Let's start by understanding the problem: we need to find the median of each sliding window of size k in an array.

Thinking Process: The most straightforward approach is to maintain a separate array for each window, sort it, and then find the median. As the window slides, we remove the leftmost element and add the new rightmost element, then sort the window again to find the new median.

Intuition: This approach directly follows the problem statement. For each window, we extract the k elements, sort them, and calculate the median. While simple to understand, this approach is inefficient because we're sorting each window from scratch, which takes O(k log k) time for each window.

Algorithm:

  1. Initialize an empty result array.
  2. For each position of the sliding window:
  3. a. Extract the k elements in the current window.
  4. b. Sort these k elements.
  5. c. Calculate the median of the sorted window.
  6. d. Add the median to the result array.
  7. Return the result array.

Time Complexity:

O(n * k log k)

Where n is the length of the input array and k is the size of the window. For each of the n-k+1 windows, we sort k elements, which takes O(k log k) time.

Space Complexity:

O(k)

We need O(k) space to store the elements in the current window.

Approach 2: Two Heaps Approach

We can optimize the brute force approach by using two heaps to maintain the sorted order of elements in the window.

Thinking Process: Instead of sorting the entire window each time, we can use two heaps to maintain the smaller half and the larger half of the elements in the window. The smaller half is stored in a max heap, and the larger half is stored in a min heap. This way, the median can be quickly calculated from the tops of the heaps.

However, there's a challenge: as the window slides, we need to remove elements from the heaps, which is not a standard operation for heaps. To handle this, we can use a hash map to keep track of elements that have been removed from the window but are still in the heaps. We call these "delayed" elements. When we encounter a delayed element at the top of a heap, we remove it and continue.

Intuition: By using two heaps, we can efficiently maintain the sorted order of elements in the window and quickly calculate the median. The key insight is to handle the removal of elements from the window by marking them as "delayed" and removing them only when they reach the top of a heap.

Algorithm:

  1. Initialize a max heap for the smaller half of elements and a min heap for the larger half.
  2. Initialize a hash map to track delayed elements (elements that have been removed from the window but are still in the heaps).
  3. Process the first k elements and add them to the heaps, maintaining the balance between the two heaps.
  4. Calculate the median from the tops of the heaps and add it to the result array.
  5. For each subsequent position of the sliding window:
  6. a. Add the new element to the appropriate heap.
  7. b. Mark the element leaving the window as delayed in the hash map.
  8. c. Rebalance the heaps if necessary, removing delayed elements when they reach the top.
  9. d. Calculate the median from the tops of the heaps and add it to the result array.
  10. Return the result array.

Time Complexity:

O(n log k)

Where n is the length of the input array and k is the size of the window. For each of the n elements, we perform heap operations that take O(log k) time.

Space Complexity:

O(k)

We need O(k) space to store the elements in the heaps and the delayed elements in the hash map.

Approach 3: Ordered Set Approach

Another approach is to use a self-balancing binary search tree (like a multiset in C++) to maintain the sorted order of elements in the window.

Thinking Process: A self-balancing binary search tree can maintain the sorted order of elements and allow for efficient insertion and deletion. We can use an ordered set (like a multiset in C++) to store the elements in the current window. As the window slides, we add the new element and remove the element that's no longer in the window.

To find the median, we can use an iterator to access the middle element(s) of the ordered set. If the window size is odd, the median is the middle element. If the window size is even, the median is the average of the two middle elements.

Intuition: An ordered set provides efficient operations for maintaining a sorted collection of elements, which is exactly what we need for this problem. The key insight is that we can directly access the middle element(s) of the ordered set to find the median.

Algorithm:

  1. Initialize an empty ordered set.
  2. Process the first k elements and add them to the ordered set.
  3. Calculate the median by finding the middle element(s) of the ordered set and add it to the result array.
  4. For each subsequent position of the sliding window:
  5. a. Remove the element leaving the window from the ordered set.
  6. b. Add the new element to the ordered set.
  7. c. Calculate the median by finding the middle element(s) of the ordered set and add it to the result array.
  8. Return the result array.

Time Complexity:

O(n log k)

Where n is the length of the input array and k is the size of the window. For each of the n elements, we perform ordered set operations that take O(log k) time.

Space Complexity:

O(k)

We need O(k) space to store the elements in the ordered set.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
function medianSlidingWindow(nums, k):
    result = []
    for i from 0 to nums.length - k:
        window = nums[i:i+k]
        sort(window)
        if k is odd:
            median = window[k/2]
        else:
            median = (window[k/2 - 1] + window[k/2]) / 2
        result.append(median)
    return result
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone