Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/128.html
128. 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.
@tag-array
Algorithm
For every num existed in set, try to probe to right to see if following numbers are also in set, and record longest possible sequence.
Code
Java
-
import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class Longest_Consecutive_Sequence { // Time complexity : O(n) // Space complexity : O(n) class Solution_oN { public int longestConsecutive(int[] nums) { Set<Integer> hs = new HashSet<Integer>(); // remove duplicates for (int num : nums) { hs.add(num); } int longestStreak = 0; for (int num : hs) { if (!hs.contains(num - 1)) { int currentNum = num; int currentStreak = 1; while (hs.contains(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; } } class Solution_sort { public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } Arrays.sort(nums); int longestStreak = 1; int currentStreak = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[i-1]) { if (nums[i] == nums[i-1]+1) { currentStreak += 1; } else { longestStreak = Math.max(longestStreak, currentStreak); currentStreak = 1; } } } return Math.max(longestStreak, currentStreak); } } }
-
// OJ: https://leetcode.com/problems/longest-consecutive-sequence/ // Time: O(N) // Space: O(N) // Ref: https://leetcode.com/problems/longest-consecutive-sequence/discuss/41088/Possibly-shortest-cpp-solution-only-6-lines. class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_map<int, int> m; int ans = 0; for (int n : nums) { if (m[n]) continue; ans = max(ans, m[n] = m[n - m[n - 1]] = m[n + m[n + 1]] = m[n - 1] + m[n + 1] + 1); } return ans; } };
-
class Solution: def longestConsecutive(self, nums: List[int]) -> int: s, res = set(nums), 0 for num in nums: if num - 1 not in s: t, next = 1, num + 1 while next in s: t, next = t + 1, next + 1 res = max(res, t) return res ############ class Solution(object): def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ ans = 0 s = set(nums) for num in nums: if num in s: s.discard(num) cnt = 1 right = num + 1 left = num - 1 while left in s: s.discard(left) cnt += 1 left -= 1 while right in s: s.discard(right) cnt += 1 right += 1 ans = max(ans, cnt) return ans