I came across an algorithmic problem. I do not know how to do it optimally.

The problem is as follows:

  1. There is an increasing array $A$ of size $n_1$

  2. There is an array $M$ of queries of size $n_2$

    where $1 \le n_1, n_2 \le 10^7$

For each query element $m \in M$, it is required to find the count of elements in array $A$ that are strictly less than the query element $m$.
For example:

$A = [1,2,3,5]$
$M = [4,2]$
for $m = 4$ answer $3$
for $m = 2$ answer $1$

My idea works for a $O(nlogn)$. The algorithm is simple; for each request I do a binary search in array $A$. But can it be faster? Maybe B-tree?

  • 1
    $\begingroup$ Can you credit the original source where you encountered this task? $\endgroup$
    – D.W.
    Apr 5 at 7:45
  • $\begingroup$ @D.W. Сlosed group on codeforce from the university $\endgroup$
    – southpaw
    Apr 5 at 7:49
  • $\begingroup$ Your hypothesis states that $A$ and $M$ are the same size $n$, but that is not the case in your example. Which is it? Also, are there hypotheses about the values in $A$? (if they are positives integers, there is an algorithm in $O(n+\max(A))$.) $\endgroup$
    – Nathaniel
    Apr 5 at 8:50
  • $\begingroup$ @Nathaniel Sizes may be different, but within certain limits, I wrote inattentively, sorry. All values in both arrays are within $[1, 10^7]$ and are integers $\endgroup$
    – southpaw
    Apr 5 at 9:10
  • $\begingroup$ @Nathaniel There is also an idea to try to somehow minimize the number of read cache lines per request $\endgroup$
    – southpaw
    Apr 5 at 9:18

If values in both arrays are positive integers, there is an algorithm in $O(n_1 + n_2 + \max(A))$. This algorithm is interesting if those three values are of the same order of magnitude.

The steps are as follow:

  • check last element of $A$ to know $\max(A)$;
  • create an array $B$ of size $\max(A)$;
  • browse $A$ and modify $B$ so that $B[i]$ represents the smallest index $j$ such that $A[j] \geq i$ (that means the number of elements of $A$ that are $<i$);
  • browse $M$; for $m \in M$, if $m > \max(A)$, return $n_1$, else return $B[m]$.
  • $\begingroup$ Wow, great solution, thanks a lot! $\endgroup$
    – southpaw
    Apr 5 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.