How can we calculate, for every element in an array, the number of elements to the right that are greater than that element?

Given an array A with n values, let X of A be an array that holds in index i the number of elements which are bigger than A[i] and are to its right side in the original array A.

For example, if A was: [10,12,8,17,3,24,19], then X(A) is: [4,3,3,2,2,0,0]

How can I solve this in O(n log(n)) Time and O(n) Space complexity?

I can solve this easily in O(n^2) Time and O(1) Space by using a loop and, for every element, counting how many elements are bigger than it on the right side, but I wasn’t successful with those requirements.

I was thinking about using quick sort with can be done in O(n log(n)) at worst, but I don’t see how the sorted array could help here.

Note: Regarding quick sort the algorithm needs some tweak to insure O(n log(n)) at worst and not only on average.

Answer

Quick summary of the problem statement: Given an array A which contains N integers, construct an array X such that for every i, X[i] = the number of elements in A that have an index greater than i and are also greater than A[i].

One way to solve this problem would be to use a binary search tree. Start by iterating from the last to the first element, adding each element to the set as we iterate. Every time we are at an element e, use the binary search tree’s find() operation to find how many elements are greater than e in the current tree.

Perhaps your first thought would be to use a std::multiset (not std::set because we may have duplicate elements!), which is a self-balancing binary search tree that offers O(logN) insertion and O(logN) element finding. This seems like it would work for this algorithm, but it actually wouldn’t. The reason is because when you call std::multiset::find(), it returns an iterator to the element in the set. Finding how many elements in the set are actually greater than the element would take O(N) time, as to find the distance from the iterator to the end of the set would require incrementing it repeatedly.

To solve this problem, we use an “indexed multiset”, which is a slightly modified binary search tree such that we can find the index of an element in the multiset in O(logN) time while still supporting O(logN) insertion. Here’s my code demonstrating this data structure:

#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// I know this is kind of messy, but it's the general way to get a C++ indexed
// multiset without using an external library
typedef tree <int, null_type, less_equal <int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

int main()
{
    int A_size;
    cin >> A_size;

    vector <int> A(A_size);
    for(int i = 0; i < A_size; ++i){
        cin >> A[i];
    }
    // Input Done

    indexed_set nums;
    vector <int> X(A_size);
    for(int i = A_size - 1; i >= 0; --i){
        // order_of_key returns the first index that A[i] would be at in a sorted list
        // with the same elements as nums.
        X[i] = nums.size() - nums.order_of_key(A[i]);

        nums.insert(A[i]);
    }

    for(int item : X){
        cout << item << " ";
    }
    cout << "n";

    return 0;
}

So, overall, the general strategy would be to

  1. Iterate from the last element to the first element.
  2. For every element, check in nums to see how many elements are greater than the current element. (O(logN))
  3. Then, insert the current element and continue to iterate. (O(logN)) Clearly, the total time complexity of this algorithm is O(NlogN) and the space complexity is O(N).

A quick summary of the observations and insights of this method:

  1. INSIGHT: If we iterate from the last to the first element (not the first to the last), the indexed-set will only contain elements to the right of the current element at any given iteration, which is exactly what we want. This saves us time because we don’t need to worry about inserting all the elements at the beginning then removing them one by one if we were to iterate from left to right.

  2. OBSERVATION: A std::set wouldn’t suffice for the binary search tree in this algorithm because although it provides O(logN) finding an element, calculating the elements position in the set requires a worst case of O(N) time. An indexed-set, however, provides this “position-finding” operation in O(logN) time, as well as insertion.

Leave a Reply

Your email address will not be published. Required fields are marked *