Can element uniqueness be solved in deterministic linear time?
You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y.  This does not impose any restrictions of the ordering of X and Y.


Initially all bits are unset. 
Iterate over X setting the corresponding bit.
Iterate over Y checking if the corresponding bit was set above.