CareerCup

There is an answer at stackoverflow, (relative path /a/17249084/288875)

The solution posted there works as follows:

* treat the array as consecutive, non-overlapping blocks of size k
* calculate 'running' minima: traverse the array from left to right.
At the start of each block, reset the variable holding the minimum seen so far,
at each position i store the minimum seen so far within this
block into an array LR[i]
* do the same thing also traversing the array in the opposite direction (from right to left),
storing the running minimum values into an array RL

Given a subarray starting at position i, the corresponding minimum is obtained as follows:

* if the subarray coincides with a block (i % k == 0 for zero based indexing), the
minimum is the last running minimum value of this block in the LR array, i.e. LR[i+k-1]
* otherwise, the subarray starting at i overlaps with two blocks: the overlap on the right
ends at i+k-1, LR[i+k-1] is then the minimum value found in the fraction of the right block
up to position i+k-1.
Similarly, the minimum of the overlap region of the block on the left starting at position i
is in RL[i].
The minimum of the requested subarray is therefore min(RL[i], LR[i+k-1])

Take a queue of size k, keep k elements in the queue at a time.
You can use min heap too.

This is minimum sliding array problem.

public static void MinSlideArray( int k){

		Deque<Integer> d = new ArrayDeque<Integer>(k) ;
		int[] ar = new int[]{9, 2, 3, 4, 8, 5, 6, 10};
		int i =0 ;
		for(; i<k; i++){

			while((!d.isEmpty() && ar[i] <= ar[d.getLast()])){
				d.pollLast();
			}

			d.addLast(i);
		}

		System.out.println("Min in deque");
		for(;i<ar.length; i++){

			System.out.println(ar[d.getFirst()]);

			//Removing front element out of windows
			while((!d.isEmpty() && d.getFirst() <= (i-k))){
				d.pollFirst();
			}

			while((!d.isEmpty() && ar[i] <= ar[d.getLast()])){
				d.pollLast();
			}

			d.addLast(i);
		}

		System.out.println(ar[d.getFirst()]);
	}

public static int minSum(int arr[], int k) { 
		int minsum = 0; 
		for(int i =0; i < k; i++) minsum += arr[i];
		int cSum = minsum; 
		for(int i =0; i < arr.length-k; i++) {
			cSum = cSum-arr[i]+arr[i+k];
			minsum = Math.min(minsum, cSum);
		}
		return minsum;
	}

You can check the min in the first subarray B, then, if B[0] = min, recalculate the min in the new subarray, if B[0] is not min, then you only have to check if the new element is less than the actual min.
This wil be O(n*n) in the worst case, but I guess than the mean complexity is not that bad.

Other option, build a binary tree (maybe a balanced tree) with the first k elements, this will be O(k*log(k)), then the min will always be the leaf at the left (to find this will be O(log(k))).
When finding the min in the new subarray, at first we have to delete the element that's leaving the subarray (O(1) if not balanced) and add the new element (O(log(k)), then find the min (O(log(k)).
As this has to be done n-k times, the complexity will be max(n-k,k)log(k), easier, n*log(k).

I think about using a binary tree (maybe a balanced binary tree).
At first it's necessary to build the tree with the k elements, this takes O(k*log(k)).
Then to find the min just check the leaf at the left, this will be O(log(k)).
When finding the min in the next subarray, at first it's neccesary to remove the element that's leaving O(1) and add the new element O(log(k)), this has to be done n-k+1 times, so the complexity will be O(n*log(k)).
If k = 1, then it will be O(n).

I think about using a binary tree (maybe a balanced binary tree).
At first it's necessary to build the tree with the k elements, this takes O(k*log(k)).
Then to find the min just check the leaf at the left, this will be O(log(k)).
When finding the min in the next subarray, at first it's neccesary to remove the element that's leaving O(1) and add the new element O(log(k)), this has to be done n-k+1 times, so the complexity will be O(n*log(k)).
If k = 1, then it will be O(n).

Here is the O(n) solution

Actually I hate this is a very difficult 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();
	}
}

IEnumerable<int> FindMinOfSubArrays(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;
	}
}

Its variation of Maximum slide array problem

