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

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: