Sliding window minimum

July 26, 2018

Introduction

It is my 10:00 PM mock interview. I had chance to give the peer second algorithm to work on called sliding window minimum. He gave me the optimal solution but I could not fully understood the algorithm. So I decided to prove it the correctness using k = 3.

Mock interview discussion

I modified the transcript to make it more readable. Here is the transcript.

	given an integer array, give range size k, find minimum value in each range.
	for example, integer array [1, 2, 3, 4, 5]
	k = 3,
	min[0] = min{1, 2, 3} = 1
	min[1] = min{2, 3, 4} = 2
	min[2] = min{3, 4, 5} = 3
	The interviewee gave the proposal of solution using O(N) time complexity, preproces the array by two scans, one
	is from left to right, second one is from right to left.
	[1,2,3 | 4,5]
	leftToRight [1,1,1 | 4,4]
	rightToLeft [1,2,3 | 4,5]
	[1,2,
	[
	[43, 21, 34, 22, 12]
	lToR [43, 21, 21,||| 22, 12]
	rToL [21, 21, 34 12, 12]
	[
	1000 elements, k = 3
	1, 2, 3 ||| 4, 5, 6 ||| ....999 ||| 1000
	lToR - 1, 1, 1 ||| 4, 4, 4 |||
	RtoL - 1 2 3 ||| 4 5 6 ||| 999 ||| 1000
	rangeSum[i] = min(righToLeft[i], lefttoRight[i+k-1]);
	i=0, min(1, 1)
	i=1, min(2, 4) =2
	i=2, min(3,4) = 3
	So Julia as an interviewer tried very hard to understand the algorithm. After more than 3 minutes discussion,
	Julia said that it is better to prove that it is correct as well.
	Julia tried to give a proof about the correctness of the algorithm, since she has math major.
	She likes to prove the algorithm approach will work.
	Given an integer array, given size of k = 3, find minimum number in each sliding window.
	For example, k = 3, there are three possible values.
	i%3 == 0
	0, 1, 2
	case 0:
	first test case, rightToLeft[i] cover minimum number of 3 numbers
	case 1:
	rightToLeft, rightToLeft[i] covers two numbers
	leftToright -> i + k - 1, next window, first element,
	cover first one
	in total we have k numbers covers - 3
	by math, in total there are 3 numbers
	case 2:
	rightToLeft, one number
	LeftToright, two number
	in total 3 numbers

view raw sliding window minimum hosted with ❤ by GitHub

To summarize, the sliding window minimum algorithm can be solved using two scan of array, one from left to right, second one from right to left. And then each scan the minimum value is calculated after the elements of array are divided into windows with size k.

Follow up

Feb. 12, 2019

I just learned that the interviewee joined Google this Feb. 2019. I like to review mock interview, and also I like to write an algorithm based on his idea as well.