Home/

...

/

Sliding Window Median (hard)

Sliding Window Median (hard)

Problem Statement

Given an array of numbers and a number ‘k’, find the median of all the ‘k’ sized sub-arrays (or windows) of the array.

Example 1:

Input: nums=[1, 2, -1, 3, 5], k = 2
Output: [1.5, 0.5, 1.0, 4.0]
Explanation: Lets consider all windows of size ‘2’:

  • [ 1, 2, -1, 3, 5] -> median is 1.5
  • [1, 2, -1, 3, 5] -> median is 0.5
  • [1, 2, -1, 3, 5] -> median is 1.0
  • [1, 2, -1, 3, 5] -> median is 4.0

Example 2:

Input: nums=[1, 2, -1, 3, 5], k = 3
Output: [1.0, 2.0, 3.0]
Explanation: Lets consider all windows of size ‘3’:

  • [1, 2, -1, 3, 5] -> median is 1.0
  • [1, 2, -1, 3, 5] -> median is 2.0
  • [1, 2, -1, 3, 5] -> median is 3.0

Try it yourself

Try solving this question here:

import java.util.*;
class SlidingWindowMedian {
  public double[] findSlidingWindowMedian(int[] nums, int k) {
    double[] result = new double[nums.length - k + 1];
    // TODO: Write your code here
    return result;
  }
  public static void main(String[] args) {
    SlidingWindowMedian slidingWindowMedian = new SlidingWindowMedian();
    double[] result = slidingWindowMedian.findSlidingWindowMedian(new int[] { 1, 2, -1, 3, 5 }, 2);
    System.out.print("Sliding window medians are: ");
    for (double num : result)
      System.out.print(num + " ");
    System.out.println();
    slidingWindowMedian = new SlidingWindowMedian();
    result = slidingWindowMedian.findSlidingWindowMedian(new int[] { 1, 2, -1, 3, 5 }, 3);
    System.out.print("Sliding window medians are: ");
    for (double num : result)
      System.out.print(num + " ");
  }
}

Solution #

This problem ...