Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
- mine
- Java
- Arrays.sort
Runtime: 2 ms, faster than 100.00%, Memory Usage: 40.3 MB, less than 34.83% of Java online submissions
//O(N * logN)time O(N)space public int longestConsecutive(int[] nums) { if (nums == null || nums.length == 0) { return 0; } Arrays.sort(nums); int t = 1; int res = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] - nums[i - 1] <= 1) { t += nums[i] - nums[i - 1]; } else { res = Math.max(res, t); t = 1; } } res = Math.max(res, t); return res; }
- Arrays.sort
- Java
- the most votes
-
HashMap
Runtime: 5 ms, faster than 49.11%, Memory Usage: 40 MB, less than 45.16% of Java online submissions
//O(N)time O(N)space public int longestConsecutive(int[] num) { int res = 0; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int n : num) { if (!map.containsKey(n)) { int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0; int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0; // sum: length of the sequence n is in int sum = left + right + 1; map.put(n, sum); // keep track of the max length res = Math.max(res, sum); // extend the length to the boundary(s) // of the sequence // will do nothing if n has no neighbors map.put(n - left, sum); map.put(n + right, sum); } } return res; }
-
HashSet
Runtime: 3 ms, faster than 91.81%, Memory Usage: 39.6 MB, less than 75.77% of Java online submissions
//O(N)time O(N)space public int longestConsecutive(int[] nums) { if (nums == null || nums.length == 0) return 0; Set<Integer> set = new HashSet<>(); for (int i : nums) set.add(i); int ans = 0; for (int num : nums) { int left = num - 1; int right = num + 1; set.remove(num); while (set.remove(left)) left--; while (set.remove(right)) right++; ans = Math.max(ans, right - left - 1); if (set.isEmpty()) return ans; } return ans; }
-