CareerCup

In the window, we should keep all the order of the elements. So the best way is using min heap to keep this order. And the time complexity would be O(nlog(k)).

Here is the c++ code:

#include <iostream>
#include <vector>
using namespace std;

class sliding{
private:
    int heap[1000];
    int id[1000];
    int size;
    int parent(int index)
    {
        return index / 2;
    }
    void insertheap(int *array, int index)
    {
        ++size;
        heap[size] = index;
        id[index] = size;
        top(array, size);
    }
    void swap(int i, int j)
    {
        id[heap[i]] = j;
        id[heap[j]] = i;
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    void top(int *array, int index)
    {
        int p = parent(index);
        if (array[heap[p]] > array[heap[index]])
        {
            swap(p, index);
            top(array, p);
        }
    }
    void deleteheap(int *array, int index)
    {
        int heapi = id[index];
        swap(heapi, size);
        --size;
        down(array, heapi);
    }
    int left(int index)
    {
        return index * 2;
    }
    int right(int index)
    {
        return index * 2 + 1;
    }
    void down(int *array, int index)
    {
        int min = index;
        int l = left(index);
        int r = right(index);
        if (l <= size && array[heap[l]] < array[heap[min]])
        {
            min = l;
        }
        if (r <= size && array[heap[r]] < array[heap[min]])
        {
            min = r;
        }
        if (min != index)
        {
            swap(min, index);
            down(array, min);
        }
    }
public:
    sliding():size(0)
    {
        size = 0;
        heap[0] = -1;
    }
    vector<int> slidingWindow(int *array, int n, int k)
    {
        vector<int> result;
        if (k == 1)
        {
            result.insert(result.begin(), array, array + n);
            return result;
        }
        for (int i = 0; i < k; ++i)
        {
            insertheap(array, i);
        }
        result.push_back(array[heap[1]]);
        for (int i = k; i < n; ++i)
        {
            int del = i - k;
            deleteheap(array, del);
            insertheap(array, i);
            result.push_back(array[heap[1]]);
        }
        return result;
    }
};

int main()
{
    int n, k;
    int array[1000];
    sliding s;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> array[i];
    }
    vector<int> result = s.slidingWindow(array, n, k);
    vector<int>::iterator iter;
    for (iter = result.begin(); iter != result.end(); ++iter)
    {
        cout << *iter << " ";
    }
    cout << endl;
    return 0;
}

.1) Write a funtion to get the minimum element in a given array.Lets call this int GetMin(int array[],int n/*array size*/).
.2) Write another function that passes the sliding window of size k of the list to GetMin. This function prints the minimum function returned from GetMin.

An improvement make the GetMin function to avoid copying array element from one array to another.
int GetMin(int array/*original list*/,int startPos, int endPos)

general heap will not work as u cant heapify when u remove or add element in between levels except root...heapify says that from any node its subtrees follows heap property but that node may not...so if u replace any element in between, its subtrees and that node may satisfy heap property but from root it may not...

For ex- in min-heap of level 4, u replaced an outgoing element in level 2 with incoming element which is minimum to root.

In this case, one has to keep parent pointer to move upwards till root to satisfy heap property which will definitely be take O(logn) but

For replacement also first u have to reach to outgoing node by using either BSF or DFS which will take O(n)..so process is no better

<pre lang="" line="1" title="CodeMonkey70650" class="run-this">public class SlidingWindow {

private static int min=999999999;
private static int minIndex=-1;
private static final int windowSize=3;

public static void main(String[] args)
{
int[] arr = {5,1,3,2,6,8,4,6,2,1,3,4};

for(int i=0;i<(arr.length-windowSize+1);++i)
{
System.out.println(findMin(arr,i,i+windowSize-1));
}

}

private static int findMin(int[] arr, int start, int end) {

if((start<=minIndex))
{
if(arr[end]>=min)
return min;
else
{
min=arr[end];
minIndex=end;
}
}
else
{
min=999999999;

for(int i=start;i<=end;i++)
{
if(arr[i]<min)
{
min = arr[i];
minIndex =i;
}
}
}



return min;
}

}
</pre><pre title="CodeMonkey70650" input="yes">
</pre>

