Determine if two unsorted arrays are identical? <p>Given two <strong>unsorted</strong> arrays <code>A</code> and <code>B</code> with distinct elements, determine if <code>A</code> and <code>B</code> can be rearranged so that they are identical. </p> <p>My strategy was as follows: </p> <ol> <li>First, use a deterministic selection algorithm of <strong>O(N)</strong> time to find the <strong>Max</strong> of <code>A</code> and <strong>Max</strong> of <code>B</code>, if they don't have the same <strong>Max</strong>, we can automatically declare that they are <strong>not</strong> identical, otherwise, move to step 2.</li> <li>Merge the two arrays together and create an array <code>C</code> of size <strong>2N</strong>.</li> <li>Use the <em>counting sort algorithm</em> by creating an array <code>D</code> of size <strong>Max(A)</strong> and scanning <code>C</code> and bumping the counters of the appropriate index in <code>D</code> <em>(we don't actually need to complete the counting sort algorithm, we just need this intermediate step)</em>.</li> <li>Scan the <code>D</code> array, if any <code>D[i] = 1</code>, we know that the arrays are not identical, otherwise they are identical.</li> </ol> <p><strong>Claim:</strong> Time Complexity O(N), and <strong>no</strong> constraints on space.</p> <p>Is this a correct algorithm ?</p>