5
\$\begingroup\$

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

Problem

(This problem is the same as Minimize Malware Spread, with the differences bolded.)

In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.

Some nodes initial are initially infected by malware. Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.

We will remove one node from the initial list, completely removing it and any connections from this node to any other node. Return the node that if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.

Example 1:

  • Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
  • Output: 0

Example 2:

  • Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
  • Output: 1

Example 3:

  • Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
  • Output: 1

Note:

  • \$1 < \text{graph}.\text{length} = \text{graph}[0].\text{length} <= 300\$
  • \$0 <= \text{graph}[i][j] == \text{graph}[j][i] <= 1\$
  • \$\text{graph}[i][i] = 1\$
  • \$1 <= \text{initial}.\text{length} < \text{graph}.\text{length}\$
  • \$0 <= \text{initial}[i] < \text{graph}.\text{length}\$

Inputs

[[1,1,0],[1,1,0],[0,0,1]]
[0,1]
[[1,1,0],[1,1,1],[0,1,1]]
[0,1]
[[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]]
[0,1]

Outputs

0
1
1

Code

#include <cstdint>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>


struct Solution {
    using uint16 = std::uint_fast16_t;
    int minMalwareSpread(
        std::vector<std::vector<int>>& graph,
        std::vector<int>& initial
    ) {
        uint16 smallest_node = 0;
        uint16 initial_len = std::size(initial);
        uint16 min_len = std::size(graph);
        std::sort(std::begin(initial), std::end(initial));

        for (const auto init_node : initial) {
            const uint16 curr_len = breadthFirstSearch(graph, initial, init_node);

            if (curr_len < min_len) {
                min_len = curr_len;
                smallest_node = init_node;
            }
        }

        return smallest_node;
    }

private:
    static uint16 breadthFirstSearch(
        const std::vector<std::vector<int>>& graph,
        std::vector<int>& initial,
        uint16 node
    ) {
        std::queue<uint16> nodes_queue;
        std::unordered_set<uint16> nodes_set = {node};
        uint16 count = 0;

        for (const auto init_node : initial) {
            if (init_node != node) {
                nodes_queue.push(init_node);
            }
        }

        while (!nodes_queue.empty()) {
            uint16 curr_node = nodes_queue.front();
            nodes_queue.pop();

            if (nodes_set.count(curr_node)) {
                continue;
            }

            nodes_set.insert(curr_node);
            ++count;

            for (uint16 index = 0; index < std::size(graph); ++index) {
                if (index != curr_node && graph[curr_node][index]) {
                    nodes_queue.push(index);
                }
            }
        }

        return count;
    }
};

References

\$\endgroup\$
1
\$\begingroup\$

Misleading type alias

You are using uint16 = std::uint_fast16_t, but if I see the name uint16, as a programmer I assume this is identical to uint16_t. But uint16_t and uint_fast16_t might have very different properties, so therefore it is a potentially misleading name.

When you create a type alias, you usually want to give it a name that conveys its intent. Here, it's to hold sizes and indices. So I would recommed using size_type = ... instead.

Name functions after their intent, not their implementation

The function breadthFirstSearch() indeed uses a BFS algorithm internally, but the intent of this function is to return the number of infected nodes given a set of initial infectations and an excluded node. So name it something like countInfectedNodes() instead.

While you are at it, rename node in that function to excluded_node, to make it clear what its purpose is.

Use a std::vector<bool> to keep track of infected nodes

A bitset is much more compact and faster than a std::set in this case, since nodes are just numbers between zero and std::size(graph). However, you can't use std::bitset here because that needs the size to be known at compiletime. Instead, this is one of the few occasions where a std::vector<bool> is useful:

std::vector<bool> nodes_set(std::size(graph));
nodes_set[excluded_node] = true;
...

Avoid modifying the input parameters

While the LeetCode problem does state that the parameters are non-const, it is nevertheless bad practice to modify the input parameters if it's not expected that this will happen.

You can avoid sorting initial, by just modifying the way you set smallest_node:

if (curr_len < min_len || (curr_len == min_len && init_node < smallest_node)) {
    min_len = curr_len;
    smallest_node = init_node;
}

Consider stopping counting infections if it won't improve the minimum

Currently, for every candidate node to remove, you count all infections. However, if halfway you notice that you are already above the minimum seen so far, then you can stop early. Just pass the previous min_len to countInfectedNodes() and check it when incrementing count:

static size_type countInfectedNodes(
    const std::vector<std::vector<int>>& graph,
    std::vector<int>& initial,
    size_type excluded_node,
    size_type current_min,
) {
    ...
        nodes_set[curr_node] = true;
        if (++count > current_min) {
            break;
        }
    ...
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.