Leetcode 128) Longest Consecutive Sequence

09 Nov 2021 in Algorithms

Solution

• If we need to look up the data often, and we want time complexity to be O(n).

  => Think of Hash . O(1)

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int i : nums){
            s.add(i);
        }

        int max=0;
        Iterator<Integer> it = s.iterator();
        for(int i : s){
            int len = 1;
            int cur =  it.next();
            int left = cur-1; int right = cur+1;

            if(!s.contains(left)){
                while(s.contains(right)){
                    right++;
                    len++;
                }
                max= Math.max(max,len);

            }
        }
        return max;

    }
}

오답

• So the problem with this code, Even though it will work just okay with smaller dataset, This repeats unnecessary examination, which is not needed.

  • for example, Let’s say we have this 4 numbers in our set,

    s = {4,3,-1,2,1}

    iteration 1 : i=4, It will go through 2 while loops and find “4,3,2,1” , len =4

    iteration 2 : i=3, It will go through 2 while loops and fine “4,3,2,1” , len = 4

    iteration 3 : i=-1, It will go through 2 while loops and fine “-1” , len = 1

    iteration 4: i=2, It will go through 2 while loops and fine “4,3,2,1” , len = 4

    iteration 5 : i=1, It will go through 2 while loops and fine “4,3,2,1” , len = 4

    • so from here, the same sequence is identified over and over again, yet we only need one. => Time Limit Exceeded.

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int i : nums){
            s.add(i);
        }
        
        int max=0;
        for(int i : s){
            int len = 1;
            int left = i-1; int right = i+1;
            while(s.contains(left)){
                left--;
                len++;
            }
            while(s.contains(right)){
                right++;
                len++;
            }
            max= Math.max(max,len);
            
        }
        
        return max;
        
    }
}