algorithm - Given the array A and the number K create array B where B[i] = min(A[i], A[i+1].. A[i + K - 1]) -

algorithm - Given the array A and the number K create array B where B[i] = min(A[i], A[i+1].. A[i + K - 1]) -

given array of integers, a, , integer value, k, create array b b[i] minimum value in sub-array a[i], a[i+1], ..., a[i+k-1]. note b.length equal a.length - k.

for illustration k = 3 , a=[1,2,3,4,0,1,2] solution 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 o(kn) time complexity follows:

public static int[] createarray(int[] arr, int k) { int[] result = new int[arr.length]; (int = 0; <= arr.length - k; i++) { int cursmallestval = arr[i]; (int j = + 1; j < + k; j++) { cursmallestval = math.min(cursmallestval, arr[j]); } result[i] = cursmallestval; } homecoming result; }

can provide more elegant solution o(n) runtime? (potentially using queues)

update 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 (int = 0; < k; i++) { if (!queue.isempty() && arr[queue.getlast()] >= arr[i]) queue.removelast(); queue.addlast(i); } (int = k; < 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()]; homecoming result; }

using double ended queue (one supports adding pushing , poppoing front end , back) bit of logic can build solution runs o(n).

here's pseudocode solution.

void getmaxslidingwindow(int[] a, int k) { int[] b = new int[a.length - k]; // store indexes of in q // q.front(): index of smallest element in window, q.back(): index of largest 1 in window dobuleendedqueue<int> q = new dobuleendedqueue<int>(); for(int i=0; i<k; i++) { // fill double ended queue first k elements // remove elements ignore because they're bigger next 1 in window while(!q.empty() && a[i] <= a[q.back()]) { q.popback(); } q.pushback(i); } for(int i=k; < a.length; i++) { b[i - k] = a[q.front()]; // first element in queue index of smallest element in window // add together current element queue. before do, remove elements ignore because they're bigger current 1 while(!q.empty() && a[i] <= a[q.back()] ) { q.popback(); } q.pushtoback(i); // remove index front end of queue no longer in window while(!q.empty() && q.front() <= i-k) { q.popfront(); } } b[a.length - k] = a[q.front()]; }

the time complexity of solution o(n): iterate through elements 1 time , either add together or remove them double ended queue once. maximum operations done 2n, o(n) complexity.

for solution work need implement double ended queue info construction next operations:

class dobuleendedqueue int front(), void pushfront(int n), void popfront() // peeks @ front end element, adds , removes front end int back(), void pushback(int n) , void popback() // same element

further explanation algorithm simple example:

iterate through first k elements , insert these indexes double ended q info construction a[q.front()] smallest element , a[q.back()] largest element in window. as build window, throw out "unnecessary" elements queue: both smallest elements not counted , elements outside of window example of building queue a=[8, 6, 9, 2] , k-3 q = [0], (insert 0 of q because a[0] smallest element we've seen.) q = [1], (a[1] < q.back() pop element , replace 1. because a[0] irrelevant when looking smallest number on.) q = [1, 2], b=[8] (a[2] > q.back(), add together 2 on q. b[0] smallest item in q, a[q.first()], a[1]) q = [3], b=[8, 2] (a[4] smaller elements in q, pop of them. b[1] smallest item in q, a[q.first()], a[3]

arrays algorithm deque