Multi Query: Check if two subarrays have the same distinct elements

I’m trying to solve a question where I am given an array of n integers [a_1,\ldots,a_n], 1\le a_i\le n and multiple queries of the form i, j, k, l.
Each query wants the answer to the question:
Is the set of distinct elements in the subarray [a_i, \ldots, a_j] equal to the set of elements in [a_k,\ldots,a_l]

I want each query to be answered fast, in something like O(\log n), O(\log^2 n).

I have been trying a lot of different techniques, including segment trees, polynomial hashing but none of them are working for me.

Can anyone see a solution to this problem? The problem is the Subarray Set problem from here

EDIT: So I managed to get a solution using square root decomposition and hashing which answers each query in O(\sqrt{n}).
But I am still curious if this can be done faster…

what was wrong with polynomial hashing?

Where is the Problem?? Can you share the link??

It can’t be done using standard polynomial hashing as duplicates of a node would change the hash

E.g. for an array [1,2,1,3,1,2,3] and i, j, k, l = 0, 3, 4, 6 we would have the two subarrays
[1, 2, 1, 3] and [1,2,3] which both have the same set \{1, 2, 3\}

I don’t see why is that a problem, can you share the statement so I can try?

Subarray Set problem from this contest

I added the problem link in the original post

That’s not a contest, that’s a question that was created by yourself on hackerrank! Please share the link to the original source where you found the question.

1 Like

Yes, I know.
Because there is no original contest link.
I came up with this problem while discussing at university last week.
I created the problem on hackerrank to illustrate the problem.

You could simply google search “How to find distinct elements in a subarray”.


By this you can calculate all the queries in O((N+Q)*logn)

Ah, fair, I didn’t think about offline algorithms!

Thanks for the link!