O(n) Solution using DFS with Explanation and Visualization - Accepted

• ``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int,int> mp;

for(int i = 0;i < nums.size();i++){
mp[nums[i]] = -1;
}

for(int i = 0;i < nums.size();i++){
if(mp[nums[i]+1]){
mp[nums[i]+1] = i;
}
}
int mx = 0;
for(int i = 0;i < nums.size();i++){
if(!mp[nums[i]+1]){
int next_index = mp[nums[i]],depth = 1;
while(next_index!=-1){
next_index = mp[nums[next_index]];
depth++;
}
mx = max(mx,depth);
}
}
return mx;
}
};
``````

First, we initialize our unordered_map with -1 (which mean I'm the bottom node of this tree) for all elements.
Then for each element in array check if its (value + 1) exist, if it exist change the (value + 1) hash value to be the index of this element.
Finally DFS, Iterate over all elements if the elements (value + 1) not exists (it means its the top node of this tree) start traversing until the next index value is -1 (which means we reached the bottom node).

Visualization :

After first iteration
[7,4,6,1,3,2,8] -> Array elements
[-1,-1,-1,-1,-1,-1,-1] -> unordered_map

After second iteration
[7,4,6,1,3,2,8] -> Array elements
[2,4,-1,-1,5,3,0] -> unordered_map

Third iteration
*start traversal from 4 since there is no 5 in our orderderd_map
4->3->2->1

*start traversal from 8 since there is no 9 in our orderderd_map
8->7->6

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.