CareerCup

Question seems incomplete. Are you asking for all possible(over-lapping) sub-arrays of size k? And minimum of what? Do we need to sum them? or min element in them?

Actually I hate this is a very defficult problem to solve in O(n).
I was doing similar exercise of implement a queue with a Max() function from the book "Elements of Programming Interviews" which has a O(n) 'Ninja' level solution which I could not get as it required a another 'ninja' solution from another problem.

This is a variation of implementing a Queue which had a Max function which used a Stack which maintained the max but in this case it maintains the minimum.

This is a very hard solution to perform this in O(n) taking O(n) space as well.

class Stack<T>()
{
	List<StackNode<T>> buffer = new List<StackNode<T>>();
	private class StackNode<T>
	{
		T Value;
		T Min;
	}

	public void Push(T val)
	{
		var node = new StackNode<T>();
		node.Value = val;
		if(buffer.Count == 0 || buffer[buffer.Count - 1].Min > val)
		{
			node.Min = val;
		}
		else
		{
			node.Min = buffer[buffer.Count - 1].Min;
		}

		buffer.Add(node);
	}

	void T Pop()
	{
		var node = buffer[buffer.Count - 1];
		buffer.RemoveAt(buffer.Count - 1);
	
		return node.Value;
	}

	public bool IsEmpty()
	{
		return buffer.Count == 0;
	}

	public T Min()
	{
		if(buffer.Count > 0)
			return buffer[Count - 1].Min;

		return default(T);
	}
}

public class Queue<T>
{
	Stack<T> A = new Stack<T>();
	Stack<T> B = new Stack<T>();

	public void Enqueue(T val)
	{
		A.Push(val);
	}

	public T Dequeue()
	{
		if(B.IsEmpty())
		{
			while(!A.Empty())
			{
				B.Push(A.Pop());
			}
		}

		return B.Pop();
	}

	public T Min()
	{
		wile(!A.Empty())
		{
			B.Push(A.Pop());
		}

		return B.Min();
	}
}

public IEnumerable<int> FindMinOfSubArray(int[] A, int k)
{
	if(A.Length < k) throw ArgumentOutOfRangeException("k");
	Queue q = new Queue();

	for(int i = 0; i < k; i++)
	{
		q.Enqueue(A[i]);
	}

	int min =	q.Min();
	for(int j = k; j < A.Length; j++)
	{
		q.Enqueue(A[j]);
		q.Dequeue();

		var temp = q.Min();
		if(min > temp)
			min = temp;

                yield return min;
	}
}

In order to keep time-complexity at O(n), only one loop can be used. So, to avoid a second loop, the first has to repeat itself to iterate thru each subarray.

import java.util.*;

public class Careercup5 {
	public static ArrayList findMin(ArrayList<ArrayList<Integer>> main){
		ArrayList<Integer> result = new ArrayList<Integer>();
		int smallestValue = Integer.MAX_VALUE;
		int j = 0;
		int n = main.size(); //size of array
		int k; //size of each subarray
		
		for (int i = 0; i < n; i++){
			k = main.get(i).size(); 
			
			if (j < k){
				smallestValue = Math.min(smallestValue, main.get(i).get(j)); //find new minimum value
				j++;	//helps iterate thru subarrays
				i--;	//helps keep the loop at current subarray
			}
			else {
				j = 0;
				result.add(smallestValue);
				smallestValue = Integer.MAX_VALUE;
			}
		}
		return result;
	}
}

Main{}

for (int i=0; i<n; i++) {
	    if (i>=k) {
	        cout << q.front() << " ";
	        if (q.front() == a[i-k]) {
	            q.pop();
	        }
	    }
	    while (!q.empty() && a[i] < q.front()) {
	        q.pop();
	    }
	    q.push(a[i]);
	}
	cout << q.front() << endl;
	return 0;

Assuming its for every overlapping array, here is a simple order of N solution.

int min = array[0]
 for(int i=0: k-1){
	if(array[I] < min)
		min = array[i];
}
cout<<"Min so far" << min;
for(int j = k : j<n-1){
	if(array[j] < min){
		min = array[j];
		//display min
	}
}