Speed up counting sort algorithm in Ruby

I'm attempting this simple HackerRank counting sort problem but testcase #3, which has 100,000 test cases, is timing out.

Is there something particularly inefficient about this code?

input = []
$stdin.each do |line|
  input << line
end
input.shift

arr = input.map { |line| line.split(' ')[0].to_i }

answer = (0..99).map do |i| 
  counter = 0
  arr.uniq.each do |j| 
    counter += arr.count(j) if j <= i
  end
  counter
end

puts answer.join ' '

arr.count(j) scans the array, so it takes linear time. Doing it once for each element of arr.uniq takes quadratic time. Doing it 100 times doesn't help either. :)

The arr.uniq.each loop is unnecessary, though (as is the call to uniq). The problem is to count the entries less than i, and you can express that directly:

counter = arr.count {|n| n <= i}

This takes linear time, so it should be much faster.

For another speedup, you can solve the whole problem with only one pass over the input, not 100. As the problem description hints, you'll need an auxiliary array to store the counts.

By the way, the first four lines can be replaced by one, using one of Ruby's convenient utilities:

input = $stdin.readlines

The whole program can be simplified to two lines.

StackExchange Code Review Q#49689, answer score: 2