CareerCup

Merge Sort modification which sorts initial array "a" in decreasing order, but in spite of modifying given array it modifies an array of indexes "b", which allows to track surpassers in the third array "c". Array "t" is a temp buffer used for merging purposes as required by Merge Sort algorithm.
Time: O(n log n).
Space: O(n).

class MaxSurpasser {
    int[] a, b, c, t;

    private MaxSurpasser(int[] a) {
        this.a = a;
        this.b = new int[a.length];
        this.c = new int[a.length];
        this.t = new int[a.length];
        for (int i = 0; i < b.length; i++){
            b[i] = i;
        }
    }

    public static int find(int[] a) {
        return new MaxSurpasser(a).search();
    }

    private int search() {
        mergeSort(0, a.length - 1);
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (c[i] > max) {
                max = c[i];
            }
        }
        return max;
    }

    private void mergeSort(int l, int r) {
        if (l >= r) {
            return;
        }
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);
        int i = l;
        int j = m + 1; int acc = 0;
        for (int s = l; s <= r; s++) {
            if (j > r || i <= m && a[b[i]] >= a[b[j]]) {
                t[s] = b[i];
                c[b[i]] += acc;
                i++;
            } else {
                t[s] = b[j];
                acc++;
                j++;
            }
        }
        for (int s = l; s <= r; s++) {
            b[s] = t[s];
        }
    }
}

public static void surpass(int[] a){

int max = 0; int result[] = new int[a.length];
for(int i=1; i<a.length; i++){
for(int j=0; j<i; j++){
if(a[i] > a[j]){
result[j] +=1;
max = Math.max(max, result[j]);
}
}
}
}

public static void main(String[] args){
		int[] array = new int[]{2,7,5,5,2,7,0,8,1};
		System.out.println(getMaxSurpasser(array, 0));
	}
	
	public static int getMaxSurpasser(int [] array, int index){
		if(array.length <= index){
			return -1;
		}
		int element = array[index];
		int surpasserCount = 0;
		for(int i=index + 1; i<array.length; i++){
			if(array[i] > element){
				surpasserCount ++;
			}
		}
		int nextSurpasserCount = getMaxSurpasser(array, index + 1);
		return surpasserCount > nextSurpasserCount ? surpasserCount : nextSurpasserCount;
	}

public static void main(String[] args){
		int[] array = new int[]{2,7,5,5,2,7,0,8,1};
		System.out.println(getMaxSurpasser(array, 0));
	}
	
	public static int getMaxSurpasser(int [] array, int index){
		if(array.length <= index){
			return -1;
		}
		int element = array[index];
		int surpasserCount = 0;
		for(int i=index + 1; i<array.length; i++){
			if(array[i] > element){
				surpasserCount ++;
			}
		}
		int nextSurpasserCount = getMaxSurpasser(array, index + 1);
		return surpasserCount > nextSurpasserCount ? surpasserCount : nextSurpasserCount;
	}

Time: O(n log n)
Space: O(n)

int maxSurpasser(vector<int> input)
    {
        vector<int> copied(input.begin(), input.end());
        sort(copied.begin(), copied.end());

        int maxSurpasser = -1;

        for (int const& i : input)
        {
            auto begin = std::lower_bound(copied.begin(), copied.end(), i);
            auto end = std::upper_bound(begin, copied.end(), i);

            maxSurpasser = max(maxSurpasser, copied.end() - end);
            copied.erase(begin, end);
        }

        return maxSurpasser;
    }

public class SurPasser {
public static void main(String[] args) {
int a[] = { 2, 7, 5, 5, 2, 7, 0, 8, 1 };
findSurPasser(a);
}

private static void findSurPasser(int[] a) {
int n = a.length;
int sp[] = new int[n];
for (int i = 0; i < n; i++)
sp[i] = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] < a[j])
sp[i] = sp[i] + 1;
}
}
int max = 0;
for (int i = 0; i < n; i++)
if (max < sp[i])
max = sp[i];
System.out.println(max);
}
}

Create a bst inserting elements going from i=0 to N.
Now in this bst find the right subtree which has max number of elements.
complexity: nlogn (avg) worst n2

public static int surpasser(int[] arr){
    if(arr==null){
           throw new NullPointerException();
    }
    
    int flagList[arr.length];
    int maxS = 0;
    flagList[0] = 1;
    for (int i=0;i<arr.length;i++){
        if(flagList[i]){
            int localS = 0;
            for (int j=i+1;j<arr.length;j++){
                if(arr[i]<arr[j]){
                    localS++;
                    flagList[j]=0;
                }
                else if(arr[i]==arr[j]){
                    flagList[j]=0;
                }
                else {
                    flagList[j]=1;
                }
            }
            if(maxS < localS){
                maxS = localS;
            }
        }
    }
    return globalS;
}

public static int surpasser(int[] arr){
    if(arr==null){
           throw new NullPointerException();
    }
    
    int flagList[arr.length];
    int maxS = 0;
    flagList[0] = 1;
    for (int i=0;i<arr.length;i++){
        if(flagList[i]){
            int localS = 0;
            for (int j=i+1;j<arr.length;j++){
                if(arr[i]<arr[j]){
                    localS++;
                    flagList[j]=0;
                }
                else if(arr[i]==arr[j]){
                    flagList[j]=0;
                }
                else {
                    flagList[j]=1;
                }
            }
            if(maxS < localS){
                maxS = localS;
            }
        }
    }
    return globalS;
}

public static int surpasser(int[] arr){
    if(arr==null){
           throw new NullPointerException();
    }
    
    int flagList[arr.length];
    int maxS = 0;
    flagList[0] = 1;
    for (int i=0;i<arr.length;i++){
        if(flagList[i]){
            int localS = 0;
            for (int j=i+1;j<arr.length;j++){
                if(arr[i]<arr[j]){
                    localS++;
                    flagList[j]=0;
                }
                else if(arr[i]==arr[j]){
                    flagList[j]=0;
                }
                else {
                    flagList[j]=1;
                }
            }
            if(maxS < localS){
                maxS = localS;
            }
        }
    }
    return globalS;
}

//defacto binary insetion
public int surpasser(int [] input){

int i = input.length -1;

TreeNode root = new TreeNode(input[i]);
int globalSurpasser =0;
while(i>=0){
int localSurpasser = 0;
boolean foundPlace = false;
while(!foundPlace){
if(input[i]<root.value){
if (root.left != null) {
root = root.left;
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
}
else {
root.left = new TreeNode(input[i]);
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
foundPlace = true;
}
}

else if(input[i]>root.value){
if (root.right != null) {
root = root.right;
}
else{
root.right = new TreeNode(input[i]);
foundPlace = true;
}
}
}

}

return globalSurpasser;

}

public int surpasser(int [] input){

int i = input.length -1;

TreeNode root = new TreeNode(input[i]);
int globalSurpasser =0;
while(i>=0){
int localSurpasser = 0;
boolean foundPlace = false;
while(!foundPlace){
if(input[i]<root.value){
if (root.left != null) {
root = root.left;
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
}
else {
root.left = new TreeNode(input[i]);
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
foundPlace = true;
}
}

else if(input[i]>root.value){
if (root.right != null) {
root = root.right;
}
else{
root.right = new TreeNode(input[i]);
foundPlace = true;
}
}
}

}

return globalSurpasser;

}

time O(nlogn)
space O(n)

Just insert from left to right of the array in a binary tree...as you traverse just count number of left turns...

public int surpasser(int [] input){
    
        int i = input.length -1;
        
       TreeNode root =   new TreeNode(input[i]);
       TreeNode rootTree = root;
      int globalSurpasser =0;
      i--;
      while(i>=0){
          int localSurpasser = 0;
          
          boolean foundPlace = false;
          while(!foundPlace){
             if(input[i]<root.value){
                 if (root.left != null) {
                     root = root.left;
                     localSurpasser++;
                     if (localSurpasser > globalSurpasser) {
                         globalSurpasser = localSurpasser;
                     }
                   }  
                 else {
                     root.left = new TreeNode(input[i]);
                     localSurpasser++;
                     if (localSurpasser > globalSurpasser) {
                         globalSurpasser = localSurpasser;
                     }
                     foundPlace = true;
                 }
                 }
                 
             else if(input[i]>root.value){                 
                   if (root.right != null) {
                       root = root.right;                      
                 } 
                   else{
                     root.right = new TreeNode(input[i]);
                     foundPlace = true;
                   }
             }
          }
        i--;  
      }
    
    return globalSurpasser;  
    
    }

My solution is O(n*logn) average and O(n^2) worst case time complexity and O(n) space: using Binary search tree where each node maintain a bit of information of number of nodes on its right, denoted as num_right

From right to left of the array: take an element a[i] to add to the tree by traverse from root, find the suitable place to add a[i], like BST insert, and do the following extra work at each node k:
- if need to go right child of k: (node k).num_right++
- if need to go left of k: surpassers[i] += (node k).num_right+1

Since each step take O(h), average is O(logn) and worst case is O(n), so in the end it is O(nlogn) avg and O(n^2) worst case

-

I think it would be simplest to sort the array: bound below by nlogn due to comparison. Then, the max surpasser is found by iterating from index 0 and subtracting by one until a new element is found: O(n). The total running time would be O(nlogn).

Time Complexity: O(n)
Space Complexity: O(n)

public class surpass {

	public static void main(String a[])   {
		int[] aa = {2,7, 5, 5, 2, 7, 0, 8, 1};
		System.out.print(maxSurpass(aa)) ;
	}
	
	public static int maxSurpass(int[] a) {
		int max = 0;
		
		Node[] surpass  = new Node[a.length]; 		
		for (int i = 0; i < a.length ; i ++) {
			if (surpass[i] == null)
				surpass[i] = new Node(a[i]);
			for ( int j = 0; j < i; j++) 
				if (surpass[j].getData() < a[i])
					surpass[j].incrementSurpass();
		}
		
		for (int j=0; j < surpass.length; j++)
			if (surpass[j].getSurpass().get() > max)
				max = surpass[j].getSurpass().get();
		 
		return max;
	}
	
}
 
class Node {
	private int data;
	private Node next;
	private Node previous;
	private AtomicInteger surpass;
	
	Node(int d){
		this.data = d;
		this.surpass = new AtomicInteger(0);
	}
	
	Node(int d, Node n) {
		this.data = d;
		this.next = n;
	}
	
	Node(int d, Node n, Node p) {
		this.data = d;
		this.next = n;
		this.previous = p;
	}
	
	public void incrementSurpass() {
		this.surpass.getAndIncrement();
	}
	
	public void decrementSurpass() {
		this.surpass.getAndDecrement();
	}
	
	public int getData() {
		return data;
	}
	public Node getNext() {
		return next;
	}
	public Node getPrevious() {
		return previous;
	}
	public AtomicInteger getSurpass() {
		return surpass;
	}
	
	public String toString() {
		return "[ Data: "+ getData() + "; surpass: " + getSurpass().get() + "]";
	}
	
}

Time Complexity: O(n)
Space Complexity: O(n)

package ds;

import java.util.concurrent.atomic.AtomicInteger;

public class surpass {

	public static void main(String a[])   {
		int[] aa = {2,7, 5, 5, 2, 7, 0, 8, 1};
		System.out.print(maxSurpass(aa)) ;
	}
	public static int maxSurpass(int[] a) {
		int max = 0;
		Node[] surpass  = new Node[a.length]; 		
		for (int i = 0; i < a.length ; i ++) {
			if (surpass[i] == null)
				surpass[i] = new Node(a[i]);
			for ( int j = 0; j < i; j++) 
				if (surpass[j].getData() < a[i])
					surpass[j].incrementSurpass();
		}
		for (int j=0; j < surpass.length; j++)
			if (surpass[j].getSurpass().get() > max)
				max = surpass[j].getSurpass().get();
		return max;
	}
}
 
class Node {
	private int data;
	private Node next;
	private AtomicInteger surpass;
	Node(int d){
		this.data = d;
		this.surpass = new AtomicInteger(0);
	}
	Node(int d, Node n) {
		this.data = d;
		this.next = n;
	}
	public void incrementSurpass() {
		this.surpass.getAndIncrement();
	}
	public int getData() {
		return data;
	}
	public Node getNext() {
		return next;
	} 
	public AtomicInteger getSurpass() {
		return surpass;
	}
	public String toString() {
		return "[ Data: "+ getData() + "; surpass: " + getSurpass().get() + "]";
	}
}

Copying an answer from SO:

Solution 1

I don't know if this is the same as Rem's solution, but you could solve this quite easily with a binary search tree.

