Sliding window minimum

Sept. 13, 2018

Introduction

It is third time in the row I had chance to be an interviewer last few days. I had chance to learn from those interviewees, specially I can tell the super good performance.

I used the algorithm called sliding window minimum. I like to write a solution for hard level sliding window maximum in short future using the similar idea.

Sliding window minimum

Here is the code I like to study again written by the mock interviewee.

	/*second algorithm:
	given an integer array, for example, [3, 5, 4, 6, 5, 9, 7], given an integer k = 3
	minArray[0] = min{3, 5, 4}
	minArray[1] = min{5, 4, 6}
	minArray[2] = min{4, 6, 5},
	...*/
	/*
	arr = [3, 5, 4, 6, 5, 9, 7]
	k = 3
	res = [3, 4, ]
	dq = [2,3]
	i = 3
	*/
	public List<Integer> minSlidingWindow(int[] arr, int k) {
	List<Integer> res = new ArrayList<>();
	if (k == 0 || arr == null || arr.length == 0 || k > arr.length) return res;
	Deque<Integer> dq = new LinkedList<>();
	for (int i = 0; i < arr.length; i++) {
	// compute min
	// popFront of deque while element index < (i - k + 1)
	while (!dq.isEmpty() && q.peekFirst() < (i-k+1)) dq.pollFirst();
	// maintain min;
	while (!dq.isEmpty() && arr[dq.peekLast()] > arr[i]) dq.pollLast();
	dq.offerLast(i);
	if (i >= k-1)
	res.add(arr[dq.peekFirst()]); // ?
	}
	return res;
	}

view raw SlidingWindowMinimum.java hosted with ❤ by GitHub

I like to write the similar solution using C#.