Task — Count smaller

You are given an array of integers. Write a script to calculate the number of integers smaller than the integer at each index.

Examples

Example 1
Input: @int = (8, 1, 2, 2, 3)
Output: (4, 0, 1, 1, 3)

For index = 0, count of elements less 8 is 4.
For index = 1, count of elements less 1 is 0.
For index = 2, count of elements less 2 is 1.
For index = 3, count of elements less 2 is 1.
For index = 4, count of elements less 3 is 3.

Example 2
Input: @int = (6, 5, 4, 8)
Output: (2, 1, 0, 3)

Example 3
Input: @int = (2, 2, 2)
Output: (0, 0, 0)

Analysis

This is not a difficult task to solve, but as always I looked for a scalable solution that will work with a much larger set of numbers than those in the examples.

So my solution does a single pass through @ints to produce %less_than, where $less_than{$i} is the count of elements less than $i. This requires an initial sort of @ints but as I have noted in the past, Perl sorts fast.

Having done that the answer is simply:

$result .= $less_than{$_} . ', ' for @ints;

This runs in milliseconds even if there are 10000 elements in @ints.

Try it 

Try running the script with any input:

Your @ints =

example: 0, 6, 5, 4, 8

⤡

#!/usr/bin/perl

use v5.26;    # The Weekly Challenge - 2023-11-20
use utf8;     # Week 244 task 1 - Count smaller
use strict;   # Peter Campbell Smith
use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

count_smaller(8, 1, 2, 2, 3);
count_smaller(0, 6, 5, 4, 8);

my @nums;
$nums[$_] = int(rand(100)) + 1 for 0 .. 99;
count_smaller(@nums);

sub count_smaller {
    
    my (@ints, @sorted, $i, $old_i, $count, %less_than, $result);
    
    # initialise
    @ints = @_;
    @sorted = sort {$a <=> $b} @ints;
    $count = 0;
    $old_i = -1;
    
    # create $less_than[$i] = number of $ints[$i] less than $i
    for $i (@sorted) {
        $less_than{$i} = $count if $i > $old_i;
        $count ++;
        $old_i = $i;
    }
    
    # format and output
    $result .= $less_than{$_} . ', ' for @ints;
    $result =~ s|..$||;
    
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    say qq[Output:         ($result)];
}

Output

Input:  @ints = (8, 1, 2, 2, 3)
Output:         (4, 0, 1, 1, 3)

Input:  @ints = (0, 6, 5, 4, 8)
Output:         (0, 3, 2, 1, 4)

Input:  @ints = (33, 33, 35, 84, 89, 43, 25, 46, 99, 54, 93, 59, 84, 89, 74, 41, 76, 18, 66, 43, 64, 38, 81, 88, 81, 45, 23, 46, 2, 14, 32, 31, 49, 45, 53, 82, 11, 4, 40, 15, 95, 77, 50, 82, 4, 29, 45, 77, 57, 96, 48, 2, 63, 72, 11, 94, 40, 85, 64, 15, 7, 27, 48, 84, 59, 35, 30, 52, 20, 82, 100, 42, 45, 55, 50, 93, 50, 23, 31, 3, 40, 100, 74, 58, 20, 55, 60, 1, 50, 91, 23, 9, 50, 77, 24, 69, 78, 67, 9, 42)
Output:         (28, 28, 30, 84, 89, 39, 21, 45, 97, 57, 92, 62, 84, 89, 72, 36, 74, 14, 68, 39, 66, 32, 79, 88, 79, 41, 17, 45, 1, 11, 27, 25, 49, 41, 56, 81, 9, 4, 33, 12, 95, 75, 50, 81, 4, 23, 41, 75, 60, 96, 47, 1, 65, 71, 9, 94, 33, 87, 66, 12, 6, 22, 47, 84, 62, 30, 24, 55, 15, 81, 98, 37, 41, 58, 50, 92, 50, 17, 25, 3, 33, 98, 72, 61, 15, 58, 64, 0, 50, 91, 17, 7, 50, 75, 20, 70, 78, 69, 7, 37)