## Bigger To The Right

### March 9, 2021

The obvious solution is to count at each item in the list, which takes times O(n²):

```(define (f1 xs)
(define (gt? x) (lambda (y) (< x y)))
(let loop ((xs xs) (zs (list)))
(if (null? xs) (reverse zs)
(loop (cdr xs) (cons (length (filter (gt? (car xs)) (cdr xs))) zs)))))```

An O(n log n solution is available using some sort of balanced binary tree. Working right to left, we insert each item in the tree, then output for each item the current count of items processed less the rank of the current item in the tree:

```  (let loop ((xs (reverse xs)) (zs (list)) (t (make-avl <)))
(if (null? xs) zs
(let* ((t (t 'insert (car xs) (car xs)))
(z (- (length zs) (t 'rank (car xs)))))
(loop (cdr xs) (cons z zs) t)))))```

Both solutions output the desired (4 3 3 2 2 0 0).

There is no O(n) solution, for exactly the same reason that the best comparison-base sorting algorithms take time O(n log n). And I can’t think of any way to adapt radix sorting to this problem.

You can see all of the code assembled at https://ideone.com/CoCl4p, though it doesn’t run. The Chicken Scheme interpreter at ideone is very old, and sometimes doesn’t work. I assure you the code works on Chez Scheme on my system.

Pages: 1 2

### 9 Responses to “Bigger To The Right”

1. James Curtis-Smith said
```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 } @_ } @_;
}
```
2. matthew said

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

3. Kevin said

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:

```> (big-right '(10 12 8 17 3 24 19))
'(4 3 3 2 2 0 0)
> (big-right '(7 6 5 4 3 2 1))
'(0 0 0 0 0 0 0)
> (big-right '(1 2 3 4 5 6 7))
'(6 5 4 3 2 1 0)
> (big-right '(4 0 4 0 4 0))
'(0 2 0 1 0 0)
> (big-right '())
'()
```
4. vinoth said

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();

5. faisi said

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;
}
}

6. Stephane Quenson said

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?

7. r. clayton said

a couple of solutions in Racket.

8. Luis Leonel said

;;; 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;
}
```