title: find if two arrays contain the same set of integers without extra space and faster than NlogN
body: <p>I came across this <a href="http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-fresher-about-algorithms-24" rel="nofollow noreferrer">post</a>, which reports the following interview question:</p>
  
  <blockquote>
    <p>Given two arrays of numbers, find if each of the two arrays have the
    same set of integers ? Suggest an algo which can run faster than NlogN
    without extra space?</p>
  </blockquote>
  
  <p>The best that I can think of is the following:</p>
  
  <ol>
  <li><p>(a) sort each array, and then (b) have two pointers moving along the two arrays and check if you find different values ... but step (a) has already NlogN complexity :(</p></li>
  <li><p>(a) scan shortest array and put values into a map, and then (b) scan second array and check if you find a value that is not in the map ... here we have linear complexity, but we I use extra space</p></li>
  </ol>
  
  <p>... so, I can't think of a solution for this question.</p>
  
  <p>Ideas?</p>
  
  <hr>
  
  <p>Thank you for all the answers. I feel many of them are right, but I decided to choose <a href="https://stackoverflow.com/questions/6691184/find-if-two-arrays-contain-the-same-set-of-integers-without-extra-space-and-faste/6693091#6693091">ruslik's one</a>, because it gives an interesting option that I did not think about.</p>