# Count numbers less than $K$ in array

Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and answer queries for different $K$ fast. Note that the elements of the array will be small up to $10^5$, so it will be possible to count how many times each elements appears.

For example, let $A = \{1, 2, 3,0,0,2\}, K =3$ the answer is $5$, because all $\{1,2,0,0,2\}$ are less than $3$.

I know that we can implement this with segment tree and than answer queries in $O(\log N)$, but I was thinking that we can implement easier solution that is easier to code.

• Can't you just sort the array? Am I understanding the problem wrong? – quicksort Dec 23 '17 at 15:06
• What's the problem with doing what you suggest, i.e., just compute the counts for each possible $K$ as a preprocessing step? This is surely easy, and maybe more efficient than you expect. – Juho Dec 23 '17 at 16:07

## 2 Answers

Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode

count = new int[C] (array of integers)
for every a[i] in a
count[a[i]]++
for i = 1, i < C, i++
count[i] += count[i-1]


To Answer a query for a given k you just return count[k - 1]

• That's not $O(n)$ preprocessing; it's $O(\max(n,C))$, which might be much slower if the array contains a large number (much larger than $n$). – D.W. Jan 2 '18 at 2:12
• @D.W. Quoted from the question : "Note that the elements of the array will be small up to $10^5$" – User Not Found Jan 2 '18 at 5:22

As mentioned in comments, you can sort the array as a pre-process. Then answer to the query in $O(\log(n))$ using binary search. The implementation is common and easier.