# Why is first more efficient than other methods? (Java 4ms solution)

• This was the first thing that I tried and it somehow beat 97.5% of submissions.

``````public class Solution {
public int longestConsecutive(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;
}
}
``````

• Your algorithm is correct, but the direction says that it should run in O(n) time.

The fact that you used sort on the array means your algorithm runs at least O(nlogn)

• why O(nlogn) solution beat 97.5% of others? It means that the test metrics of leetcode isn't designed properly. 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.

• 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));
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.