✅☑️ Best C++ 4 solution ||  Hash Table || Sorting || Brute Force -> Optimize || One Stop Solution.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this problem using Four approaches. (Here I have explained all the possibl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this problem using Four approaches. (Here I have explained all the possible solutions of this problem).\n\n1. Solved using Array(Three Nested Loop). Brute Force Approach.\n2. Solved using Array + Sorting. Brute Better Approach.\n3. Solved using Array + Hash Table(Unordered map). Optimize Approach.\n4. Solved using Array + Hash Table (Unordered set). Optimize Approach.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the All the approaches by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is given in code comment.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is given in code comment.\n\n# Code\n```\n/*\n\n    Time Complexity : O(N^3), The outer loop runs exactly N times, and because currentNumber increments by 1\n    during each iteration of the while loop, it runs in O(N) time. Then, on each iteration of the while loop, an\n    O(N) operation in the array is performed. Therefore, this brute force algorithm is really three nested O(N)\n    loops, which compound multiplicatively to a cubic runtime. Where N is the size of the Array(nums).\n\n    Space Complexity : O(1), Constant space.\n\n    Using Array(Three Nested Loop). Brute Force Approach.\n\n    Note : This will give TLE.\n\n*/\n\n\n/***************************************** Approach 1 Code *****************************************/\n\nclass Solution {\nprivate: \n    bool longestConsecutive(vector<int>& nums, int target){\n        int n = nums.size();\n        for(int i=0; i<n; i++){\n            if(nums[i] == target){\n                return true;\n            }\n        }\n        return false;\n    }\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        int n = nums.size();\n        int longestConsecutiveSequence = 0;\n        for(auto num : nums){\n            int currentNumber = num;\n            int currentConsecutiveSequence = 1;\n            while(longestConsecutive(nums, currentNumber+1)){\n                currentNumber += 1;\n                currentConsecutiveSequence += 1;\n            }\n            longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);\n        }\n        return longestConsecutiveSequence;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(NlogN), The main for loop does constant work N times, so the algorithm\'s time complexity\n    is dominated by the invocation of sorting algorithm, which will run in O(NlogN) time for any sensible\n    implementation. Where N is the size of the Array(nums).\n\n    Space Complexity : O(1), For the implementations provided here, the space complexity is constant because we\n    sort the input array in place.\n\n    Solved using Array + Sorting. Brute Better Approach.\n\n*/\n\n\n/***************************************** Approach 2 Code *****************************************/\n\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        int n = nums.size();\n        if(n == 0){\n            return 0;\n        }\n        sort(nums.begin(), nums.end());\n        int currentConsecutiveSequence = 1;\n        int longestConsecutiveSequence = 0;\n        for(int i=1; i<n; i++){\n            if(nums[i] != nums[i-1]){\n                if(nums[i] == nums[i-1] + 1){\n                    currentConsecutiveSequence++;\n                }\n                else{\n                    longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);\n                    currentConsecutiveSequence = 1;\n                }\n            }\n        }\n        return max(longestConsecutiveSequence, currentConsecutiveSequence);\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), We are traversing the Array(nums) thrice which creates the time complexity O(N)\n    becuase Unordered map operating takes constant time. Where N is the size of the Array(nums).\n\n    Space Complexity : O(N), Unordered map space.\n\n    Solved using Array + Hash Table(Unordered map). Optimize Approach.\n\n*/\n\n\n/***************************************** Approach 3 Code *****************************************/\n\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        unordered_map<int, bool> map;\n        for(int i = 0; i<nums.size(); i++){\n            map[nums[i]] = true;\n        }\n        for(int i=0; i<nums.size(); i++){\n            if(map.count(nums[i]-1) > 0){\n                map[nums[i]] = false;\n            }\n        }\n        int maxlen = 0;\n        for(int i=0; i<nums.size(); i++){\n            if(map[nums[i]] == true){\n                int j=0; int count=0;\n                while(map.count(nums[i]+j) > 0){\n                    j++;\n                    count++;\n                }\n                if(count>maxlen){\n                    maxlen = count;\n                }\n            }\n        }\n        return maxlen;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N), Although the time complexity appears to be quadratic due to the while loop nested\n    within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when\n    marks the beginning of a sequence (i.e. currentNumber-1 is not present in nums), the while loop can only run\n    for N iterations throughout the entire runtime of the algorithm. This means that despite looking like O(N^2)\n    complexity, the nested loops actually run in O(N+N)=O(N) time. All other computations occur in constant\n    time, so the overall runtime is linear. Where N is the size of the Array(nums).\n\n    Space Complexity : O(N), Unordered set space.\n\n    Solved using Array + Hash Table(Unordered set). Optimise Approach.\n\n*/\n\n\n/***************************************** Approach 4 Code *****************************************/\n\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& nums) {\n        unordered_set<int> set;\n        for(int num : nums){\n            set.insert(num);\n        }\n        int longestConsecutiveSequence = 0;\n        for(int num : nums){\n            if(set.find(num-1) == set.end()){\n                int currentNumber = num;\n                int currentConsecutiveSequence = 1;\n                while(set.find(currentNumber+1) != set.end()){\n                    currentNumber++;\n                    currentConsecutiveSequence++;\n                }\n                longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);\n            }\n        }\n        return longestConsecutiveSequence;\n    }\n};\n```\n***IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.***\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)
['Array', 'Hash Table', 'Sorting', 'C++']