Given an array of integers, A, and an integer value, K, create array B where B[i] is the minimum value in the sub-array A[i], A[i+1], ..., A[i+K-1]. Note that B.length will be equal to A.length - K.
For example for K = 3 and A=[1,2,3,4,0,1,2] the solution is B=[1,2,0,0,0].
A = [1,2,3,4,0,1,2]
_____| | | | |
B[1] = 1 | | | |
_____| | | |
B[2] = 2 | | |
_____| | |
B[3] = 0 | |
_____| |
B[4] = 0 |
_____|
B[5] = 0
A solution for O(kn) time complexity is as follows:
public static int[] createArray(int[] arr, int k) {
int[] result = new int[arr.length];
for (int i = 0; i <= arr.length - k; i++) {
int curSmallestVal = arr[i];
for (int j = i + 1; j < i + k; j++) {
curSmallestVal = Math.min(curSmallestVal, arr[j]);
}
result[i] = curSmallestVal;
}
return result;
}
Can you provide a more elegant solution with O(n) runtime? (potentially with using queues)
Update with the O(n) solution:
public static int[] getMinSlidingWindow(int[] arr, int k) {
int[] result = new int[arr.length-k+1];
Deque<Integer> queue = new LinkedList<Integer>();
//initialize sliding window
for (int i = 0; i < k; i++) {
if (!queue.isEmpty() && arr[queue.getLast()] >= arr[i])
queue.removeLast();
queue.addLast(i);
}
for (int i = k; i < arr.length; i++) {
result[i-k] = arr[queue.getFirst()];
while (!queue.isEmpty() && arr[queue.getLast()] >= arr[i])
queue.removeLast();
queue.addLast(i);
while (!queue.isEmpty() && queue.getFirst() <= i-k)
queue.removeFirst();
}
result[arr.length-k] = arr[queue.removeFirst()];
return result;
}
Using a double ended queue (one that supports adding pushing and poppoing from the front and the back) with a bit of extra logic you can construct a solution that runs O(n).
Here's the pseudocode for a solution.
void getMaxSlidingWindow(int[] A, int k) {
int[] B = new int[A.length - k];
// Store the indexes of A in Q
// Q.front(): index of smallest element in the window, Q.back(): index of the largest one in the window
DobuleEndedQueue<int> Q = new DobuleEndedQueue<int>();
for(int i=0; i<k; i++) {
// Fill up the double ended queue for the first k elements
// Remove elements that we would ignore because they're bigger than the next one in the window
while(!Q.empty() && A[i] <= A[Q.back()]) {
Q.popBack();
}
Q.pushBack(i);
}
for(int i=k; i < A.length; i++) {
B[i - k] = A[Q.front()]; // The first element in the queue is the index of the smallest element in the window
// Add the current element to the queue. Before we do, remove all elements that we would ignore immediately because they're bigger than the current one
while(!Q.empty() && A[i] <= A[Q.back()] ) {
Q.popBack();
}
Q.pushToBack(i);
// Remove any index from the front of the queue which is no longer in the window
while(!Q.empty() && Q.front() <= i-k) {
Q.popFront();
}
}
B[A.length - k] = A[Q.front()];
}
The time complexity of this solution is O(n): we iterate through all elements once and either add or remove them to the double ended queue once. The maximum operations done are 2n, which is a O(n) complexity.
For this solution to work you need to implement the double ended queue data structure with the following operations:
class DobuleEndedQueue
int front(), void pushFront(int n), void popFront() // peeks at the front element, adds and removes to the front
int back(), void pushBack(int n) , void popBack() // same for the back element
Further explanation for the algorithm with a simple example: