Monday 14 October 2013

Maximum of all subarrays of size k in O(n) time and O(1) extra space !!

#include<stdio.h>
#include<limits.h>

void printKMax(int *arr, int n , int k)
{
    int max=INT_MIN, sec_max=INT_MIN, tag=0,cnt=0;
    int i, max_i, sec_max_i;
   
    for(i=0;i<n;i++)
    {
        if(arr[i]>=max)
        {
            max = arr[i];
            max_i=i-cnt;
        }
       
        else if(arr[i]>=sec_max)
        {
            sec_max = arr[i];
            sec_max_i=i-cnt;
        }
       
        if(i==k-1)
            tag=1;
       
        if(tag)
        {
            cnt++;
            printf("%d ", max);
                   
            max_i--;
            sec_max_i--;
           
            if(max_i==-1)
            {
                max_i = sec_max_i;
                max=sec_max;
                sec_max = INT_MIN;
            }
        }
    }
        printf("\n");
}

int main()
{
    int arr[] ={3,7,1,213, 12, 312};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    printKMax(arr, n, k);
    return 0;
}

1 comment:

  1. this code is incorrect when the array is sorted in descending order.

    ReplyDelete