CC-19 : Find first negative number in stream of integers with sliding window of N numbers.

Description:

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

Test cases and expected outputs:

Input Parameters	Expected outputs
QueueFindFirstNegInWin queue = new QueueFindFirstNegInWin(); int[] arr= { -1,20,30,-2,-3,25,-4,15,15, 5, -5, 10}; System.out.println("Window Size: "+3); retVal=queue.queueFindFirstNegInWin(arr, 3);	1stNegInWin: -1,-2,-2,-2,-3,-4,-4,0,-5,-5

Pseudocode:

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

Declare and initialize an array negArr of size (input array size – n +1) to store the found negative numbers.

Initialize variable negArrIdx=0 to hold index of negArr.

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 0, remove last node from Deque.

If current element of input array is less than 0, add it to end of Deque.

If Deque size is greater than 0 and we have iterated more than N integers of input array, then store first node of Deque to negArr at index negArrIdx and increment negArrIdx by 1.

If Deque size is 0 and we have iterated more than N integers of input array, then store 0 to negArr at index negArrIdx (this means there is no negative integer sliding window of n integers) in current and increment negArrIdx by 1.

Code:

public int[] queueFindFirstNegInWin(int[]arr, int n) {
	int[] negArr=new int[arr.length-n+1];
	Deque<Integer> idxQ=new LinkedList<Integer>();
	int negArrIdx=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()] >= 0)) {
			idxQ.removeLast();
		}
		if (arr[idx] <0) {
			idxQ.addLast(idx);
		}
		
		if (idxQ.size() !=0) {
			if (idx >= n-1) {
				negArr[negArrIdx]=arr[idxQ.getFirst()];
				negArrIdx++;
			}
		}else {
			if (idx >= n-1) {
			negArr[negArrIdx]=0;
			negArrIdx++;
			}
		}
	}
	return negArr;
}

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.Deque;


public class QueueFindFirstNegInWin {
	
public int[] queueFindFirstNegInWin(int[]arr, int n) {
	int[] negArr=new int[arr.length-n+1];
	Deque<Integer> idxQ=new LinkedList<Integer>();
	int negArrIdx=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()] >= 0)) {
			idxQ.removeLast();
		}
		if (arr[idx] <0) {
			idxQ.addLast(idx);
		}
		
		if (idxQ.size() !=0) {
			if (idx >= n-1) {
				negArr[negArrIdx]=arr[idxQ.getFirst()];
				negArrIdx++;
			}
		}else {
			if (idx >= n-1) {
			negArr[negArrIdx]=0;
			negArrIdx++;
			}
		}
	}
	return negArr;
}

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 {
	QueueFindFirstNegInWin queue=new QueueFindFirstNegInWin();
	int[] arr= { -1,20,30,-2,-3,25,-4,15,15, 5, -5, 10};
	System.out.println("Window Size: "+3);
	printArraySummary(arr, "Original Array:");
	retVal=queue.queueFindFirstNegInWin(arr, 3);
	
	printArraySummary(retVal, "1stNegInWin:");
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}