[LeetCode] Longest Consecutive Sequence

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution: HashSet.

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

public class Solution { public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } HashSet<Integer> set = new HashSet<Integer>(); for (int num : nums) { set.add(num); } int max_len = 0; for (int num : nums) { int len = 1; set.remove(num); int i = num - 1; while (set.contains(i)) { len++; set.remove(i); i--; } int j = num + 1; while (set.contains(j)) { len++; set.remove(j); j++; } if (max_len < len) { max_len = len; } } return max_len; } }