Longest Consecutive Sequence in an Array
Longest Consecutive Sequence – Medium Level
Given an array of integers nums, return the length of the longest consecutive sequence of elements.
A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element.
You must write an algorithm that runs in O(n) time.
Output: 4
Output: 7
Constraints:
- 0 <= nums.length <= 1000
- -10^9 <= nums[i] <= 10^9
Check Sudoku board configuration is valid or not Solution
Recommendation for Time and Space Complexity – You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would be to consider every element from the array as the start of the sequence and count the length of the sequence formed with that starting element. This would be an O(n^2) solution. Can you think of a better way?
Hint 2 :
Is there any way to identify the start of a sequence? For example, in [1, 2, 3, 10, 11, 12], only 1 and 10 are the beginning of a sequence. Instead of trying to form a sequence for every number, we should only consider numbers like 1 and 10.
Hint 3 :
We can consider a number num as the start of a sequence if and only if num – 1 does not exist in the given array. We iterate through the array and only start building the sequence if it is the start of a sequence. This avoids repeated work. We can use a hash set for O(1) lookups by converting the array to a hash set.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Sorting Method
- Hash Set Method
- Hash Map Method
1. Brute Force Method
This method check every possible sequence starting from each element in the array to find the longest consecutive sequence.
- Time complexity: O(n^2)
- Space complexity: O(n)
Code
class Solution { public: int longestConsecutive(vector& nums) { int res = 0; unordered_set store(nums.begin(), nums.end()); for (int num : nums) { int streak = 0, curr = num; while (store.find(curr) != store.end()) { streak++; curr++; } res = max(res, streak); } return res; } };
public class Solution { public int longestConsecutive(int[] nums) { int res = 0; Setstore = new HashSet<>(); for (int num : nums) { store.add(num); } for (int num : nums) { int streak = 0, curr = num; while (store.contains(curr)) { streak++; curr++; } res = Math.max(res, streak); } return res; } }
class Solution: def longestConsecutive(self, nums: List[int]) -> int: res = 0 store = set(nums) for num in nums: streak, curr = 0, num while curr in store: streak += 1 curr += 1 res = max(res, streak) return res
class Solution { /** * @param {number[]} nums * @return {number} */ longestConsecutive(nums) { let res = 0; const store = new Set(nums); for (let num of nums) { let streak = 0, curr = num; while (store.has(curr)) { streak++; curr++; } res = Math.max(res, streak); } return res; } }
2. Sorting Method
This method sort the array, then iterate through it to find the length of the longest consecutive sequence.
- Time complexity: O(n logn)
- Space complexity: O(1)
Code
class Solution { public: int longestConsecutive(vector& nums) { if (nums.empty()) return 0; sort(nums.begin(), nums.end()); int res = 0, curr = nums[0], streak = 0, i = 0; while (i < nums.size()) { if (curr != nums[i]) { curr = nums[i]; streak = 0; } while (i < nums.size() && nums[i] == curr) { i++; } streak++; curr++; res = max(res, streak); } return res; } };
public class Solution { public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } Arrays.sort(nums); int res = 0, curr = nums[0], streak = 0, i = 0; while (i < nums.length) { if (curr != nums[i]) { curr = nums[i]; streak = 0; } while (i < nums.length && nums[i] == curr) { i++; } streak++; curr++; res = Math.max(res, streak); } return res; } }
class Solution: def longestConsecutive(self, nums: List[int]) -> int: if not nums: return 0 res = 0 nums.sort() curr, streak = nums[0], 0 i = 0 while i < len(nums): if curr != nums[i]: curr = nums[i] streak = 0 while i < len(nums) and nums[i] == curr: i += 1 streak += 1 curr += 1 res = max(res, streak) return res
class Solution { /** * @param {number[]} nums * @return {number} */ longestConsecutive(nums) { if (nums.length === 0) { return 0; } nums.sort((a, b) => a - b); let res = 0, curr = nums[0], streak = 0, i = 0; while (i < nums.length) { if (curr !== nums[i]) { curr = nums[i]; streak = 0; } while (i < nums.length && nums[i] === curr) { i++; } streak++; curr++; res = Math.max(res, streak); } return res; } }
3. Hash Set Method
This method store all elements in a hash set for O(1) lookups, then iterate through the array and start counting the length of a sequence only when the current number is the start of a sequence (no smaller number exists).
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution { public: int longestConsecutive(vector& nums) { unordered_set numSet(nums.begin(), nums.end()); int longest = 0; for (int num : numSet) { if (numSet.find(num - 1) == numSet.end()) { int length = 1; while (numSet.find(num + length) != numSet.end()) { length++; } longest = max(longest, length); } } return longest; } };
public class Solution { public int longestConsecutive(int[] nums) { SetnumSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } int longest = 0; for (int num : numSet) { if (!numSet.contains(num - 1)) { int length = 1; while (numSet.contains(num + length)) { length++; } longest = Math.max(longest, length); } } return longest; } }
class Solution: def longestConsecutive(self, nums: List[int]) -> int: numSet = set(nums) longest = 0 for num in numSet: if (num - 1) not in numSet: length = 1 while (num + length) in numSet: length += 1 longest = max(length, longest) return longest
class Solution { /** * @param {number[]} nums * @return {number} */ longestConsecutive(nums) { const numSet = new Set(nums); let longest = 0; for (let num of numSet) { if (!numSet.has(num - 1)) { let length = 1; while (numSet.has(num + length)) { length++; } longest = Math.max(longest, length); } } return longest; } }
4. Hash Map Method
This method use a hash map to dynamically update the lengths of consecutive sequences while iterating through the array, achieving O(n) time complexity.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution { public: int longestConsecutive(vector& nums) { unordered_map mp; int res = 0; for (int num : nums) { if (!mp[num]) { mp[num] = mp[num - 1] + mp[num + 1] + 1; mp[num - mp[num - 1]] = mp[num]; mp[num + mp[num + 1]] = mp[num]; res = max(res, mp[num]); } } return res; } };
public class Solution { public int longestConsecutive(int[] nums) { Mapmp = new HashMap<>(); int res = 0; for (int num : nums) { if (!mp.containsKey(num)) { mp.put(num, mp.getOrDefault(num - 1, 0) + mp.getOrDefault(num + 1, 0) + 1); mp.put(num - mp.getOrDefault(num - 1, 0), mp.get(num)); mp.put(num + mp.getOrDefault(num + 1, 0), mp.get(num)); res = Math.max(res, mp.get(num)); } } return res; } }
class Solution: def longestConsecutive(self, nums: List[int]) -> int: mp = defaultdict(int) res = 0 for num in nums: if not mp[num]: mp[num] = mp[num - 1] + mp[num + 1] + 1 mp[num - mp[num - 1]] = mp[num] mp[num + mp[num + 1]] = mp[num] res = max(res, mp[num]) return res
class Solution { /** * @param {number[]} nums * @return {number} */ longestConsecutive(nums) { const mp = new Map(); let res = 0; for (let num of nums) { if (!mp.has(num)) { mp.set(num, (mp.get(num - 1) || 0) + (mp.get(num + 1) || 0) + 1); mp.set(num - (mp.get(num - 1) || 0), mp.get(num)); mp.set(num + (mp.get(num + 1) || 0), mp.get(num)); res = Math.max(res, mp.get(num)); } } return res; } }