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

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]


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.

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.