1
$\begingroup$

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.

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

2 Answers 2

4
$\begingroup$

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]

$\endgroup$
2
  • $\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, 2018 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$ Jan 2, 2018 at 5:22
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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