passworld's blog

how to count the "smaller number" in an array
By passworld, 10 years ago, In English

I want to count for every number ,say A[i] ,how many numbers there are that is smaller than Ai with id smaller than i. For example , here is an array: 5 3 7 2 9 6 ,the anwser is 0 0 2 0 4 3 Is there any fast algorithm that can solve this problem? Thank you for your help!

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Use Fenwick Tree, add 1 to tree[A[i] and ask for sum on tree[0...A[i] - 1]

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If constraints are too big (A[i] <= 10^9) you can use segment tree with zipping vertexes; It means you will create vertex only when you will need it;

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

the problem can be solved with O(nlogn) complexity using segment tree:

Consider the array b[] where b[i] denotes the number of elements of A that are <=i

Traverse the array A[] from left to right, editing the array b[] on your way by adding 1 on the interval from A[i] to Max number in A[]. The answer for ith number is b[A[i]-1]

please correct me if I am wrong.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    And changing limit for A[i] does not make much difference for this solution. You just have to compress all input numbers — say that smallest of them is equal to 1, second smallest is equal to 2 and so an. There will be no more than N different values in array of size N, so you'll end up with array of numbers <=N, even if original numbers were up to 1e18.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You are right, fixed, thanks.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it -8 Vote: I do not like it

      Can this sequence "canonicalization" be done faster than sorting and then assigning? I've always used this method when I needed to, and I'm almost sure there is no better method (mainly because you need to know ordinal position for every number), but now I'm thinking about this.

      By "sorting" I include any variant which implies the use of a set/heap or similar things.

      edit: Sometimes I fail to understand why posts get downvoted :|

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        If you're able to get the position of each element in O(f(n)), then you can sort array in O(f(n) + n), but that's impossible if you use only comparison and f(n) ~< nlogn

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What you're asking is similar to counting the number of inversions, though the comparison is the other way around. It can be solved with BIT / Segment Tree, like others have said, and also with a modified Merge Sort algorithm.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If i didnt get the question wrong it can be solved with a monotonic queue with O(n) time complexity.

EDT: Yes i did get it wrong. Sorry.

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The problem can be solved without compressing the numbers.
Put Fi = 0 for all i <  = N
Sort the pairs Pi = (Ai, i).
Then go from left to right, calculate the answer for Pi.second, which is (F1 + ... + FPi.second - 1). Do this with segment tree.
Then put FPi.second = 1

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If there are repeated numbers in the array and you do it that way, you'd need to process the numbers in groups.

    → Reply