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_arrayendnums = [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]
Counting the elements of one array that are less than or equal to some other numbers
algorithm;ruby;array;time limit exceeded
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 }  endendDon'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  endendThe 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 indexIf 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)endwhich 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)endOr 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)endAnd 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.