Maximum Value in JavaScript Sliding Window Queue

Use Case:

In this sliding window scenario, we are given an array of numbers and a window size. The window size determines how many numbers we're looking at at one time. When the window slides forward by 1, we're now looking at another set of numbers (the first number is being removed and a new number is being added to the end based on the values in our array).

Here's an illustration:

2

7

3

1

5

2

6

2

We have been tasked with returning the maximum value found in the window at each slide of the pane in O(n) - or linear time. To do so, we're going to start with the constant-time JavaScript stack that we previously created.

But we need to make a few updates. We need to give our stack the functionality of a queue so that we can dequeue values from the front of the stack when the window pane slides forward. We don't want to lose the constant-time efficiency of the stack however, so we'll need to add a 'start' variable to keep track of the index of our stack's starting variable. This will also alter the index that we use for pushing new values onto our stack so we'll need to change that as well.

Here are the updated declarations and push functions.

JavaScript

var Stack = function() {
	this.count = 0
	this.start = 0
	this.storage = {}
	this.auxiliary = {}
}

// Adds a value onto the end of the stack
Stack.prototype.push = function(value) {
	this.storage[this.start + this.count] = value

	// Push to and update auxiliary stack
	if (this.auxiliary[this.count - 1] >= value) {
		for (i = this.count - 1; i >= 0; i--) {
			// If bigger than current value
			if (value > this.auxiliary[i]) {
				this.auxiliary[i + 1] = value
				break
			} else if (i == 0) {
				// If 0 or at first value in stack
				temp = this.auxiliary[i]
				this.auxiliary[i + 1] = temp
				this.auxiliary[i] = value
				break
			} else {
				// If not bigger or at first value, move iterated value up in stack
				temp = this.auxiliary[i]
				this.auxiliary[i + 1] = temp
			}
		}
	} else {
		// If bigger than top-most value of stack, place on top of stack
		this.auxiliary[this.count] = value
	}
	this.count++
}

Now we can add our new dequeue function that will allow us to remove the bottom value in our stack.

JavaScript

// Removes value from front of stack (queue dequeue)
Stack.prototype.dequeue = function() {
	var dequeueValue = this.storage[this.start]
	delete this.storage[this.start]

	// Delete from auxiliary stack
	var located = false
	for (i = 0; i < this.count; i++) {
		// If we've already found the matching value, we'll just reduce the indexes of the remaining values
		if (located == true) {
			// Delete the last value after copying
			if (i == this.count - 1) {
				this.auxiliary[i - 1] = this.auxiliary[i]
				delete this.auxiliary[i]
			} else {
				this.auxiliary[i - 1] = this.auxiliary[i]
			}
		} else {
			// If the value matches, delete it
			if(this.auxiliary[i] == dequeueValue) {
				delete this.auxiliary[i]
				located = true
			}
		}
	}
	// Increment starting point index
	this.start++
	// Lower count of stack
	this.count--
}

If we just had one stack for our main storage, this would be a piece of cake as we'd just need to delete the value found at the start index of our storage object. However, we also have to iterate over our 'auxiliary' stack (used for keeping track of the maximum value) to remove the matching value.

JavaScript

var values = [2,7,3,1,5,2,6,2]

function slideWindow(values, size) {
	// Create our new stack
	var window = new Stack()

	// Iterate over values
	for (j = 0; j <= values.length; j++) {
		if (window.size() < size) {
			// At beginning, populate window to size
			window.push(values[j])
		} else {
			// Log maximum value
			console.log(window.max())
			// Slide window
				// Dequeue first value
				window.dequeue()
				// Push new value
				window.push(values[j])
		}
	}
}

slideWindow(values, 4) // Logs 7 7 5 6 6

Tweet me @tylerewillis

Or send me an email: