CC-18 : Find median in stream of integers with sliding window of N numbers.

Description:

Given a stream of integers, process the same and find median within a sliding window of N integers.

Test cases and expected outputs:

Input Parameters	Expected outputs
QueueFindMedianInWin queue= new QueueFindMedianInWin(); int[] arr= { 1,20,30,40,70,90,110,115,125, 135, 145, 160}; System.out.println("Window Size: "+3); retVal=queue.queueFindMedianInWin(arr, 3);	Median in sliding window of 3 nums: 20,30,40,70,90,110,115,125,135,145

Pseudocode:

We need to process an array of integers and find median in sliding window of size N.

Declare and initialize an array mdnArr of size (input array size – n +1) to store the calculated medians.

Initialize variable mdnArrIdx=0 to hold index of mdnArr.

Declare and initialize a Deque to hold sliding window of integers from input array.

Iterate through stream of input integer array using a for loop:

Add current element of input array to Deque.

If Deque size is greater than N, remove first element of Deque.

If Deque size is equal to N calculate the medians using the integers in the sliding window that are part of Deque:

If N is even, median is sum of data of (N/2)th and ((N/2)+1)th node of Deque divided by 2.

If N is odd, median is the data of (N/2+1)th node of Deque.

Store median in mdnArr, increment mdnArrIdx by 1.

Code:

public int[] queueFindMedianInWin(int[]arr, int n) {
	int[] mdnArr=new int[arr.length-n+1];
	Deque<Integer> numQ=new LinkedList<Integer>();
	int mdnArrIdx=0; 
	int nMdn=0;
	for (int idx=0; idx < arr.length; idx++) {
		numQ.addLast(arr[idx]);
		if  (numQ.size() > n) {
			numQ.removeFirst();
		}
		if  (numQ.size() == n) {
			Iterator<Integer> itr=numQ.iterator();
			int cnt=1; int num=0, n1=0, n2=0;
			if (n%2==0) {
				while (itr.hasNext()) {
					num=itr.next();
					if (cnt== n/2) {
						n1=num;
					}
					if (cnt== (n/2)+1) {
						n2=num;
						break;
					}	
					cnt++;
				}
				nMdn=(n1+n2)/2;				
			}else {
				cnt=1;
				while (itr.hasNext()) {
					num=itr.next();
					if (cnt== (n+1)/2) {
						nMdn=num;
					}					
					cnt++;
				}
				
			}
			mdnArr[mdnArrIdx]=nMdn;
			mdnArrIdx++;
		}			
		
	}
	return mdnArr;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.*;

public class QueueFindMedianInWin {
	
public int[] queueFindMedianInWin(int[]arr, int n) {
	int[] mdnArr=new int[arr.length-n+1];
	Deque<Integer> numQ=new LinkedList<Integer>();
	int mdnArrIdx=0; 
	int nMdn=0;
	for (int idx=0; idx < arr.length; idx++) {
		numQ.addLast(arr[idx]);
		if  (numQ.size() > n) {
			numQ.removeFirst();
		}
		if  (numQ.size() == n) {
			Iterator<Integer> itr=numQ.iterator();
			int cnt=1; int num=0, n1=0, n2=0;
			if (n%2==0) {
				while (itr.hasNext()) {
					num=itr.next();
					if (cnt== n/2) {
						n1=num;
					}
					if (cnt== (n/2)+1) {
						n2=num;
						break;
					}	
					cnt++;
				}
				nMdn=(n1+n2)/2;				
			}else {
				cnt=1;
				while (itr.hasNext()) {
					num=itr.next();
					if (cnt== (n+1)/2) {
						nMdn=num;
					}					
					cnt++;
				}
				
			}
			mdnArr[mdnArrIdx]=nMdn;
			mdnArrIdx++;
		}			
		
	}
	return mdnArr;
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex < intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println(" ************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}
  	
public static void main(String[] args) {
	int[] retVal;
	try {
	QueueFindMedianInWin queue=new QueueFindMedianInWin();
	int[] arr= { 1,20,30,40,70,90,110,115,125, 135, 145, 160};
	printArraySummary(arr, "Original Array:");
	retVal=queue.queueFindMedianInWin(arr, 3);
	printArraySummary(retVal, "Median in sliding window of 3 nums:");
	
	int[] arr1= { 1,20,30,40,70,90,110,115,125, 135, 145, 160};
	printArraySummary(arr, "Original Array:");
	retVal=queue.queueFindMedianInWin(arr1, 4);
	printArraySummary(retVal, "Median in sliding window of 4 nums:");
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}