Given the array A and the number K, create an array B, where B [i] = min (A [i], A [i + 1] .. A [i + K - 1])
For an array of integers A
and an integer value K
, create an array B
, where B[i]
is the minimum value in the subaddress A[i], A[i+1], ..., A[i+K-1]
. Note that it B.length
will be equal A.length - K
.
For example, for K = 3
and the A=[1,2,3,4,0,1,2]
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
The solution for time complexity O (kn) 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 using queues)
Update with 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;
}
source to share
Using a double queue (which supports adding pushing and poppoing front and back) with some extra logic, you can build a solution that runs O (n).
Here's pseudo code 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 all the elements once and add or remove them to the double terminated queue. The maximum operations performed is 2n, which is O (n) complexity.
For this solution, you need to implement a double terminated 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 of the algorithm with a simple example:
- Iterate through the first k elements and insert them as indices into the double-terminated Q data structure so that A [Q.front ()] is the smallest element and A [Q.back ()] is the largest element in the window.
- As we create the window, we discard "unnecessary" elements from this queue: both the smallest elements that would not have been counted, and elements that are outside the window
- An example of building a queue for A = [8, 6, 9, 2] and k-3
-
- Q = [0], (Insert 0 at the end of Q because A [0] is the smallest item we've seen.)
-
- Q = [1], (A [1] <Q.back () so pull out the back item and replace it with 1. We do this because A [0] doesn't matter when looking for the smallest number from now.)
- Q = [1, 2], B = [8] (A [2] is> Q.back (), so we just add 2 to Q. B [0] will be the smallest element in Q, which is A [Q. first ()], that is, A [1])
- Q = [3], B = [8, 2] (A [4] is less than all elements in Q, so we spread them all, B [1] will be the smallest element in Q, A [Q.first ()], then is A [3]
source to share
Reach O(n)
time complexity by using a standard algorithm with minimum slip deteksom. Here is a detailed description: http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
source to share
The first idea that comes to my mind is to use two sets. Both sets are preserved std::pair<index_t,value_t>
, but in a different order. (one ordered by index and one by value). This way you can iterate through the array at each step to find the minimum (first element in the set, sorted by value), and which element / pair to remove from both sets (first element in the set, sorted by index). In each step, you add a pair to each set and remove a pair from each set.
source to share