C++ O(n) solution, 6ms, beats 100%


  • 0
    S
    class Solution {
    public:
    
        vector<int> findRedundantConnection(vector<vector<int>>& edges) 
        {
            unordered_map<int, int> vertex_in_degrees; //vertex in-degrees
            unordered_set<int> no_in_vertex_set;       //vertex with zero in-degree
            
            vector<int> possible_res;
            
            for(const auto & edge : edges)
            {
                if(vertex_in_degrees.count(edge[1]) == 1 && no_in_vertex_set.size() == 1)
                    return edge;
                
                if(vertex_in_degrees.count(edge[1]) == 1)
                    possible_res = edge;
                
                ++vertex_in_degrees[edge[1]];
                
                if(no_in_vertex_set.count(edge[1]) == 1)
                    no_in_vertex_set.erase(edge[1]);
                
                if(vertex_in_degrees.count(edge[0]) == 0)
                    no_in_vertex_set.insert(edge[0]);
                
                if(no_in_vertex_set.empty() == true)
                    return edge;
            }
            
            if(no_in_vertex_set.size() == 2)
            {
                for(auto & ele : vertex_in_degrees)
                {
                    if(ele.second == 2)
                    {
                        vector<int> res;
                        for(auto & edge : edges)
                        {
                            if(no_in_vertex_set.count(edge[0]) == 1 && edge[1] == ele.first)
                                res = edge;
                        }
                        return res;
                    }
                }
            }
            else
            {
                return possible_res;
            }
        }
    };
    

Log in to reply
 

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