8.1 (Approach 1) | O(n)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe intuition behind this approach is to use an unordered map to efficiently check the presence of numbers and track consecutive sequences. We mark t
# Intuition\nThe intuition behind this approach is to use an unordered map to efficiently check the presence of numbers and track consecutive sequences. We mark the potential starting points of consecutive sequences and explore each sequence to find the longest one.\n\n# Approach\n1. Create an unordered map `mp` to store whether a number is present in the input vector `nums`.\n2. Iterate through the input vector and populate the unordered map with the presence of each number.\n3. Iterate through the input vector again:\n   - If `nums[i] - 1` is present in `mp`, mark `nums[i]` as not the start of a consecutive sequence by setting its value in the map to false.\n   - If `nums[i] - 1` is not present in `mp`, it means `nums[i]` is potentially the start of a consecutive sequence.\n4. Find the length of the consecutive sequences starting from the marked points and update the maximum length.\n5. Return the length of the longest consecutive sequence.\n\n\n# Complexity\n- Time complexity: O(n), where n is the size of the input vector.\n- Space complexity: O(n), due to the usage of the unordered map to store number presence.\n\n\n# code(Python)\n```python\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        # Step 1: Create a set \'num\' to efficiently check the presence of numbers.\n        num = set(nums)\n        longest = 0\n\n        # Step 2: Iterate through each number in \'nums\'.\n        for x in nums:\n            # If \'x-1\' is not in \'num\', it means \'x\' is potentially the start of a consecutive sequence.\n            if x - 1 not in num:\n                l = 0\n                # Step 3: While (x + l) is in \'num\', count the length of the consecutive sequence.\n                while (x + l) in num:\n                    l += 1\n                # Update \'longest\' if the current sequence length is greater.\n                longest = max(l, longest)\n\n        # Step 4: Return the length of the longest consecutive sequence.\n        return longest\n\n```\n\n# code(C++)\n```c++\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        // Step 1: Create an unordered map \'mp\' to store whether a number is present in the input vector \'nums\'.\n        unordered_map<int, bool> mp;\n\n        // Step 2: Iterate through the input vector and populate the unordered map with the presence of each number.\n        int n = nums.size();\n        for(int i = 0; i < n; i++) {\n            mp[nums[i]] = true;\n        }\n\n        // Step 3: Iterate through the input vector again:\n        for(int i = 0; i < n; i++) {\n            // If \'nums[i] - 1\' is present in \'mp\', mark \'nums[i]\' as not the start of a consecutive sequence by setting its value in the map to false.\n            if(mp.count(nums[i] - 1) > 0) {\n                mp[nums[i]] = false;\n            }\n        }\n\n        // Step 4: Find the length of the consecutive sequences starting from the marked points and update the maximum length.\n        int ml = 0;\n        for(int i = 0; i < n; i++) {\n            if(mp[nums[i]] == true) {\n                int j = 0, c = 0;\n                // Count the length of the consecutive sequence starting from \'nums[i]\'.\n                while(mp.count(nums[i] + j) > 0) {\n                    j++;\n                    c++;\n                }\n                // Update \'ml\' if the length of the current sequence is greater.\n                if(c > ml) {\n                    ml = c;\n                }\n            }\n        }\n\n        // Step 5: Return the length of the longest consecutive sequence.\n        return ml;\n    }\n};\n\n```\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n\n
['C++']