CareerCup

Looks like below is not correct
B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.

here A[i-K+1] should be A[i+k-1]

if i=0, and k=4 then i-K+1 will be negative, which is not correct

the algo could go on like this....
1.scan the array in reverse order and create a min heap of k elements.
2.the element B[i] would be the element at the root of min heap.
3. now delete the element at A[K+i -1] and insert the element A[i-1]
4.reheapify the heap.
TC-O(nlogk)

I think question is that k is some given number and length of B is N-k+1,
So can be done in O(n) Time Complexity
Traverse the array from i=N-k+1 to i=0{
keep one min variable if(a[i]<min) min=a[i]
b[i]=min;
}

Is it not a sliding window problem ?

yes it should be i+k -1.

segment tree concept will be used

segment tree concept will be used

segment tree concept will be used

the algo could go on like this....
1.scan the array in reverse order and create a min heap of k elements.
2.the element B[i] would be the element at the root of min heap.
3. now delete the element at A[K+i -1] and insert the element A[i-1]
4.reheapify the heap.
TC-O(nlogk)

we can use selection to find the min. number and complexy will be o(n) and space used will be o(1).....

Solution: O(n) time and excluding the result space + O(1) space if there are no duplicates (if there are duplicates we can move them to the end of the array and use extra HashMap to count the duplicates)
Here is the java code for nonDuplicate version (can be easyly modified for duplicates) :

public int[] getFirstElements(int[] arr, int k) {
  int[] result = new int[k];
  
  int currK = 0;
  for (int i = 0; i < arr.length && currK < k; i++)
   if (arr[i] != 0)
    result[currk++] = arr[i]; 
 
  return result 
 }
 
 //O(n) time
 private void sortArr(int[] arr) {
  for (int i = 0; i < arr.length; i++)
   while (arr[i] != i || arr[i] != 0)
    swap(arr, arr[i], i);
 }

We can use binary search for it.
Step-1: Add 1st k elements to bst tree.
Step-2: Print the min element from bst tree
Step-3: Print min element and Remove the ith element
Step-4: Add the i+k+1 th element..i++
Step-5: Repeat Step-2,3,4 until no more elements

Using queue.

int arr[1000001];

void printKMax(int n, int k) {
    deque<int>  Qi(k);
 
    int i;
    for (i = 0; i < k; ++i) {
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();  // Remove from rear
 
        Qi.push_back(i);
    }
 
    for ( ; i < n; ++i) {
        printf ("%d ", arr[Qi.front()]);
 
        while ( (!Qi.empty()) && Qi.front() <= i - k)
            Qi.pop_front();  // Remove from front of queue
 
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();
 
        Qi.push_back(i);
    }
 
    printf ("%d", arr[Qi.front()]);
}

can be done in O(N)
1.b[0] = the minimum of (0,1,K-1)
2. b[1] = min(b[0], a[k]
3. b[2] = min(b[1], a[k+1]