spoj ARRAYSUB: O(n) Complexity Approach

Question

I was trying to solve this problems on spoj http://spoj.pl/problems/ARRAYSUB

I solved it using two approaches

firstly using optimised brute force. Secondly taking Pivot at k,2k,3k so on and finding maximum.

Although both Solutions are accepted in worst case there Complexity are O(n*k);

Can anyone Suggest O(n) solution Approach for the problems .

Below is my Running Accepted code of worst case complexity O(n*k):

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
main()
{
    long n;
    cin >> n;
    long *arr = new  long[n];
    for( long i=0;i<n;i++)
        cin >> arr[i];
     long k;
    cin >> k;
     long max=arr[0];
    for(long i=1;i<k;i++)
    {
        if(arr[i]>max)
            max=arr[i];
    }
    if(k!=n)
    cout<<max<<" ";
    else cout<<max;
    for( long i=k;i<n;i++)
    {
        if(arr[i-k]==max)
        {max=-1;
        for(int j=i-k+1;j<=i;j++)
        if(arr[j]>max)
        max=arr[j];
        if(i!=n)
        cout<<max<<" ";
        else cout<<max;

        }
        else{
        if(arr[i]>max)
        {   max=arr[i];

        if(i!=n)
        cout<<max<<" ";
        else 
        cout<<max;
        }
        else
        {
        if(i!=n)
        cout<<max<<" ";
        else cout<<max;}
        }
    }

        cout<<endl;
    return(0);
}

Answer 1

The data structure to be used to solve this problem in O(n) time is "deque"

A natural way most people would think is to try to maintain the queue size the same as the window’s size. Try to break away from this thought and try to think outside of the box. Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.

  void maxInWindow(vector<int> &A, int n, int k, vector<int> &B) {
  deque<int> Q;
  for (int i = 0; i < k; i++) {
    while (!Q.empty() && A[i] >= A[Q.back()])
      Q.pop_back();
    Q.push_back(i);
  }
  for (int i = k; i < n; i++) {
    B[i-k] = A[Q.front()];
    while (!Q.empty() && A[i] >= A[Q.back()])
      Q.pop_back();
    while (!Q.empty() && Q.front() <= i-k)
      Q.pop_front();
    Q.push_back(i);
  }
  B[n-k] = A[Q.front()];
  //B stores the maximum of every contiguous sub-array of size k    
}

Explanation :

The first for loop calculates the maximum of the first 'k' elements and store the index at Q.front(). This becomes B[0] = A[index]. The next section, we push and pop from the back if A[i] is greater than the previous maximum stored. We pop from front if the value of the index is less than i-k which means it is no more relevant.

Answer 2

One approach which is efficient than Brute Force is to use Red Black Trees (RB) as the data structure. Because RB trees has the property that insert, removal and find min or max in O(log n) time where n is the number of nodes in the tree.

Even though AVL Trees has the same property but the constant hidden behind the Big O is big compared to RB Trees.

The overall complexity for the problem will now become O(n lg k).

First insert k nodes in RB Tree and then use find max to get the max element. (2 * log k) Second we remove the first element that got inserted and then insert a new element and then query for max element. (3 * log k). Following the same procedure, approx we need (3 * n * log k). That is O(n* log k).

Currently naive brute force solution is not getting accepted but this solution got accepted.