O(n) HashMap Java Solution


  • 22
    S

    Use a hashmap to map a number to its longest consecutive sequence length, each time find a new consecutive sequence, only the begin number and end number need to be modified.

    public class Solution {
        public int longestConsecutive(int[] num) {
            int longest = 0;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for(int i = 0;i < num.length;i++){
                // if there is no duplicates, these two lines can be commented
                if(map.containsKey(num[i])) continue;
                map.put(num[i],1);
                
                int end = num[i];
                int begin = num[i];
                if(map.containsKey(num[i]+1))
                    end = num[i] + map.get(num[i]+1);
                if(map.containsKey(num[i]-1))
                    begin = num[i] - map.get(num[i]-1);
                longest = Math.max(longest, end-begin+1);
                map.put(end, end-begin+1);
                map.put(begin, end-begin+1);
            }
            return longest;
        }
    }

  • 2
    D

    I have another solution, which minimize the number of put/get on HashMap

    public class Solution {
        public int longestConsecutive(int[] num) {
            int longest = 0;
            Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
            for(int i = 0; i< num.length; i++){
                map.put(num[i], false);
            }
            
            int l, k;
            for(int i = 0;i < num.length;i++){
                
                if(map.containsKey(num[i]-1) || map.get(num[i])) continue;
                map.put(num[i], true);
                l = 0; k = num[i];
                while (map.containsKey(k)){
                    l++;
                    k++;
                }
                if(longest < l) longest = l;
                
            }
            return longest;
        }
    }

  • 0
    H

    Can someone tell me why we need map.put(num[i],1);? Can't this be achieved by map.put(end, end-begin+1);
    map.put(begin, end-begin+1);?


  • 0
    J

    The code is right, but just difficult to explain and understand it's correctness. for example what Map<Integer, Integer> map stores, what's the key and value.

    100, 5, 4, 200, 2, 3, 1
    Map:
    {100=1}
    {100=1, 5=1}
    {100=1, 4=2, 5=2}
    {100=1, 4=2, 5=2, 200=1}
    {2=1, 100=1, 4=2, 5=2, 200=1}
    {2=4, 3=1, 100=1, 4=2, 5=4, 200=1}
    {1=5, 2=4, 3=1, 100=1, 4=2, 5=5, 200=1}


Log in to reply
 

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