<p>(Probably too complex for an interview question.)</p>

<p>(You can use O(N) time to check the min, max, sum, sumsq, etc. are equal first.)</p>

<p>Use <a href="http://arxiv.org/abs/0706.4107" rel="nofollow noreferrer">no-extra-space radix sort</a> to sort the two arrays in-place. O(N) time complexity, O(1) space.</p>

<p>Then compare them using the usual algorithm. O(N) time complexity, O(1) space.</p>

<p>(Provided (max &minus; min) of the arrays is of O(N<sup>k</sup>) with a finite k.)</p>
Compare two integer arrays with same length
<p>[Description] Given two integer arrays with the same length. Design an algorithm which can judge whether they're the same.  The definition of "same" is that, if these two arrays were in sorted order, the elements in corresponding position should be the same.</p>

<pre><code>[Example]
&lt;1 2 3 4&gt;  = &lt;3 1 2 4&gt;
&lt;1 2 3 4&gt; != &lt;3 4 1 1&gt;
</code></pre>

<p>[Limitation] The algorithm should require constant extra space, and O(n) running time.</p>