I'm stuck with comparing two lists and finding how many elements are <= list1 (list2 <= list1) and putting the result in a new_list.

Here are the test cases:

Test Case 1:

list1 = [1, 4, 2, 4]
list2 = [3, 5]
Output: [2, 4]

Explanation:

1. For list2[0] = 3, we have 2 elements in list1 (list1[0] = 1 and list1[2] = 2) that are <= list2[0].

2. For list2[1] = 5, we have 4 elements in list1 (list1[0] = 1, list1[1] = 4, list1[2] = 2, and list1[3] = 4) that are <= list2[1]

Test Case 2:

list1 = [1, 2, 3]
list2 = [2, 4]
Output: [2, 3]

Explanation:

1. For list2[0] = 2, we have 2 elements in list1 (list1[0] = 1 and list1[1] = 2) that are <= list2[0].

2. For list2[1] = 4, we have 3 elements in list1 (list1[0] = 1, list1[1] = 2, list1[2] = 3) that are <= list2[1]

I was thinking to solve with two pointers where I place the first pointer in list1[0] and 2nd pointer in list2[0] then compare each element in both lists and increment a count each time I see an element in list2 is smaller than elements in list1. The implementation is a little challenging to me and I'm sure whether it's working or not.

Here what I wrote:

def counts(list1, list2):
   new_list = []
   count = 0
   a = list1[0]
   b = list2[0]
   i, j = 1, 1

   while a or b:
     if a <= b:
        count  = 1
        new_list.append(a[i])
        i  = 1

   return new_list

CodePudding user response：

You can use Python sum on boolean to get the number of items that match, e.g.

[sum(l1x <= l2x for l1x in list1) for l2x in list2]

If you need efficiency¹, you can switch to a numpy based solution, such as

np.sum(np.asarray(list1)[:, None] <= [list2], axis=0)

If you want the version without list comprehension or without sum:

res = []
for l2x in list2:
    cnt = 0
    for l1x in list1:
        cnt  = l1x <= l2x
    res.append(cnt)

_{¹ Disclaimer: I did not test the actual efficiency.}

CodePudding user response：

The easiest way is:

import numpy as np
[(np.array(list1)<=l2).sum() for l2 in list2]

But if you need a more efficient solution, just let me know

CodePudding user response：

You could sort both the input lists. Then binary search(bisect.bisect_right from std lib) to get the insertion position of values in list2 in list1. The position would eventually tell you how many values are less than the value of the items in list2.

from bisect import bisect_right # For binary search.

srt_l1 = sorted(list1) # NlogN
srt_l2 = sorted(list2) # MlogM

out = [bisect_right(srt_l1, val) for val in srt_l2] # MlogN

This brings the time complexity to O(NlogN MlogM) with extra space of N M(though you could sort in-place using list.sort). The suggested answers above have a time complexity of O(N*M).