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


  • 0
    B
    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


Log in to reply
 

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