if we find min each time using standard klogk alg. then it would be (n-k)klogk.

if we maintain a min heap of size k then delete and insert both will take logk + logk time. thus total complexity (n-k)logk. thus if k is big enough in comparison to n . then heap would be best.

I think we can solve this problem in O(n) complexity and with using any extra space.
-> First find the minimum element among 0 -k by traversing.
-> Then as u move next in the window compare the minimum element with the just one new element in the window. becoz we already have min of 0-k, now we are moving by 1. So we just need to compare min found by us with k+1th element to get the min.
-> Simiarly we can found the Min in o(n) complexity without using extra space.

for each item(i) in i = 0 ... k - 1 // O(k)
  add item(i) to map // O(logk)
end for // O(klogk)
append min(map) to results
for each item(i) in i = k ... (n - k) // O(n - k)
  remove first item(i - k) from map // O(1)
  add item(i) to map // O(logk)
  append min(map) to results
end for // O((n-k)logk)

O(nlogk)

Create a binary search tree using the first k elements. This would be done in O(k.log(k)). Now move the window on the rest of the array one by one and delete the element to be removed from the BST O(log(k)) and insert the element to be added to the window to the BST which again takes O(log(k)). Keep reporting the left most leaf as the min everytime the window is moved. Hence, the final worst case order = O(k.log(k) + (n-k).(log(k)+log(k)+log(k))) = O((3n-2k)log(k)) which is equavalent to O(n.log(k))

Use a queue, which is implemented by two stack with min().
So the question is converted to implent a stack with min() in O(1). Just google it!
The amortized complexity is O(1)

Just maintain a min heap of k elements with duplicates. When window moves, replace the last element from heap with the new incoming element and then perform heapify down or up as necessary.

MinHeap + HashMap .... O(nlogn)

It's o(N) the answer.

O(n) solution exists for it

//following should work with complexity of n log k.


#include<stdio.h>

#define SIZE 10
int Array[SIZE] = {5,6,7,3,4,2,5,6,4,1};
int K = 3; // Sliding Window size

int slidingWindowMinIdx(int s)
{
int c, root, index, i;
index = s ; //assume min value is at root
for(i = s; i < s+K; i ++)
{
c = i;
do{
root = (c-1)/2;
if(Array[root] > Array[c] && Array[index] > Array[c]){
index = c;
}
c = root;
}while(c > s);
}
return index;
}
int main(){
int i;
for(i =0; i < SIZE - K + 1; i ++)
printf("\nMinimum value in sliding window is %d", Array[slidingWindowMinIdx(i)]);
return 0;
}

Use a deque (double-ended queue)
First insert the elements of the window size.
Maintain the minimum in the front ( for every window) this allows O(1) retrieval of minimum.
And make sure you only insert if the element in the new window is less than the current queue elements.

public static void maxSlidingwindow(int a[],int n,int w)
    {
        if(w<n)
        {
            int b[]=new int[n];
            Deque<Integer> q=new ArrayDeque<>();

            for(int i=0;i<w;i++)
            {
                while(!q.isEmpty() && a[i]>=a[q.peekLast()])
                    q.removeLast();
                q.addLast(i);
            }
            for(int i=w;i<n;i++)
            {
                b[i-w]=a[q.peekFirst()];
                while(!q.isEmpty() && a[i]>=a[q.peekLast()])
                    q.removeLast();
                while(!q.isEmpty() && q.peekFirst() >= i-w)
                    q.removeFirst();
                q.addLast(i);
            }
            b[n-w]=a[q.peekFirst()];

            for(int i=0;i<n;i++)
                System.out.print(b[i]+"\t");
        }
    }

I have seen correct solution to this somewhere here. It may be done in O(n) by having a queue. I will start with window from the left, adding each element to the TAIL of the queue with doing it specially (deleting all the elements bigger than the current added value, until I will reach lower one). Then I will print the HEAD of queue and in case it is going to be removed in next turn (it is the most left in the window), remove it... It is O(n), because every single element will be added once to the queue and also deleted once.