CareerCup

This prob is equiv f finding the k-smallest elements, then ans is their sum.
Find the kth smallest using QuickSelect Algo and choosing pivot by median-of-medians method. O(n)
2. Use this element to partition the array so that all smaller elements come to one side.O(n)

Can any one please explain the question in detail? What we need to find with an example please

How about creating a min heap of size k and adding elements as we scan through the array.

This can be done easily using a deque.We loop through the array, and at the same time we keep a deque with the minimums.Always, the front of the deque will be the minimum of the current subarray of length k.At a new value, while the last value in the deque is greater than the new one, we pop it.So it the deque will remain only the smallest values. If the current value and the beginning of the deque have indexes at a distance greater than k in the array, we pop from the beginning of the deque.At last, if the current index is greater than k, we can return the front of the deque as the samllest value in the current subarray of length k.Time complexity O(N) and space O(N).

@bogdan.cebere
could u plz elaborate ur approch

@bogdan.cebere
could u plz elaborate ur approach

Suppose A is the original vector, N it's length and deque the vector that acts like a deque. Initially back = -1 and front = 0.In the deque vector we keep the positions possible for the answer in the current subarray of length K. First we pop values front the back of the deque as long as the value at the position deque[back] is greater than the one at the position i. After we check is i - deque[front] is less or equal than K.If it isn't, it means that the valuw at deque[front] isn't useful anymore because it is too far from to current position. Finally, if we alredy seen k numbers, it means we can start to get minimums, whick will always be stored in deque[front]. I hope it's clear

for(int i = 1 ; i <= N ; i++)
   {
    while(front<=back && a[i]<=a[deque[back]]) back--;
    deque[++back]=i;
    if(deque[front] == i-K) front++;
    if(i >= K) printf("%d\n",a[deque[front]]);
    }

@Nitin Agarwal,
Could you please explain the question in detail with one example?

That can be easily accomplished by keeping an array 'sum' which will hold the sum of previous 'k' elements(including current one) and take the min. of them. Keeping the sum can be done in O(N) time and in O(N) space (you can even get it down to O(1)).
Here is the code for the same:

int input[200];
int main()
{
	int N,K;
	cin >> N >> K;
	FOR(i,0,N) cin >> input[i];
	int ans = 1<<25;
	int sum = input[0];
	FOR(i,1,N)
	{
		if(i<K)
		{
			sum += input[i];
		}
		else 
		{
			sum = input[i]+sum-input[i-K];
		}
		if(i>=K-1)ans = min(ans,sum);	
	}
	if(ans == (1<<25))cout << "Doesn't exist...\n";
	else cout << ans << endl;
}

Subarray is not contigious, So I doubt if we can do it O(n) time.
Next what should the output? subarray and minimum?

If the subarray is contiguous then scan through array once in o(n) time maintaining sums over a moving window of size k. Sum calculation for each window can be done in o(1) time by maintaining a queue structure to remove element from front of queue and add a new one to back.

If the subarray is not contiguous then scan through the array once and find the min k elements by putting them into a min heap of size k. At the end sum up the element in the heap, that is the answer

We can partition the array according to (i+1)th smallest element.