# O(n) HashMap Java Solution

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

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

• 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);?

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

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