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.

  • 1
    $\begingroup$ Can't you just sort the array? Am I understanding the problem wrong? $\endgroup$ – quicksort Dec 23 '17 at 15:06
  • $\begingroup$ 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. $\endgroup$ – Juho Dec 23 '17 at 16:07

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  
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]

  • $\begingroup$ 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$). $\endgroup$ – D.W. Jan 2 '18 at 2:12
  • $\begingroup$ @D.W. Quoted from the question : "Note that the elements of the array will be small up to $10^5$" $\endgroup$ – 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.


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.