# Java Straightforward Solution

1. Use a HashMap<Integer,Boolean>. Use every number in num[] as a key, mark them as not used.

2. For each number in the hashmap, if the number is not used, select it as the center to grow a sequence on number++ and number--
directions. Mark used number as used.

3. After each growth, update the longestSoFar.

4. Return the longestSoFar.

5. Since each number is used only once, the time complexity is O(n).

``````public class Solution {
public int longestConsecutive(int[] num) {
if(num.length<=1)
return num.length;
HashMap<Integer,Boolean> numberUsed=new HashMap<Integer,Boolean>();
for(int i:num)
numberUsed.put(i,false);
int longestSoFar=1;
for(int i:num)
{
if(numberUsed.get(i)==false)
{
int localLongest=1;
int tmp=i+1;
numberUsed.put(i,true);
while(numberUsed.containsKey(tmp)&&numberUsed.get(tmp)==false)
{
localLongest+=1;
numberUsed.put(tmp,true);
tmp+=1;
}
tmp=i-1;
while(numberUsed.containsKey(tmp)&&numberUsed.get(tmp)==false)
{
localLongest+=1;
numberUsed.put(tmp,true);
tmp-=1;
}
longestSoFar=Math.max(longestSoFar,localLongest);
}
}
return longestSoFar;
}
}``````

• nice solution! actually the boolean value is not nessesary. this is my python version using set instead of hashmap:

``````class Solution:
# @param num, a list of integer
# @return an integer
def longestConsecutive(self, num):
unUsedNum, maxlen = set(num), 0
for numi in num:
if numi in unUsedNum:
unUsedNum.remove(numi)

small = numi - 1
while small in unUsedNum:
unUsedNum.remove(small)
small -= 1

big = numi + 1
while big in unUsedNum:
unUsedNum.remove(big)
big += 1

maxlen = max(maxlen, big - small - 1)
return maxlen``````

• Actually... This is a O(n^2) solution. Clearly you have some misunderstandings on Big O. And surprisingly, the OJ cannot judge the real big O of this questions.

• Hi @nevergone_sc, may I ask why? It seems to me it's O(n)

• Sorry! My bad, I didn't think it through! Genius thought!

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