go_rob's blog

Help — Total number of unique integers in given n ranges
By go_rob, history, 8 years ago, In English

We are given n ranges `(L1,R1) , (L2,R2) , ... .. (Ln,Rn)'
All ranges are integer values between (0 to 10^6). We have to find out the total number of unique integers across all the ranges?

Ex. For n = 3, (1,4) , (2,3) , (4,5) the answer is 5.

My solution is to sort the ranges according to their L value and then iterate one by one using two pointers. Time Complexity O(n*Log(n)).

Is there any better solution than this(may be using Hash Maps)?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

Since you said that the ranges are from 0 to 10^6, then you can use the +1, -1 trick. The trick is as follows: First maintain an array of size 10^6+2, then, for each query L,R, you do this: {ar[L]++; ar[R+1]--;}, now after answering all queries, find the prefix sum array of ar till index = max of all R values, the no. of non-zero entries in this prefix sum array is your answer. The complexity is O(n+Q) where n<=10^6 and Q is the total no. of queries.

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

    This won't be correct. Consider 2 ranges (2,7) and (4,8). Here that method would count elements 3-7 twice and we only need to count each number once.

    EDIT : This comment was made before the revision of the parent comment. Please ignore this comment.

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

      No bro, it seems like you misunderstood my soln., you need to find the no. of non-zero elements in the prefix sum array, not the prefix sum itself. So each element gets counted only once, if and only if it is non-zero.

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

        I agree. My comment was made before you revised your answer to include that you only count the number of non zero elements and not their actual values.

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

          I NEVER mentioned to take the prefix sum itself as the answer. You can go check my revision history :)

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

            I know. I misunderstood your solution. My mistake. (Hence the +1 for your answers)

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

              Here is +1 for accepting ur mistake :). Happy Coding!

              → Reply