Compare two integer arrays with same length
algorithm, arrays
Solution
(Probably too complex for an interview question.)
(You can use O(N) time to check the min, max, sum, sumsq, etc. are equal first.)
Use no-extra-space radix sort to sort the two arrays in-place. O(N) time complexity, O(1) space.
Then compare them using the usual algorithm. O(N) time complexity, O(1) space.
(Provided (max − min) of the arrays is of O(Nk) with a finite k.)
Problem
[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. ``` [Example] <1 2 3 4> = <3 1 2 4> <1 2 3 4> != <3 4 1 1> ``` [Limitation] The algorithm should require constant extra space, and O(n) running time.