Initialize an empty binary search tree and then iterate in reverse order through the array.

Insert each element in the binary search tree and then perform a count of all the elements in the tree above the value of the element. (If each subtree stores the number of elements it contains, then these operations can both be done in O(logn) if an appropriate balanced tree is used.)

The max number of successors is given by the largest count observed.

My solution is almost the same as hieu.pham's solution above using BST and adding # of right nodes as an additional tree node property. One additional detail is handling of equal values. A value should be inserted to the left of a node with the same value and its surpasser should be increased by numRight of the node instead of (numRIght + 1).

Here is a C++ implementation.

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
  TreeNode *left;
  TreeNode *right;
  int data;
  unsigned numRight;
  
  TreeNode(int value) : left(NULL), right(NULL), data(value), numRight(0) {}
};

class BST {
private:
  TreeNode *root;

  unsigned InsertToSubTree(int value, TreeNode *subRoot) {
    if (value <= subRoot->data) {
      auto countMe = value < subRoot->data ? 1 : 0;
      
      if (subRoot->left == NULL) {
        subRoot->left = new TreeNode(value);
        
        return (subRoot->numRight + countMe);
      }
      
      return (InsertToSubTree(value, subRoot->left) + subRoot->numRight + countMe);
    }
    else {
      subRoot->numRight++;
      if (subRoot->right == NULL) {
        subRoot->right = new TreeNode(value);
        return 0;
      }
      
      return InsertToSubTree(value, subRoot->right);
    }
  }
  
public:
  BST() : root(NULL) {}
  
  unsigned FindSurpasser(int value) {
    if (root == NULL) {
      root = new TreeNode(value);
      return 0;
    }
    
    return InsertToSubTree(value, root);   
  }
};

int main()
{
  std::vector<int> input { 2, 7, 5, 5, 2, 7, 0, 8, 1 };
  BST bTree;
  
  unsigned maxSurpasser = 0;
  
  for (unsigned i = input.size(); i-- > 0; ) {
    unsigned surPasser = bTree.FindSurpasser(input[i]);
    cout << "input " << input[i] << " surPasser " << surPasser << endl;
    maxSurpasser = max(surPasser, maxSurpasser);
  };
  
  cout << maxSurpasser << endl;
  
  return 0;
}

And no one thinks that this might not be an actual google interview question? O(n^2) is fine but anyone trying to do O(nlgn) on phone, good luck....I would urge to search web for "surpasser count"

void maxSurpasserOfArray(int iArr[SIZE])
{
	int resArr[SIZE]={0};
	int max =0;
	for(int i=0;i<9;i++)
	{
		for(int j=i+1;j<SIZE;j++)
		{
			if(iArr[i]<iArr[j])
				resArr[i] = resArr[i]+1;
		}
		if(max<resArr[i])
			max = resArr[i];
	}
	cout << "\n max surpasser is "<< max;
}

there are a data structure named Binary Indexed Tree(BIT), it can solve this problem well. ps. if the data range is so large, we can hash each different num to a continuous sequence.

Quick and easy idea:
Remember where each element was.
Sort the array (descending). For each element, see how many spaces to the right it moved in the sort.

maxVal = 0;
function insert(cNode, val, vishnu, parentNode, dir){
	if(!cNode){
		parentNode[dir] = {val: val, cnt: vishnu};
		maxVal = Math.max(maxVal, vishnu);
		return;
	}
	
	if(val <= cNode.val){
		insert(cNode.left, val, cNode.cnt + 1, cNode, 'left');
		return;
	}
	
	cNode.cnt++;
	insert(cNode.right, val, vishnu, cNode, 'right');
}

var p = {left: null};
[6,1,5,2,4,3].forEach(function(val){
	
	insert(p.left, val, 0, p, 'left');
});

console.log(maxVal);

maxVal = 0;
function insert(cNode, val, surpasser, parentNode, dir){
	if(!cNode){
		parentNode[dir] = {val: val, cnt: surpasser};
		maxVal = Math.max(maxVal, surpasser);
		return;
	}
	
	if(val <= cNode.val){
		insert(cNode.left, val, cNode.cnt + 1, cNode, 'left');
		return;
	}
	
	cNode.cnt++;
	insert(cNode.right, val, surpasser, cNode, 'right');
}


