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


  • 0
    I

    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;
        }
    }
    

  • 1
    D

    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)


  • 0
    F

    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.


  • 0

    @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));
        }
    }
    

Log in to reply
 

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