[C++]|Detailed Explanation w/ Three Approaches| Dry Run | EACH STEP EXPLAINED
Brief note about Question-\n We have to return the  length of the longest consecutive elements sequence.\n\nSince understanding question statement is very easy,
***Brief note about Question-***\n* We have to return the  length of the longest consecutive elements sequence.\n```\nSince understanding question statement is very easy, but just take an example not given in question-\nSuppose our given array is arr[]: [14, 5, 7, 6, 984, 8, 10]\n\nSo, if we rearrange this in a sorted manner, then it looks like arr[]: [5, 6, 7, 8, 10, 14, 984]\nso we can clearly see that (5, 6, 7, 8) forming an consecutive sequence\nTherefore, answer is 4\n```\n___________\n***Solution - I (using sorting)-***\n* The very first thing we can think of is we simply arrange the array in ascendig order.\n* After arranging the array in sorted order, we just find the length of the longest consecutive sequence.\n* Like, this is the most basic thing we can do.\n```\nTime Complexity --> O(n logn) // where n is the size of the array and since we are using sorting\nSpace Complexity --> O(1) // we are not using anything extra from our side\nIt paases [ 71 / 71 ] in built test cases\n```\n**Code (C++)**\n```\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& arr) {\n        int n = arr.size(); // extract the size of array\n        if(n == 0) return 0; // if length of array is zero, then from here simply return 0\n        \n        sort(arr.begin(), arr.end()); // sort the array\n        \n        int mxLen = 0, currLen = 1; // put mxLen = 0, and currLen as 1\n        \n        for(int i = 1; i < n; i++) // traverse from the array\n        {\n            if(arr[i] == arr[i - 1] + 1) // this is the part of consecutive sequence\n            {\n                currLen++; // increase the curr Length by 1\n            }\n            else if(arr[i] != arr[i - 1]) // but if it is not equal\n            {\n                mxLen = max(mxLen, currLen); // update our mxLen \n                currLen = 1; // and reset the currLen with 1\n            }\n        }\n        \n        mxLen = max(mxLen, currLen); // update our mxLen \n        return mxLen; // Finally return mxLen\n    }\n};\n```\n__________\n***Solution - I| (using Disjoint set Union)-***\n* What if we assume that every consecutive set of elements are work as connencted component.\n* It is totally fine, if we put all the consecutive set of elements in a group.\n* After putting all the elements in a group now we have to just find the maximum size of consecutive set of elements.\n* Using DSU, we are easily able to do that.\n* We are using standard format of DSU.\n* See commented code for better explantion.\n```\nTime Complexity --> O(n ) // where n is the size of the array and since we are making component\nSpace Complexity --> O(n) // we are using map\nIt paases [ 71 / 71 ] in built test cases\n```\n**Code (C++)**\n```\nclass Solution {\npublic:\n    int parent[100001], Rank[100001]; // make parent and rank array of max size\n    \n    int find(int a) // find function used to tell us the parent of the value \'a\'\n    {\n        if(parent[a] == a)\n            return a;\n        \n        return parent[a] = find(parent[a]);\n    }\n    \n    void Union(int a, int b) // By union we are making parent \n    {\n        a = find(a); // find parent of a\n        b = find(b); // find parent of b\n        \n        if(a == b) // if both parents are equal, simply return\n            return;\n        \n        if(Rank[a] > Rank[b]) // rank of a is larger, so it will become parent\n        {\n            // a would be parent\n            parent[b] = a; \n            Rank[a] += Rank[b]; // a become parent, so increase it\'s rank\n        }\n        else\n        {\n            // b would be parent\n            parent[a] = b;\n            Rank[b] += Rank[a]; // b become parent, so increase it\'s rank\n        } \n    }\n    int longestConsecutive(vector<int>& arr) {\n        int n = arr.size(); // extract the size of array\n        if(n == 0) return 0; // if length is zero simply return zero\n        \n        // since our parent and rank are global array so everytime reintiliaze them\n        for(int i = 0; i < n; i++) parent[i] = i, Rank[i] = 1;\n        \n        unordered_map<int, int> mp; // making map\n        \n        for(int i = 0; i < n; i++) // traverse from the arrat\n        {\n            // if element is already presnt into the map, just continue\n            if(mp.find(arr[i]) != mp.end()) continue;\n            \n            // if (arr[i] - 1) present in the map, we will perform union\n            if(mp.find(arr[i] - 1) != mp.end())\n            {\n                Union(mp[arr[i] - 1], i);\n            }\n            \n             // also, if (arr[i] - 1) present in the map, we will perform union\n            if(mp.find(arr[i] + 1) != mp.end())\n            {\n                Union(mp[arr[i] + 1], i);\n            }\n            \n             mp[arr[i]] = i;\n        }\n        \n        int ans = 0; // intiliaze ans as zero\n        for(int i = 0; i < n; i++)\n        {\n            ans = max(ans, Rank[i]); // take the largest component\n        }\n        \n        return ans; // finally return ans\n    }\n}; \n```\n__________________\n***Solution - III (Concept of map (Three step process), Accepted)-***\n* In the **first** step, ***for every element of the array we assume that it is the starting point of some consecutive sequence***.\n* We know that this is not right, so for a moment we just assume that every element is the starting point of some consecutive sequence.\n* So ***we will take a map, and  with every element as key we put value 1 for each element*.**\n* Now, in the **second** step ***we check for every element whether (arr[i] - 1)(arr[i] being any element of the array) is present in our map or not.***\n* Suppose if (arr[i] - 1) is present in our map, then in the first step the assumption we made that every element can be the starting point of some consecutive sequece goes wrong.\n* Because if (arr[i] - 1) is present in the array then we can surely say that arr[i] can\'t be the starting point of any consecutive sequence.\n\n* ***So, if(arr[i] - 1) is presnt in the array then we put zero for arr[i] in the map.***\n* Because at this point we can surely say that since (arr[i] - 1) is present in our map, so arr[i] can\'t be our starting point.\n* `Suppose, if arr[i] is 5 and we search for (arr[i] - 1) i.e (5 - 1 = 4) is present in our map or not. If 4 is present in our map, then 5 can\'t be the starting consecutive sequence, so in map we put zero for 5 `\n* In the **third** step, Now, we can surely say that the elements for which 1 is present in map are definately going to be the starting point of the some consecutive sequence.\n* So our task is left now, ***for every element for which 1 is presnt in map the now, for them we find the length of their consecutive sequence, and out of them whatever will be the maximum length is going to our answer.***\n* Taking an example for better understanding, see below.\n```\nSuppose our given array is arr[]: [12, 13, 2, 3, 4, 5, 8, 9, 10, 11, 78, 79, 80]\n\n1) In the first step, we make a map and for every element we put 1.\n  (Assuming that every element can be the starting point of some consecutive sequence)\n  so map looks like:-\n  \n  map\n  element (key)      |    value\n\t\t 12          |     1\n\t\t 13          |     1\n\t\t  2          |     1\n\t\t  3          |     1\n\t\t  4          |     1\n\t\t  5          |     1\n\t\t  8          |     1\n\t\t  9          |     1\n\t\t 10          |     1\n\t\t 11          |     1\n\t\t 78          |     1\n\t\t 79          |     1\n\t\t 80          |     1\n\t\t \n2) Now, in the second step, we will see whether (arr[i] - 1) is present in our map or not.\n    If (arr[i] - 1) is present in our map, then arr[i] can\'t be the starting point of some consecutive sequence.\n\t\n\tso, map looks like:-\n\t map\n  element (key)      |    value\n\t\t 12          |     0          (since (12 - 1 = 11) is present in map so we put zero in front of 12)\n\t\t 13          |     0          (since (13 - 1 = 12) is present in map so we put zero in front of 13)\n\t\t  2          |     1          (since (2 - 1 = 1) is not present in map so we leave 2 as it is)\n\t\t  3          |     0          (since (3 - 1 = 2) is present in map so we put zero in front of 3)\n\t\t  4          |     0          (since (4 - 1 = 3) is present in map so we put zero in front of 4)\n\t\t  5          |     0          (since (5 - 1 = 4) is present in map so we put zero in front of 5)\n\t\t  8          |     1          (since (8 - 1 = 7) is not present in map so we leave 8 as it is)\n\t\t  9          |     0          (since (9 - 1 = 8) is present in map so we put zero in front of 9)\n\t\t 10          |     0          (since (10 - 1 = 9) is present in map so we put zero in front of 10)\n\t\t 11          |     0          (since (11 - 1 = 10) is present in map so we put zero in front of 11)\n\t\t 78          |     1          (since (78 - 1 = 77) is not present in map so we leave 77 as it is)\n\t\t 79          |     0          (since (79 - 1 = 78) is present in map so we put zero in front of 79)\n\t\t 80          |     0          (since (80 - 1 = 79) is present in map so we put zero in front of 80)\n\t\t \n3) Now, in the third step, the elements for which 1 is left in the map, for them we can definately say\n    that they are starting point of some consecutive sequence.\n\tHere we can see that elements 2, 8, and 78 definately starting some consecutive sequence.\n\t\n\tThe only task is left to us now is to find the longest length of the consecutive sequence.\n\tHow we are going to do that? let see-\n\t\n\tNow, at this point we are only going to care about those elements which are having value as 1 in the map.\n\tWe also say that they are definately going to be the starting point some consecutive sequence, right.\n\tso, intially we define our length as 1, because they are the starting point so its definite they are having length atleast 1.\n\tsuppose we take 2, so intially length = 1\n\twhat we search now, we say 2 is there, ok, it\'s fine\n\tnow we ask whether 3 is there or not, we say yes it is their, so we increase our length as 2\n\tagain, we say whether 4 is there or not, and according to presence we increase our length.\n\t\n\tso if we observe everytime what we asking for, \n\tsuppose arr[i] is being 2 and intially length is 1\n\t\n\tso if i ask whether (arr[i] + length) is present or not, \n\tthan what (arr[i] + length) is, it is (2 + 1 = 3), we say yes 3 is there\n\tso we increase our length as 2\n\t\n\tnow, if we ask again (arr[i] + length) what it looks like, it looks like\n\tarr[i] is 2, but length is 2 now so (2 + 2 = 4) is present or not, we say yes  \n\tso we increase our length by 1, so length becomes 3\n\t\n\tagain now, if we ask again (arr[i] + length) what it looks like, it looks like\n\tarr[i] is 2, but length is 3 now so (2 + 3 = 5) is present or not, we say yes  \n\tso we increase our length by 1, so length becomes 4\n\t\n\tIn this way we can say that with the help of length we find the length of the consecutive sequence.\n\tAnd out of them whatever the will give me the maximum length should be my answer.\n\t\n\tSo, if we talk about our above example,\n\t\n\telements that left with value 1 are (2, 8 and 78)\n\tfor 2, we will see (2, 3, 4, 5) is the sequence, so length is 4\n\tfor 8, we will see (8, 9, 10, 11, 12, 13) is the sequence, so length is 6\n\tand for 78, we will see (78, 79, 80) is the sequence, so length is 3\n\t\n\tso out of three of them maximum is ({4, 6, 3}) is 6\n\tso, 6 will be my final answer.\n\t\n\tI hope you got the concept, see commented code for better understanding.\n```\n________\n```\nTime Complexity --> O(n + n + n) = O(3n) ~ O(n) \n// where n is the size of the array and since we are traversing array three times \n// 1) for putting 1 for each element (step 1)\n// 2) for improving our assumption (step 2)\n// 3) for finding sequence (step 3)\n\nSpace Complexity --> O(n) // since we are using map\nIt paases [ 71 / 71 ] in built test cases\n```\n___\n**Code (C++)**\n```\nclass Solution {\npublic:\n    int longestConsecutive(vector<int>& arr) {\n        int n = arr.size(); // extract the size of the array\n        \n        unordered_map<int, int> mp; // declaring unordered map\n        \n        // Step 1)  we are giving 1 to each of the elemnt\n        // (Assuming that it may be the starting point of consecutive sequence)\n        for(int i = 0; i < n; i++)\n        {\n            mp[arr[i]] = 1;\n        }\n        \n        // step 2) validating our assumption taken in step 1\n        for(int i = 0; i < n; i++)\n        {\n            if(mp.find(arr[i] - 1) != mp.end()) // if(arr[i] - 1) is present in map\n            {\n                // then arr[i] can never be the starting point some of consecutive sequence\n                // so give value zero for that arr[i]\n                mp[arr[i]] = 0;\n            }\n        }\n        \n        // step 3) Now the elements for which value 1 is left\n        // for them we definately know they are the starting point of \n        // some consecutive sequence, using that length trick we find the maxlen\n        \n        int mxLen = 0; // this variable holds my answer\n        \n        for(int i = 0; i < n; i++) // travel in the array\n        {\n            // if value is 1, then they are starting point some of consecutive sequence\n            if(mp[arr[i]] == 1) \n            {\n                // if it is the starting point, then definately length is going to be \n                // atleast 1\n                int length = 1; \n                \n               // we dicuss it above\n                while(mp.find(arr[i] + length) != mp.end())\n                {\n                    length++;\n                }\n                \n                mxLen = max(mxLen, length); // update mxLen\n            }\n        }\n        \n        return mxLen; // Finally return mxLen\n    }\n};\n```\n_______________\nA reference article I have taken help from:-\n* https://leetcode.com/problems/longest-consecutive-sequence/discuss/1127908/2-Approaches-for-your-interview(hindi)\n____________________\n***`If u find this useful , please consider to give a upvote!!`***\n
['C']