-
Notifications
You must be signed in to change notification settings - Fork 0
/
LSS.java
34 lines (32 loc) · 933 Bytes
/
LSS.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// need O(n) runtime
// we can come up with hashset, the delete, add function needs constant time
// we only need to iterate the num array once
public class Solution {
public int longestConsecutive(int[] num) {
if(num == null || num.length == 0){
return 0;
}
HashSet<Integer> set = new HashSet<Integer>();
int maxLength = 1;
for(int number :num){
set.add(number);
}
for(int n : num){
int left = n - 1;
int right = n + 1;
int count = 1;
while(set.contains(left)){
set.remove(left);
left--;
count++;
}
while(set.contains(right)){
set.remove(right);
right++;
count++;
}
maxLength = Math.max(maxLength, count);
}
return maxLength;
}
}