Iterative C++ solution that works (could be optimized)


  • 0
    A

    Can someone one check and find out any optimizations that can be done or can it fail on some cases?

    class Solution {
    public:
        
        
    vector<UndirectedGraphNode *> cloneNeighBours(std::unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& outCloneMap, vector<UndirectedGraphNode *> neighbors, std::queue<UndirectedGraphNode*>& queueToBePushed)
    {
        vector<UndirectedGraphNode *> cloned;
        for (auto e : neighbors)
        {
            auto itr = outCloneMap.find(e);
            if (itr == outCloneMap.end())
            {
                UndirectedGraphNode* newClone = new UndirectedGraphNode(e->label);
                outCloneMap[e] = newClone;
                itr = outCloneMap.find(e);
                queueToBePushed.push(e);
            }
            cloned.push_back(itr->second);
        }
        return cloned;
    
    }
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    
        if (node == nullptr) return node;
    
        std::unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> cloneToNewCloneMap;
    
        UndirectedGraphNode* firstClonedElement = nullptr;
    
        std::queue<UndirectedGraphNode*> elementToClone;
        elementToClone.push(node);
    
        while (!elementToClone.empty())
        {
            auto cloning = elementToClone.front();
    
            auto itr = cloneToNewCloneMap.find(cloning);
    
            if (itr == cloneToNewCloneMap.end())
            {
                UndirectedGraphNode* newClone = new UndirectedGraphNode(cloning->label);
                cloneToNewCloneMap[cloning] = newClone;
                itr = cloneToNewCloneMap.find(cloning);
                for (auto i : cloning->neighbors)
                {
                    elementToClone.push(i);
                }
            }
    
            if (firstClonedElement == nullptr)
            {
                firstClonedElement = itr->second;
            }
    
            itr->second->neighbors = cloneNeighBours(cloneToNewCloneMap, cloning->neighbors, elementToClone);
    
            elementToClone.pop();
        }
    
        return firstClonedElement;
    
    }
    };

Log in to reply
 

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