public static void MinSlideArray( int k){

		Deque<Integer> d = new ArrayDeque<Integer>(k) ;
		int[] ar = new int[]{9, 2, 3, 4, 8, 5, 6, 10};
		int i =0 ;
		for(; i<k; i++){

			while((!d.isEmpty() && ar[i] <= ar[d.getLast()])){
				d.pollLast();
			}

			d.addLast(i);
		}

		System.out.println("Min in deque");
		for(;i<ar.length; i++){

			System.out.println(ar[d.getFirst()]);

			//Removing front element out of windows
			while((!d.isEmpty() && d.getFirst() <= (i-k))){
				d.pollFirst();
			}

			while((!d.isEmpty() && ar[i] <= ar[d.getLast()])){
				d.pollLast();
			}

			d.addLast(i);
		}

		System.out.println(ar[d.getFirst()]);
	}

Interesting. So, does "subarray" imply only a consecutive sequence of array elements, or can it mean any combination of k elements within the array?

Just to make sure that the requirement for this problem is clear here:
Say, the original array is: {23, 1, 4, 17, 5, 6, 8}, n is 7, the size of the original array
If we pick a sub array of size k, where k <= n. By definition of subarray, we will have
n - k +1 number of subarray of size k within array n.
Say we pick subarray of size k=3. The following subarray are:
{23, 1, 4}
{1, 4, 17}
{4, 17, 5}
{17, 5, 6}
{5, 6, 8}

Here is the code written C:

bool FindMin(int subArray[], int startIndex, int subArraySize, int arraySize, int *minValue)
{
bool found=false;
int i;
int lastIndex;

if ( (startIndex < 0) || (subArraySize <= 0) || (subArraySize > arraySize) )
{
*minValue = 0;
return(false);
}

if (subArraySize == 1)
{
*minValue = subArray[startIndex];
return(true);
}

*minValue = subArray[startIndex];
lastIndex = startIndex + subArraySize - 1;
for (i=startIndex; i <= lastIndex; i++)
{
if (subArray[i] < *minValue)
*minValue = subArray[i];
}


return(found);
}


int main(int argc, char *argv[])
{
int testArray[]={23, 1, 4, 17, 5, 6, 8};
int k=0;
int n;
int numLoop;
int i,j;
int minValue;

printf("Enter k\n");
scanf("%d",&k);
n = sizeof(testArray)/sizeof(int);
numLoop = n - k + 1;

for (i=0; i<numLoop; i++)
{
FindMin(testArray,i,k,n,&minValue);
printf("Min value of subArray{%d .. %d} is: %d\n",testArray[i], testArray[i+k-1], minValue);
}

return(0);
}

The complexity of the above code is: k * (n-k+1) ==> k * n

This problem can be solved in O(N) time, using a data structure call Deque, which is a queue that can be pushed/popped from both ends, in O(1) time.

The idea is: to maintain a sliding window of size K using deque. Once we push in from the right-end a number x, we need to pop out from the left-end all the numbers that are bigger than x, because these numbers cannot be a minimum of any future k-window.

I explained in details with code at this post:
capacode /array/finding-maximums-for-all-k-windows-in-linear-time/

This is an Objective-C solution

-(NSMutableArray *)getMinValueOfSubstringsInArray:(NSMutableArray *)array withSize:(int)k{
    
    if([array count] == 0 || k <= 0){
        return nil;
    }
    
    NSMutableArray *temp = [NSMutableArray new];
    NSMutableArray *result = [NSMutableArray new];
    int min = 0;
    
    for(int i = 0; i < [array count]; i++){
        
        if([temp count] >= k){
            
            min = [[[temp sortedArrayUsingSelector:@selector(compare:)] firstObject] intValue];
            [result addObject:[NSNumber numberWithInt:min]];
        }
        
        if(i >= k){
            
            [temp removeObject:array[i-k]];
        }
        
        [temp addObject:array[i]];
    }
    
    if([temp count] >= k){
        
        min = [[[temp sortedArrayUsingSelector:@selector(compare:)] firstObject] intValue];
        [result addObject:[NSNumber numberWithInt:min]];
    }
    
    return result;
}