Bigger To The Right
March 9, 2021
Given a list of integers, calculate a list of integers that contains, at each item of the list, the count of integers in the original list that are greater than the item at the current position of the original list. For example, given the input list (10 12 8 17 3 24 19), the desired output is (4 3 3 2 2 0 0), because at the first item in list, 10, there are four items (12 17 24 19) greater than 10, at the second item in the list, 12, there are three items (17 24 19) greater than 12, at the third item in the list, 8, there are three items (17 24 19) greater than 8, at the fourth item in the list, 17, there are two items (24 19) greater than 17, at the fifth item in the list, 3, there are two items (24 19) greater than 3, at the sixth item in the list, 24, there are 0 items () greater than 24, and at the seventh item in the list, 19, there are 0 items greater than 19.
Your task is to write a program to calculate the list of counts of greater than the current item; is there an O(n) solution? When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
use feature qw(say); say join q( ), max_other( qw(10 12 8 17 0 3 24 19) ); sub max_other { map { $a = shift @_; scalar grep { $_>$a } @_ } @_; }The counts are the number of elements to skip over when doing a (descending) insertion sort from the right. The tree solution is nice – basically this is “tree sort”: https://en.wikipedia.org/wiki/Tree_sort
A solution in Racket:
(define (big-right in) (reverse (cadr (foldl (λ (val init) (list (cdar init) (cons (length (filter (λ (x) (> x val)) (car init))) (cadr init)))) (list in null) in))))Examples:
import java.util.concurrent.atomic.*;
AtomicInteger index = new AtomicInteger();
Arrays.stream(array)
.map(x -> (int)Arrays.stream(array)
.skip(index.incrementAndGet())
.filter(y -> y > x)
.count())
.toArray();
code in c++
#include
using namespace std;
int main()
{
int sum = 0;
int a[6] = { 10, 12, 4, 17, 29, 8 };
int b[6];
for (int i = 0; i < 6; i++)
{
sum = 0;
for (int j = 0; j < 6; j++)
{
if (a[j] > a[i])
sum = sum + 1;
}
b[i] = sum;
}
for (int i = 0; i < 6; i++)
{
cout << b[i] << endl;
}
}
Interesting exercise! I applied iteration on the result, using it as input to compute its “Bigger to the Right”. Interestingly, it is possible to find lists of length n that leads to n lists before getting to [0, 0, …, 0]. Here is an example with a list of 10 elements:
[19, 32, 15, 44, 31, 42, 20, 48, 23, 39]
[8, 4, 7, 1, 3, 1, 3, 0, 1, 0]
[0, 1, 0, 2, 0, 1, 0, 1, 0, 0]
[4, 1, 3, 0, 2, 0, 1, 0, 0, 0]
[0, 2, 0, 2, 0, 1, 0, 0, 0, 0]
[3, 0, 2, 0, 1, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[2, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
I have not been able to find the pattern of the initial list to get 10 iterations. Any idea?
a couple of solutions in Racket.
;;; This solution was written in Common Lisp.
(defun calculate-bigger-to-the-right (a)
(map ‘list (lambda (y)
(let ((counter 0) (a y))
(map nil (lambda (x)
(when (> x (car y)) (incf counter))) a) counter))
(mapcon ‘list a)))
A solution in C++:
#include <iterator> #include <numeric> #include <vector> std::vector<int> bigger_to_the_right(const std::vector<int>& vec) { std::vector<int> retval; for (auto iter = vec.begin(); iter != vec.end(); iter = std::next(iter)) { retval.push_back(std::accumulate(std::next(iter), vec.end(), 0u, [&iter](size_t a, int b){ return a + (b > *iter); })); } return retval; }