Absolut's blog

How to solve "most frequent" query?
By Absolut, history, 8 years ago, In English

How to solve the following problem? Given an array A of size N and M queries to solve. Each element in the array is less or equal than the size of the array.

N < 50000, M < 500000

Each query consist in two numbers l and r. We must answer what is the most frequent value (the one who appears more times) in the subarray A[l], A[l+1], ... , A[r-1], A[r]. If there are many posibilities answer the smallest.

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

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I think it can be solved offline using the Mo's Algorithm.

Some references:

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

Can be solved offline.

Say bucket size = sqrt(n). Keep a list of queries for each bucket.

Now, for a query(left, right) place this query in list of left's bucket(left / bucket_size).

We can solve queries in some bucket like this now :

1.Sort all queries by right.

2.Now, you can split a query (left, right) in 2 : (left, start position of next bucket) and (start position of next bucket + 1, right)

The first case, can be done in sqrt(n) brute, in each query.

For the second case, we keep a pointer that equals at start of bucket to start_pos_of_next_bucket + 1, and now we can just move it to right each query. You can move it at most N steps, so this case takes O(n) in total for each bucket.

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

    How do you get the most frequent value in each query? with some data structure which implies a log(N) aditional complexity? So the total complexity would be N*sqrt(N)*log(N)

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

      Data structures not required.

      Keep some value Best1, at start of block, it means most frequent element for case 2(the one with the pointer).

      When you process a query now:

      Use another value Best2 that equals Best1 at start of this query, it means most frequent for this query(you have to add case 1)

      Now, move pointer to right of this query, and update Best1, Best2. Then, do brute sqrt(n) steps for case1, and only update Best2. (Do it in this order)

      After, answer for this query is Best2, and you have to remove those sqrt(n) values(you increased their frequence).

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

Hi. Can you, please, share the problem's link?

Thanks!

→ Reply
»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

i think it is a very common segment tree problem.you can search it in google and solve many problems like it easily.

→ Reply