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

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

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: