CareerCup

The idea is to keep a queue of the last K items, by enqueing each new item and dequeing the oldest item. When enqueing an item, compare it the elenents in front of it in the queue, and discard them if they are larger (since they will never be the smallest now that a new smaller item is added to the queue):

from collections import deque

def slide_win(l, k):
  dq=deque()
  for i in range(0,len(l)):
    while len(dq)>0 and dq[-1][1]<=i-k:
      dq.pop()
    while len(dq)>0 and l[i]<=dq[0][0]:
      dq.popleft()
    dq.appendleft((l[i],i))
    if i>=k-1:
      print dq[-1][0]

def main():
  l=[3,9,7,2,5,4,8,2,4,3]
  k=3
  print "l="+str(l)
  print "k="+str(k)
  slide_win(l,k)

public static void printMin(int[] input, int windowSize) {
        for(int i = 0; i <= input.length - windowSize; i++){
            int localMin = Integer.MAX_VALUE;
            for(int j = i; j < i + windowSize; j++){
                if(input[j] < localMin ){
                    localMin = input[j];
                }
            }
            System.out.println("Min : " + localMin);
        }
    }

How about using the priority queue like below:

private static void printMin2(int[] input, int windowSize){
        PriorityQueue queue = new PriorityQueue();
        for (int i = 0; i < windowSize; i++) {
            queue.add(input[i]);
        }
        System.out.println("Min : " + queue.peek());
        for (int i = windowSize ; i < input.length; i++) {
            queue.remove(input[i-windowSize]);
            queue.add(input[i]);
            System.out.println("Min : " + queue.peek());
        }
    }

Complexity is O(n * log (windowSize))

#include <stdio.h>
#include <string.h>
#define size(a) sizeof(a)/sizeof(a[0])
int main(int argc, char *argv[]){
int arr[] = {3,9,0,3,18,6}, k = atoi(argv[1]), i = 0,j = 0;
int n = size(arr) - k +1;
for(i = 0;i < n;i++){
int min = arr[i];
for(j = i+1; j < (i+k);j++ )
if(arr[j] < min) min = arr[j];
printf("%d ", min);
}
printf("\n");
return 0;
}

void least(int arr[], int k, int n)
{
	int *temp = (int *)malloc(sizeof(int)*k);
	
	int i, j, start, end;

	for(i=0; i<k; i++)
	{
		temp[i] = arr[i];
	}
	
	sort(temp, k);

	int start = 0;
	for(i=0;i<k; i++)
	{
		if(temp[i] = arr[k-1])
		{
			end = i;
			break;	
		}
	}

	printf("%d\t", temp[start]);
	
	j = k;

	while(j < n)
	{

		if(arr[j] < temp[start])
		{
			temp[start] = arr[j];
			end = start;
		}
		else if(arr[j] >= temp[end])
		{
			end = (end+1)%(k+1);
			temp[end] = arr[j]);
		}
		else
		{
			end = find_position(temp, start, end, arr[j]);
			temp[end] = arr[j];
		}			 
			
		
		if(arr[j - k] == temp[start])
		{
			start = (start+1)%k;
		}
		printf("%d\t", temp[start]);
		
	}
}

//this is a C version if anyone needs it.
void SmallestNumber()
{
    int arr[] = {3,9,0,3,18,6};
    int n = 6;
    int k = 3; //window
    int p = 0;
    int s = 0;
    for(int i=0;i<=n-k;i++)
    {
        for(int n=0;n<k;n++)
        {
            int t = arr[i+n];
            if(n == 0 || t < s)
            {
                s = t;
            }
        }
        if(i==0)
        {
            printf("%d",s);
        }
        else
        {
            printf(",%d",s);
        }
    }
     printf("\n");
}

All solutions posted so far have time complexity O(n*k) at best.
It's possible to achieve a O(n*logk) solution by combining a min heap with a
queue. We need the heap to extract the min element in logk time and we need the queue to keep track of the last element (the one that has to be removed from the heap).

The problem with a heap only is that when an element falls out of the window, we need O(k) time to find it in the heap and remove it. The idea is to keep a queue inside the heap: heap nodes have a next pointer which points to the next element in the window; we also keep a head and a tail pointer to that queue.
Now when the window slides, the node pointed by head falls out of it, so we can find it in constant time and replace it with the new element that enters the window and then re-heapify (thats O(logk) operation). Thus, the total time complexity is O(n*logk)

Here is the C++ code (sorry if it's too long but I had to implement a heap myself since C++ library does not provide O(logk) heapify operation)

(whitespace got screwed)

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cassert>

using namespace std;

template<class T>
struct Node {
    Node * next;
    size_t index;
    T value;

    Node(const T& value, size_t index = 0):next(NULL), index(index), value(value) {}
};

template<class T>
void swap(Node<T> *&a, Node<T> *&b)
{
    std::swap(a->index, b->index);
    std::swap(a, b);
}

template<class T>
bool max_node(Node<T> * a, Node<T> * b)
{
    return a->value < b->value;
}

template<class T>
bool min_node(Node<T> * a, Node<T> * b)
{
    return a->value > b->value;
}

template<class It, class Comp>
void heapify(It begin, It end, It pos, Comp comparator)
{
    It left = begin + 2 * distance(begin, pos) + 1;
    It right = begin + 2 * distance(begin, pos) + 2;
    It largest = pos;

    if (left < end && comparator(*pos, *left)) {
        largest = left;
    }
    if (right < end && comparator(*largest, *right)) {
        largest = right;
    }
    if (largest != pos) {
        swap(*pos, *largest);
        heapify(begin, end, largest, comparator);
    }

}

template<class It, class Comp>
void build_heap(It begin, It end, Comp comparator)
{
    for (It it = begin + distance(begin, end) / 2;it >= begin;--it) {
        heapify(begin, end, it, comparator);
    }
}

template<class T>
void min_sliding_window(vector<T> vals, size_t k)
{
    Node<T> *head, *tail;
    vector<Node<T>*> heap;

    heap.push_back(new Node<T>(vals[0], 0));
    for (size_t i = 1;i < k;++i) {
        Node<T> *tmp = new Node<T>(vals[i], i);
        heap.back()->next = tmp;
        heap.push_back(tmp);
    }

    head = heap[0];
    tail = heap[heap.size() - 1];

    build_heap(heap.begin(), heap.end(), min_node<T>);

    for (size_t i = k;i < vals.size();++i) {
        cout<<heap[0]->value<<" ";
        assert(head->next);
        tail->next = head;
        tail = tail->next;
        head = head->next;
        tail->value = vals[i];

        heapify(heap.begin(), heap.end(), heap.begin() + tail->index, min_node<T>);
    }
    for (size_t i = 0;i < heap.size();++i) {
        delete heap[i];
    }
}

int main()
{
    int k = 4;
    int n = 20;
    vector<int> vals;
    for (size_t i = 0;i < n;++i) {
        int n = rand() % 100;
        vals.push_back(n);
        cout<<n<<" ";
    }
    cout<<endl;
    min_sliding_window(vals, k);
}

void minWindow(vector<int> &v, unsigned k)
{
	int mi = 0;
	int m = v[0];

	for (int i = 1; i < min(v.size(), k); ++i) {
		if (v[i] < m) {
			m = v[i];
			mi = i;
		}
	}
	
	cout << m << endl;

	for (int i = 1; i+k <= v.size(); ++i) {
		if (v[i+k] < m) {
			m = v[i+k];
			mi = i;
		}
		if (i > mi) {
			m = v[i];
			mi = i;
			for (int j = mi; j+k < v.size(); ++j) {
				if (v[j] < m) {
					m = v[j];
					mi = j;
				}
			}
		}
		
		cout << m << endl;
	}
}

import java.util.Random;
public class MinimumNumberInWindow {
	static int[] inputArray;
	@SuppressWarnings("unused")
	public static void main(String[] args) {
		final int ARRAY_SIZE = 15;
		final int WINDOW_SIZE = 3;
		
		if(WINDOW_SIZE > ARRAY_SIZE){
			throw new IllegalArgumentException("Window Size greater than Array Size");
		}
		
		//Prepare Data
		System.out.println("input: ");
		inputArray = new int[ARRAY_SIZE];
		Random random = new Random();
		for(int i=0; i<ARRAY_SIZE;i++){
			inputArray[i] = random.nextInt(100);
			System.out.print(inputArray[i]+" ");
		}
		
		//Find min in the Initial Window
		System.out.println("");
		System.out.println("Result: ");
		int minIntIndex = findMinEleInWindow(0, WINDOW_SIZE);
		int minElement = inputArray[minIntIndex];
		System.out.print(minElement+" ");

		for(int i=1;i<=(ARRAY_SIZE-WINDOW_SIZE);i++){
			if(inputArray[WINDOW_SIZE+i-1] <= minElement){
				minElement = inputArray[WINDOW_SIZE+i-1];
				minIntIndex = WINDOW_SIZE+i-1;
			}else if(minIntIndex < i){
				minIntIndex = findMinEleInWindow(i, WINDOW_SIZE);
				minElement = inputArray[minIntIndex];
			}			
			System.out.print(minElement + " ");
		}
	}

	public static int findMinEleInWindow(int startIndex, int WindowSize){
		int minElement=inputArray[startIndex];
		int minIndex = startIndex;
		for(int i=startIndex+1; i<(WindowSize+startIndex); i++){
			if(inputArray[i] <= minElement){
				minElement = inputArray[i];
				minIndex = i;
			}
		}
		return minIndex;
	}
}

private static int FindMinElementIndex(int[] input, int startIndex, int endIndex)
{
	var index = -1;
	for (var i = startIndex; i <= endIndex; i++)
	{
		if (index == -1 || input[i] < input[index])
			index = i;
	}
	return index;
}
private static void PrintMinimumElements(int[] input, int windowSize)
{
	var minElementIndex = -1;
	for (var i = 0; i <= input.Length - windowSize; i++)
	{
		if (minElementIndex != -1 && minElementIndex >= i)
		{
			minElementIndex = input[minElementIndex] < input[i + windowSize - 1] ? minElementIndex : i + windowSize - 1;
		}
		else
		{
			minElementIndex = FindMinElementIndex(input, i, i + windowSize - 1);
		}
		if(i>0)
			Console.Write(", ");
		Console.Write(input[minElementIndex]);
	}
	Console.WriteLine();
}
static void Main()
{
	var array = new[] {51, 23, 47, 89, 123, 12, 78, 90, 32};
	PrintMinimumElements(array, 3);
}

Using dynamic programming:
Use the n*W matrix and as we do for the Matrix chain multiplication,
start from the diagonal. And Diagonal element would be the same as the array values.
Then keep on increasing the interval as 2,3,4,....to the window size.
The recurrence would be
A[i][j] = min(A[i][j-1], A[j-1][j]).

This algo will fill the matrix of window size W for each row N so the complexity of the algo would be O(n*W).
same would be the space complexity.

I have doubt.So we need to print smallest number from every array after dividing using window.

Just find the first windows minimum then compare it with the next element that is being added go th window since it is the only new element. Also since the first element is removed and if it is the smallest you will have to find the second smallest if this is the case. Shouls just be another boolean value to keep track of. Worst complexity is o( n*n) but avg is just o(1)

why is everyone trying his own way? the best one is to use a double linkedlist which will reduce it to O(n). it's called sliding window problem. you can find the solution everywhere