var p = {left: null};
[3,2,4,1,2,3,5].reverse().forEach(function(val){
	insert(p.left, val, 0, p, 'left');
});

console.log(maxVal);

We can solve this problem with reverse merge sort.

public static class Solution {
  
  int max;
  Map<Integer, Integer> map;
  
  int getSurpasser(int[] nums) {
    max = 0;
    map = new HashMap<Integer, Integer>();
    
    mergeSort(nums, 0, nums.length - 1);
    
    return max;
  }
  
  void mergeSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    
    int mid = lo + (hi - lo) / 2;
    
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);

    reverseMerge(a, lo, mid, hi);
  }
  
  void reverseMerge(int[] a, int lo, int mid, int hi) {
    if (lo >= hi)
      return;
    
    // make a copy of a[]
    int[] c = new int[a.length];
    System.arraycopy(a, 0, c, 0, a.length);
    
    // reverse merge
    for (int k = hi, i = mid, j = hi; k >= lo; k--) {
      if (i < lo)            a[k] = c[j--];
      else if (j < mid + 1)  a[k] = c[i--];
      else if (c[i] >= c[j]) a[k] = c[j--];
      else {
        // We need to avoid duplicates
        if (i == mid || c[i] != c[i + 1]) {
          int count = map.containsKey(c[i]) ? map.get(c[i]) : 0;
          count += j - mid;
          map.put(c[i], count);
          max = Math.max(max, count);
        }
        
        a[k] = c[i--];
      }
    }
    
  }
  
}

public static int findMaxSurpass(int[] arr)
        {
            int[] indexArr = new int[arr.Length];
            int[] surpassArr = new int[arr.Length];

            for(int i =0; i < arr.Length; i++)
            {
                indexArr[i] = i;
            }
            mergeSort(arr, 0, arr.Length - 1, indexArr, surpassArr);
            int max = 0;
            for (int i = 0; i < surpassArr.Length; i++)
            {
                if(surpassArr[i] > max)
                {
                    max = surpassArr[i];
                }
            }
            return max;
        }

        public static void mergeSort(int[] arr, int left,int right,int[] indexArr, int[] surpassArr)
        {
            if(left < right)
            {
                int mid = (left + right) / 2;
                mergeSort(arr, left, mid, indexArr, surpassArr);
                mergeSort(arr, mid + 1, right, indexArr, surpassArr);

                int i = left;
                int j = mid + 1;
                int k = left;

                int[] temp = new int[arr.Length];
                while(i <= mid && j <= right)
                {
                    if(arr[indexArr[i]] < arr[indexArr[j]])
                    {
                        surpassArr[indexArr[i]] += right - j +1;
                        temp[k++] = indexArr[i++];
                    }
                    else
                    {
                        temp[k++] = indexArr[j++];
                    }
                }

                while (i <= mid)
                {
                    temp[k++] = indexArr[i++];
                }
                while (j <= right)
                {
                    temp[k++] = indexArr[j++];
                }

                for(int l = left; l <= right;l++)
                {
                    indexArr[l] = temp[l];
                }
            }
        }

public static int findMaxSurpass(int[] arr)
{
int[] indexArr = new int[arr.Length];
int[] surpassArr = new int[arr.Length];

for(int i =0; i < arr.Length; i++)
{
indexArr[i] = i;
}
mergeSort(arr, 0, arr.Length - 1, indexArr, surpassArr);
int max = 0;
for (int i = 0; i < surpassArr.Length; i++)
{
if(surpassArr[i] > max)
{
max = surpassArr[i];
}
}
return max;
}

public static void mergeSort(int[] arr, int left,int right,int[] indexArr, int[] surpassArr)
{
if(left < right)
{
int mid = (left + right) / 2;
mergeSort(arr, left, mid, indexArr, surpassArr);
mergeSort(arr, mid + 1, right, indexArr, surpassArr);

int i = left;
int j = mid + 1;
int k = left;

int[] temp = new int[arr.Length];
while(i <= mid && j <= right)
{
if(arr[indexArr[i]] < arr[indexArr[j]])
{
surpassArr[indexArr[i]] += right - j +1;
temp[k++] = indexArr[i++];
}
else
{
temp[k++] = indexArr[j++];
}
}

while (i <= mid)
{
temp[k++] = indexArr[i++];
}
while (j <= right)
{
temp[k++] = indexArr[j++];
}

for(int l = left; l <= right;l++)
{
indexArr[l] = temp[l];
}
}
}

Start inserting elements in a BST from rightmost element of array (i.e) last element.

for each node, keep these fields,
int ans, key, num_greater
node *left, *right

num_greater will contain number of elements greater than then the node value at that instance.
for each node, keep updating num_greater, if some element goes in right subtree of that node.

when inserting each node, its ans will start from 0 at root, and ans will keep on getting updated depending on whether we go into right subtree or left subtree, till we reach a leaf and insert the key.

if we go right, ans will remain same,
if we go left, ans will increment by (node->num_greater) + (node->key > key ? 1 : 0)

when you insert your node, you will have surpasser for that key.
you can keep a maximum answer and after inserting all elements you will have your answer,

BST worst case time will be n2

you can use AVL tree for worst case time of nlogn

void sort(int *src, int *dest, int lo, int hi, int *a, int *sp) {
	if (hi <= lo) {
		return;
	}
	int mid = lo + ((hi - lo) >> 1);
	sort(dest, src, lo, mid, a, sp);
	sort(dest, src, mid + 1, hi, a, sp);

	int pos = hi;
	int i = mid, j = hi;
	while (i >= lo && j > mid) {
		if (a[src[i]] < a[src[j]]) {
			dest[pos--] = src[j--];
		}
		else {
			sp[src[i]] += hi - j;
			dest[pos--] = src[i--];
		}
	}

	while (i >= lo) {
		sp[src[i]] += hi - mid;
		dest[pos--] = src[i--];
	}
	while (j > mid)
		dest[pos--] = src[j--];
}

int maxSurpasser(int *a, int n) {
	int *index = new int[n];
	int *sp = new int[n];
	int *buf = new int[n];
	memset(sp, 0, sizeof(int) * n);
	for (int i = 0; i < n; ++i)
		index[i] = i;
	memcpy(buf, index, sizeof(int) * n);

	sort(buf, index, 0, n - 1, a, sp);

	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans = max(ans, sp[i]);

	return ans;
}

Quite long solution using tree with cached size of the right subtree for each node. Complexity: time O(n log n), space: O(n)

public int getMaxSupessor(int[] array) {
		Tree tree = new Tree();
		int maxSupessor = Integer.MIN_VALUE;
		for(int i=array.length-1; i>=0; i--) {
			tree.add(array[i]);
			maxSupessor = Math.max(maxSupessor, tree.getSupessor(array[i]));
		}
		return maxSupessor;
	}

	public class Tree {
		private Node root;

		public void add(int value) {
			if (root == null)
				root = new Node(value);
			add(value, root);
		}

		private void add(int value, Node node) {
			if (value == node.value) {
				node.count++;
				return;
			}

			if (value < node.value) {
				if (node.left == null)
					node.left = new Node(value);
				else
					add(value, node.left);
			} else {
				node.rightSize++;
				if (node.right == null)
					node.right = new Node(value);
				else
					add(value, node.right);
			}
		}

		public int getSupessor(int value) {
			return getSupessor(value, root);
		}

		private int getSupessor(int value, Node node) {
			if (node == null)
				return 0;
			if (value < node.value)
				return node.count + node.rightSize + getSupessor(value, node.left);
			if (node.value < value)
				return getSupessor(value, node.right);
			return node.rightSize;
		}
	}

	public class Node {
		public int value;
		public Node left;
		public Node right;
		public int count;
		public int rightSize;

		public Node(int value) {
			count = 1;
			rightSize = 0;
			this.value = value;
		}
	}

I create a map of potentially approritate items
value -> surpasser

we go from left to right,
if next item can be used as potential only if it is less than minimum in array of potentials.
Otherwise we increase counter of all potential which are less than item.

Best case: n
Worst case: n*n

int get_maximum_surpasser()
{
   int array_size = 0;
   int * vals= input_array( array_size );
 
   if( array_size == 0 )
   {
      return 0;
   }

   std::set<map> potential;
   int minimal_preferred = vals[0];
   potential.insert( std::pair<int,int>( minimal_preferred, 0 ) );

   for( int i = 1; i < array_size; ++i )
   {
      for( auto it = potential.begin(); it != potential.end(); ++it )
      {
         if( it->first < vals[i] )
            it->second ++;
          else
            break;
      }
      if( vals[i] < minimal_preferred )
      {
	 minimal_preferred = vals[i];
         potential.insert( std::pair<int,int>( minimal_preferred, 0 ) );
      }
   }


   int max = 0;
   for( auto it = potential.rbegin(); it != potential.rend(); ++it )
   {
       if( it->second > max )
          max = it->second();
   }
}

