Maximal Surpasser Count Problem (Binary Search Tree Solution)

I really like Pearls of Functional Algorithm Design by Richard Bird. The book just has that unique quality to it – it makes you want to think. One problem got my attention – maximal surpasser count. You have an array of integers and for every element of the array you count the number of elements to the right that are strictly greater than that element. For example, the array may be:

82    74    17    93    96    20    25    55    15    24    25    56

and the resultant surpasser count array is:

2    2    8    1    0    5    2    1    3    2    1    0

and the maximal surpasser count is 8. Note, the problem asks to find 8, not to construct the array in full but we’ll do that anyway.

So the challenge is to figure out a O(n log n) time algorithm to solve this problem. The space complexity is not specified. The book outlines convoluted (and hence interesting) solution in Haskell, which is absolutely a must-learn language for any computer-science-minded individual. But let’s try to solve it using binary search tree only. If we succeed, we can code the problem in an imperative language using familiar algorithms and also in O(n log n) time.

The idea is simple. Every node in the tree is to have three fields – the key, i.e. number in the array that the node corresponds to, number of nodes inserted to the right (A) and the maximal surpasser count so far (B). There is one node for every distinct element of the array. We start reading the array from the right to the left. The first node gets a key of 56 and both fields are set to 0. Next number is 25, which gets inserted as a left child of 56. Because we made a move to the left, the new node will have to add 1 to its count of surpassers. Next one is 24, and, since it requires two moves to the left, it gets to have 2 as its count of surpassers Skipping 15, when we get to 55, we make one move to the left but then to the right. So node 55 will have surpasser count as 1 (correct) but what about node 25? Remember, 55 gets to be inserted to the right of 25. Node 25 will have its B incremented, and next node inserted after 25 will have to pickup the B.

Let’s take a look at what the solution looks like in C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 

class Node;
vector vc;

class Node {
  public:
    Node * left;
    Node * right; 
    int k;     // key
    int c;    // count of duplicate nodes
    int surpasserCount, largerThanCount; 
    Node(){    
      right = left = NULL;
      surpasserCount = largerThanCount = k = c= 0 ;
    }
};

void insert(const int k, Node * r, int m){
  if (k == r->k){
    r->surpasserCount = r->largerThanCount + m ;     
    r->c++;
    vc.push_back(r->surpasserCount);

  } else if (k k) {
    if (r->left){
      insert (k, r->left, m+1 + r->largerThanCount+r->c);
    } else {

      r->left = new Node; 
      r->left->k = k;       
      r->left->surpasserCount =  m+1 + r->largerThanCount + r->c;
      vc.push_back(r->left->surpasserCount);
    }

  } else {
    r->largerThanCount ++; 
    if (r->right){

      insert (k , r->right, m); 
    } else {

      r->right = new Node; 
      r->right->k = k;       
      r->right->surpasserCount = m + r->c;
      vc.push_back(r->right->surpasserCount);
    }  
  }
}

int main(int argc, char ** argv) {
  int k[] = {82, 74, 17, 93, 96, 20, 25, 55, 15, 24, 25, 56};
  int l = 12; 

  Node * r = new Node;
  r->k = k[l-1]; 
  vc.push_back(0);

  for (int i = l-2; i >= 0; i--){
    insert (k[i], r, 0);
  } 
  for (int i = vc.size()-1; i>=0;i--){
    cout << vc[i] << " ";
  }
  cout << endl;
  cout << "Maximal surpasser count is: " << * max_element(vc.begin(), vc.end()) << endl;
  return(0); 
}

http://www.amazon.com/Pearls-Functional-Algorithm-Design-Richard/dp/0521513383#reader_0521513383

Pearls of Functional Algorithm Design

In addition, below is a zip file (renamed as doc for upload purposes) which contains a bunch of pds with Small Programming Exercises by Rem (from the Science of Computer Programming journal dating back to 1990s or so). The maximal surpasser count problem is contained in one of these.

Small Programming Exercises.zip

Advertisements

~ by Monsi.Terdex on September 23, 2013.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: