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.

Pages: 1 2

8 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)))

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: