@frankz306 said in Why is first more efficient than other methods? (Java 4ms solution):

If the n is large enough, say 1e6 and numbers are shuffled randomly, I believe this solution would be **5x slower** than O(n) solutions, on average.

According to my below test, it's **faster** by factor 4 (than the top-voted solution, which is O(n)):

```
O(n log n): 93 O(n): 321
O(n log n): 82 O(n): 265
O(n log n): 70 O(n): 295
O(n log n): 63 O(n): 263
O(n log n): 69 O(n): 267
O(n log n): 71 O(n): 274
O(n log n): 66 O(n): 288
O(n log n): 67 O(n): 299
O(n log n): 67 O(n): 258
O(n log n): 72 O(n): 371
Average: 72 290
```

That's times in milliseconds for test cases of 1e6 random ints. Did I do something wrong? Here's the code:

```
import java.util.*;
public class Test {
public int longestConsecutive1(int[] nums) {
Arrays.sort(nums);
int count=1;
int max=0;
for (int i=1; i<nums.length; i++){
if (nums[i-1]+1==nums[i]){
count++;
}else if (nums[i-1]!=nums[i]){
max=max<count?count:max;
count=1;
}
}
return max<count?count:max;
}
public int longestConsecutive2(int[] num) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int n : num) {
if (!map.containsKey(n)) {
int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
// sum: length of the sequence n is in
int sum = left + right + 1;
map.put(n, sum);
// keep track of the max length
res = Math.max(res, sum);
// extend the length to the boundary(s)
// of the sequence
// will do nothing if n has no neighbors
map.put(n - left, sum);
map.put(n + right, sum);
}
else {
// duplicates
continue;
}
}
return res;
}
public static void main(String[] args) {
int n = 1000000;
Test test = new Test();
long T1 = 0, T2 = 0;
for (int i=0; i<10; i++) {
int[] nums = new int[n];
Random r = new Random(1337);
for (int j=0; j<n; j++)
nums[j] = r.nextInt();
int[] copy1 = Arrays.copyOf(nums, n);
int[] copy2 = Arrays.copyOf(nums, n);
long t0 = System.currentTimeMillis();
test.longestConsecutive1(copy1);
long t1 = System.currentTimeMillis();
test.longestConsecutive2(copy2);
long t2 = System.currentTimeMillis();
System.out.println(String.format("O(n log n): %4d O(n): %4d", t1 - t0, t2 - t1));
T1 += t1 - t0;
T2 += t2 - t1;
}
System.out.println(String.format("Average: %4d %4d", T1 / 10, T2 / 10));
}
}
```