Counting the elements of one array that are less than or equal to some other numbers

Question

I have a method which compares two array О(n2), maxes with each element in nums against <= condition then it prints out the new array with total count for each case, but it's too slow for large arrays, what's the most efficient way to solve this problem?

def counts(nums, maxes)
  total = 0
  total_array = []

  maxes.each do |m|
    nums.each do |n|
      if n <= m
        total += 1
      end
    end

    total_array.push(total)

    total = 0
  end

  total_array
end

nums = [2,10,5,4,8]
maxes = [3,1,7,8]

print counts(nums, maxes) => # [1,0,3,4]

# Explanation:

# 1. maxes[0] >= nums[0]
# 2. maxes[1] >= 0
# 3. maxes[2] >= nums[0], nums[2], nums[3]
# 4. maxes[3] >= nums[0], nums[2], nums[3], nums[4]

Answer 1

For your current code, the more Ruby-esque and functional way to write it would be:

def counts(numbers, maxima)
  maxima.map do |max|
    numbers.count { |n| n <= max }
  end
end

Don't mess around with "manual" counting and array-appending when you don't have to.

As for general improvements:

Sort the numbers. If you sort them, you won't have to loop through the whole array, you just have to count up to the first case where the comparison returns false. Or you can use Array#bsearch_index to find the "split point" in \$O(\log n)\$ time. Better yet, invert the condition and the index you find is also the count you want:

def counts(numbers, maxima)
  sorted = numbers.sort
  maxima.map do |max|
    index = sorted.bsearch_index { |n| n > max } # note inverted condition
    index || sorted.size
  end
end

The above works because it's using #bsearch_index in its "find minimum" mode (i.e. find the first index for which the block returns true), but since the condition is flipped it'll find the first number that shouldn't be counted. And that number's index equals the count of the elements before it. E.g. using your example input, what happens is:

• The numbers get sorted [2, 10, 5, 4, 8] => [1, 4, 5, 8, 10]
• For a given maximum, we do a binary search for the index
• If the maximum is, say, 7, we'll find index 3 (value 8), since that's the first place where n > max (i.e. 8 > 7).
• And since indices are zero-based, 3 is also the total/count we want.

You can also sort the maxima array from high to low. Start with the highest maximum, and filter the numbers array to only include those that fit the n <= max condition. The length of the filtered array is the first count. To find the next count, we only need to find a subset of the filtered array because a lower maximum will always result in a smaller array and a lower count. And so on for the next, smaller, maximum. It's a bit trickier, since you still need to output the totals in the original (unsorted) order.

def counts(numbers, maxima)
  # create an array of [value, index] tuples, sorted (descending) by value
  pairs = maxima.each_with_index.sort_by(&:first).reverse

  result = pairs.each_with_object({numbers: numbers, counts: []}) do |(max, index), memo|
    memo[:numbers].select! { |n| n <= max } # note in-place modification
    memo[:counts] << [memo[:numbers].size, index]
  end

  # re-sort the counts so they match the original order
  result[:counts].sort_by(&:last).map(&:first)
end

which could also be written as:

def counts(numbers, maxima)
  pairs = maxima.each_with_index.sort_by(&:first).reverse

  # create a copy, since we'll be modifying it
  search_space = numbers.dup

  counts = pairs.map do |max, index|
    search_space.select! { |n| n <= max } # note in-place modification
    [search_space.size, index]
  end

  counts.sort_by(&:last).map(&:first)
end

Or you can do everything: Sort both numbers and maxima, and use bsearch_index to figure out where to split the numbers array instead of select!. However, all that sorting and extra busywork might end up being slow.

def counts(numbers, maxima)
  pairs = maxima.each_with_index.sort_by(&:first).reverse
  search_space = numbers.sort

  result = pairs.each_with_object({search_space: search_space, counts: []}) do |(max, index), memo|
    count = memo[:search_space].bsearch_index { |n| n > max }
    count ||= memo[:search_space].size
    memo[:search_space].slice!(0, count)
    memo[:counts] << [count, index]
  end

  result[:counts].sort_by(&:last).map(&:first)
end

And of course, you can memoize the total for a given maximum, so if you encounter the same maximum twice or more, you can just recall a known count without re-searching an array.

Answer 2

How about a \$O(n\log(n)+m\log(m))\$ time solution?

\$n\log(n)\$ and \$m\log(m)\$ are for sorting (I'm assuming Ruby uses \$O(n\log(n))\$ sort).

Then there's one iteration over numbers in \$\Theta(n)\$ time and one iteration over maxes in \$\Theta(m)\$ time.

def counts(nums, maxes)
  nums = nums.sort
  # `maxes_idxs` is array of pairs [value, index], sorted by value
  maxes_idxs = maxes.zip(0...maxes.size).sort
  res = maxes.clone

  i = 0

  # For all maxes...
  maxes_idxs.each do |max, maxidx|

    # find the next number greater than this max.
    while nums[i] <= max and i < nums.length
      i += 1
    end

    # This max has `i` numbers less than itself. Write it to the array
    # with results, at the original position of this max (before sorting).
    res[maxidx] = i
  end

  res
end

I haven't tested the performance, so I don't know if it's actually faster, but I'm quite convinced it is.