CC-20 : Find the maximum number in stream of integers with sliding window of N numbers.

Description:

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

Test cases and expected outputs:

Input Parameters	Expected outputs
QueueFindMaxInWin queue = new QueueFindMaxInWin(); int[] arr= { -1,20,30,40,35,25,15,15,15, 5, -5, 10}; System.out.println("Window Size: "+3); retVal=queue.queueFindMaxInWin(arr, 3);	Maximum in sliding window of 3 nums: 30,40,40,40,35,25,15,15,15,10

Pseudocode:

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

Declare and initialize an array maxArr of size (input array size – n +1) to store the found maximum numbers within sliding windows.

Initialize variable maxArrIdx=0 to hold index of maxArr.

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

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

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

While Deque size is greater than 0 and data of last node of Deque is greater than current element of input array, remove last node from Deque.

Add current element of input array to end of Deque.

If we have iterated more than N integers of input array, then store first node of Deque to maxArr at index maxArrIdx and increment maxArrIdx by 1.

Code:

public int[] queueFindMaxInWin(int[]arr, int n) {
	int[] maxArr=new int[arr.length-n+1];
	Deque<Integer> idxQ=new LinkedList<Integer>();
	int maxArrIdx=0;
	for (int idx=0; idx < arr.length; idx++) {
		if ((idxQ.size() !=0)&& (idxQ.getFirst() == idx-n)){
			idxQ.removeFirst();
		}
		while ((idxQ.size() !=0)&&(arr[idxQ.getLast()]< arr[idx])) {
			idxQ.removeLast();
		}
		idxQ.addLast(idx);
		if (idx >= n-1) {
			maxArr[maxArrIdx]=arr[idxQ.getFirst()];
			maxArrIdx++;
		}
	}
	return maxArr;
}

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.*;
import java.util.LinkedList;

public class QueueFindMaxInWin {
	
public int[] queueFindMaxInWin(int[]arr, int n) {
	int[] maxArr=new int[arr.length-n+1];
	Deque<Integer> idxQ=new LinkedList<Integer>();
	int maxArrIdx=0;
	for (int idx=0; idx < arr.length; idx++) {
		if ((idxQ.size() !=0)&& (idxQ.getFirst() == idx-n)){
			idxQ.removeFirst();
		}
		while ((idxQ.size() !=0)&&(arr[idxQ.getLast()]< arr[idx])) {
			idxQ.removeLast();
		}
		idxQ.addLast(idx);
		if (idx >= n-1) {
			maxArr[maxArrIdx]=arr[idxQ.getFirst()];
			maxArrIdx++;
		}
	}
	return maxArr;
}

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 {
	QueueFindMaxInWin queue=new QueueFindMaxInWin();
	int[] arr= { -1,20,30,40,35,25,15,15,15, 5, -5, 10};
	printArraySummary(arr, "Original Array:");
	retVal=queue.queueFindMaxInWin(arr, 3);
	
	printArraySummary(retVal, "Maximum in sliding window of 3 nums:");
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}
	
}
	
}