# Two arrays lookup

The task is to return array with values which satisfy the condition: for each max the less or equal numbers count.

Example Input: numbers = [1, 2, 1, 4] maxes = [2, 4]. Output: [3, 4]

Explanation => 1, 2 and 1 are 3 numbers less than or equal to 2, and all 4 numbers satisfy the condition for 4.

Here is my naive approach code in C#, I have a feeling there can be an optimization, and would be thankful to see one:

    static int[] counts(int[] nums, int[] maxes)
{
int queries = maxes.Length;
int numsLength = nums.Length;
int[] counts = new int[queries];

for (int i = 0; i < queries; i++)
{
for (int j = 0; j < numsLength; j++)
{
if (nums[j] <= maxes[i])
{
++counts[i];
}
}
}

return counts;
}

• The code gives no idea what it is supposed to accomplish. You didn't state what you are trying to achieve, other than meeting the requirements stated. Jun 4, 2018 at 6:10
• Entire method can be replaced with return maxes.Select(max => nums.Count(n => n <= max)); Jun 4, 2018 at 16:03
• Are there any boundaries? Like whats the maximum number of items that nums and maxes can contain? Jul 5, 2018 at 19:36

In this case performance depends on the number of maxes. The longer the array the more time it takes to check it and the slower it gets.

As an alternative you can group all numbers first and get their counts. Then just sum the counts of the numbers that meet the criteria.

public static int[] counts2(this int[] nums, int[] maxes)
{
var counts =
nums
.GroupBy(
n => n,
(k, items) => (num: k, count: items.Count()))
.ToArray();

return
maxes
.Select(m =>
counts
.Where(x => x.num <= m)
.Sum(x => x.count))
.ToArray();
}


On my machine the results are:

Number of runs: 10000

Test-1:

nums:  1000
maxes: 10

OP vs t3chb0t

00:00:00.2005513 <  00:00:00.5321118


Test-2:

nums:  1000
maxes: 100

OP vs t3chb0t

00:00:02.3541534 >  00:00:01.7438213


Test-3:

nums:  1000
maxes: 1000

OP vs t3chb0t

00:00:22.9002408 >  00:00:12.8527922


Test-4: with AsParallel()

nums:  1000
maxes: 1000

OP vs t3chb0t

00:00:22.9081026 >  00:00:03.8906315


Chaining AsParallel() to maxes makes it run even faster.

As always with performance: test different solutions before you judge which version is the fastest one because it often depends on many other factors. Using plain loops unwisely does not have to be better the using clever linq.

I would rather see different names

int maxesLength = maxes.Length;

static int[] MaxesCounts


It is efficient enough just a little hard to follow. You could sort and do a binary search but not sure that would be any more efficient.

static int[] MaxesCounts(int[] nums, int[] maxes)
{
int[] counts = new int[maxes.Length];
foreach (int num in nums)
{
for (int m = 0; m < maxes.Length; m++)
{
if (num <= maxes[m])
{
counts[m]++;
}
}
}
return counts;
}


I'm not sure about performance but using a LINQ query will certainly simplify your algorithm:

static int[] counts(int[] nums, int[] maxes)
{
return (from int max in maxes
select nums.Count(x => x <= max)).ToArray();
}

• About performance, LINQ is pretty much always slower than the equivalent code using loops. It's also more memory intensive than iterating an array. Jun 12, 2018 at 14:53