What do you think about this?

c# implementation.
Time: O(nlogn).
Space: O(n).

static private int GetGreatestNumberOfSurpassers( int[] arr ) {

    var initIndexes = new Dictionary<int, Queue<int>>();

    for ( int i = 0; i < arr.Length; i++ ) {
        var currElm = arr[ i ];
        if ( initIndexes.ContainsKey( currElm ) ) {
            initIndexes[ currElm ].Enqueue( i );
            continue;
        }
        var queue = new Queue<int>();
        queue.Enqueue( i );
        initIndexes[ currElm ] = queue;
    }

    Array.Sort( arr ); arr = arr.Reverse().ToArray(); // Merge Sort

    int res = 0;
    for ( int i = 0; i < arr.Length; i++ ) {
        var curr = i - initIndexes[ arr[ i ] ].Dequeue();
        if ( curr > res ) {
            res = curr;
        }
    }
    return res;
}

var countSurpasser = function(ar) {
    
    var result = [];
    
    for(var i = 0; i < ar.length; i++) {
        count = 0
        for(j = i + 1; j < ar.length; j++) {
            if(ar[j] > ar[i]) {
                count++;
            }
        }
        result.push(count);
    }
    return result;
}

Using partition approach.

Speed O (n log n)
Space O (n)

public int findMaxSurpasser(int[] a) {
        // partition from i to j. Complexity: O (log n)
        // keep track of max surpasser.
        // last element will be 0 so don't loop for that. (optimization)
        if (a.length < 2) return 0;
        int max = 0;
        for (int i = 0; i < a.length-1; i++) {
            int[] sortingA = new int[a.length-i];
            System.arraycopy(a,i,sortingA,0, sortingA.length);
            // position of the pivot
            int pos = partition(sortingA);
            // count # of elements on right of pivot
            int diff = sortingA.length - pos - 1;
            max = Math.max(max, diff);
        }
        return max;
    }

    public int partition(int[] a) {
        int pivot = a[0];
        int i = 1;
        for (int j = 1; j < a.length; j++) {
            if (a[j] <= pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i-1, 0);
        return i-1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

Using partition approach.

Time : O (n log n)
Space : O (n)

public int findMaxSurpasser(int[] a) {
        // partition from i to j. Complexity: O (log n)
        // keep track of max surpasser.
        // last element will be 0 so don't loop for that. (optimization)
        if (a.length < 2) return 0;
        int max = 0;
        for (int i = 0; i < a.length-1; i++) {
            int[] sortingA = new int[a.length-i];
            System.arraycopy(a,i,sortingA,0, sortingA.length);
            // position of the pivot
            int pos = partition(sortingA);
            // count # of elements on right of pivot
            int diff = sortingA.length - pos - 1;
            max = Math.max(max, diff);
        }
        return max;
    }

    public int partition(int[] a) {
        int pivot = a[0];
        int i = 1;
        for (int j = 1; j < a.length; j++) {
            if (a[j] <= pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i-1, 0);
        return i-1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

This is one of those things where it cannot really be simplified. O(n^2) complexity and O(1) memory:

public static int surpasser(int[] arr){
    if(arr == null){
        throw new NullPointerException();
    }
    
    int maxSurpasser = 0;
    for(int i = 0; i < arr.length; i++){
        int localSurpasser = 0;
        for(int j = i+1; j < arr.length; j++){
            if(arr[i] < arr[j]){
                localSurpasser++;
            }
        }
        if(localSurpasser > maxSurpasser){
            maxSurpasser = localSurpasser;
        }
    }
    return maxSurpasser;
}

this can be done in nlogn.
1.Store the position of each element for that we can use an object with
{
val: value
position: array_index
}

for each element in the array
2.Then sort the object array created above with value.
3.Subtract the old position from the new position for each element. i.e (old position - new position) remember don't take absolute value .
and the maximum of this is the maximum surpasser of the array