My really simple Java O(n) solution - Accepted


  • 379
    D

    We will use HashMap. The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for sequence {1, 2, 3, 4, 5}, map.get(1) and map.get(5) should both return 5.

    Whenever a new element n is inserted into the map, do two things:

    1. See if n - 1 and n + 1 exist in the map, and if so, it means there is an existing sequence next to n. Variables left and right will be the length of those two sequences, while 0 means there is no sequence and n will be the boundary point later. Store (left + right + 1) as the associated value to key n into the map.
    2. Use left and right to locate the other end of the sequences to the left and right of n respectively, and replace the value with the new length.

    Everything inside the for loop is O(1) so the total time is O(n). Please comment if you see something wrong. Thanks.

    public int longestConsecutive(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;
    }

  • 0
    F

    Have one question. Every time we put a n into the map, I think the right will always be 0 because n+1 will always be put into the map after the n, is that right? If my though is correct, then why do we do this right thing? Also, could you please explain more about the last two line of code in the loop?(map.put(n-left,sum)), map.put(n+right,sum), I dont quite follow this idea. Say[1,2,3,100], then when we put 2, map.put(n-left,sum)->put(1,2) but already contains (1,1), here we want to override it? why? also, since right may always be zero, map.put(n+right,sum) will always be map.put(n,sum). Am I right????


  • 1
    D

    No, because the array is not sorted.

    In the case of your example, we want to overwrite the value of key 1, because [1, 2] is a consecutive sequence, and 1 and 2 as the boundaries of the sequence, should have the length of the sequence as their value in which case is 2.


  • 0
    F

    thank you so much! I got it. I thought the array is sorted, you are right. One more question. How do you come up equation of sum = right + left + 1; can you explain a little bit? +1 here refers to n, am I right? and in this equation, right means length of right side of n(consecutive), left means length of left side of n, am I right?


  • 0
    D

    That is correct.


  • 0
    J

    This is fantastic


  • 0
    R

    Great solution!


  • 0
    P

    Building the map of keys n will take time of O(nlogn) , so how is your solution a O(n) solution ?


  • 0
    R

    Really nice solution! Bravo!


  • 0
    W

    If in c++, using unordered map is based on direct hash, so inserting is constant time, though I am not sure about how the internal java works.


  • 4
    W

    In the alg. above, the two boundaries of each sequence is maintained. But the value in the middle of the sequence may NOT have a meaning at the end.


  • 0
    H

    good solution!
    we can save the else block and it's okay just map.put(n, 1); instead of map(n, sum);
    thank you for sharing.


  • 1
    9

    Hi, what if there is duplicate in the array? then the new length sum = left + right + 1 might involve some overlap that makes the new sum larger than real sum ...


  • 0
    M

    Nice solution!


  • 0
    C

    Can Anyone tell what is the benefit using hashmap over set?


  • 0
    L

    OMG, so Brilliant!!!


  • 0
    W

    but the newly added point has to be outside the two boundaries otherwise it will be a duplicated value.


  • 6
    Y

    Python version

     def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            res, dic=1, {}
            for n in nums:
                if n not in dic:
                    left=dic.get(n-1, 0)
                    right=dic.get(n+1, 0)
                    leng=left+right+1
                    dic[n]=leng
                    res=max(res, leng)
                    dic[n-left]=leng
                    dic[n+right]=leng
            return res

  • 0
    A

    Brilliant Ideas to update information on boundaries.


  • 0
    M

    Set is implemented by Map actually, they should have no significant difference in performance.


Log in to reply
 

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