What is the time complexity of Minimize Malware Spread?

The optimal solution has a time complexity of O(N^2).

What data structures are used to solve Minimize Malware Spread?

This problem uses Array, Hash Table, Depth-First Search, Breadth-First Search, Union Find, Graph. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Minimize Malware Spread?

Insight 1: The problem can be efficiently solved using the Disjoint Set Union (DSU) data structure to find connected components in the graph. Insight 2: We need to count how many initially infected nodes belong to each connected component.

Which companies ask LeetCode 924. Minimize Malware Spread in interviews?

This problem is frequently asked at DoorDash, Dropbox.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Minimize Malware Spread - LeetCode 924 Solution

Minimize Malware Spread - Complete Solution Guide

Minimize Malware Spread is LeetCode problem 924, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a network of n nodes represented as an n x n adjacency matrix graph , where the i th node is directly connected to the j th node 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 i

Detailed Explanation

The problem asks us to find the best node to remove from an initially infected set of nodes in a graph such that the final number of infected nodes after the malware spreads is minimized. The graph is represented as an adjacency matrix. Malware spreads from an infected node to all its directly connected neighbors, and this continues until no more nodes can be infected. We need to remove exactly one node from the initial infected set and return the node that results in the least number of infected nodes overall. If there are multiple such nodes, we return the node with the smallest index.

Solution Approach

The provided code uses the Disjoint Set Union (DSU) data structure to solve this problem. First, it builds the connected components of the graph using the DSU. Then, for each connected component, it counts the number of initially infected nodes belonging to it. Finally, it iterates through the initial infected nodes. For each node, it checks if removing it would prevent the spread of malware to a whole connected component (i.e., if the connected component has only one infected node). It chooses the node to remove that saves the largest connected component. If multiple nodes achieve the same savings, it picks the node with the smallest index.

Step-by-Step Algorithm

Step 1: Initialize a DSU data structure (parent array and size array). The parent array initially points each node to itself (making it the root of its own set), and the size array is initialized to 1 for each node.
Step 2: Iterate through the adjacency matrix and build the connected components using the `union` operation of the DSU. If `graph[i][j] == 1`, it means nodes `i` and `j` are connected, so we merge their sets.
Step 3: Count the number of initially infected nodes in each connected component. Iterate through the `initial` array, find the root of each node using the `find` operation, and increment the count for that root in a `infected_counts` map.
Step 4: Sort the `initial` array to ensure that if multiple nodes result in the same minimum infected nodes, we return the one with the smallest index.
Step 5: Iterate through the sorted `initial` array. For each node, find its root and check if the `infected_counts` for that root is 1 (meaning it's the only infected node in that component). If it is, compare the size of that component with the current `max_saved_size`. If the component size is greater, update `max_saved_size` and the `result_node`.
Step 6: Return the `result_node`.

Key Insights

Insight 1: The problem can be efficiently solved using the Disjoint Set Union (DSU) data structure to find connected components in the graph.
Insight 2: We need to count how many initially infected nodes belong to each connected component.
Insight 3: Removing a node from an initial set has a significant impact only if that node is the *only* infected node in its connected component. In that case, the entire connected component is saved from infection.
Insight 4: When choosing which node to remove, prioritize those within connected components having only one infected node and select the node associated with the largest component size.

Complexity Analysis

Time Complexity: O(N^2)

Space Complexity: O(N)

Topics

This problem involves: Array, Hash Table, Depth-First Search, Breadth-First Search, Union Find, Graph.

Companies

Asked at: DoorDash, Dropbox.

Minimize Malware Spread | LeetCode 924

Hard

Array Hash Table Depth-First Search Breadth-First Search Union Find Graph

Time: O(N^2)Space: O(N)

Solution Code

Available in:

import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] parent = new int[n];
        int[] sz = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }

        function find = new function();

        class function{
            public int find(int i, int[] parent) {
                if (parent[i] == i) {
                    return i;
                }
                parent[i] = find(parent[i], parent);
                return parent[i];
            }
    
            public void union(int i, int j, int[] parent, int[] sz) {
                int root_i = find(i, parent);
                int root_j = find(j, parent);
                if (root_i != root_j) {
                    if (sz[root_i] < sz[root_j]) {
                        int temp = root_i;
                        root_i = root_j;
                        root_j = temp;
                    }
                    parent[root_j] = root_i;
                    sz[root_i] += sz[root_j];
                }
            }
        }
        

        // 1. Build connected components using DSU
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    find.union(i, j, parent, sz);
                }
            }
        }

        // 2. Count initial infections per component
        Map<Integer, Integer> infected_counts = new HashMap<>();
        for (int i : initial) {
            int root = find.find(i, parent);
            infected_counts.put(root, infected_counts.getOrDefault(root, 0) + 1);
        }

        // 3. Sort initial to handle tie-breaking (return smallest index)
        Arrays.sort(initial);

        // 4. Find the best node to remove
        int max_saved_size = -1;
        int result_node = initial[0];

        for (int node : initial) {
            int root = find.find(node, parent);
            // If this component has only one initial infection, removing `node` saves the whole component
            if (infected_counts.getOrDefault(root, 0) == 1) {
                int component_size = sz[root];
                if (component_size > max_saved_size) {
                    max_saved_size = component_size;
                    result_node = node;
                }
            }
        }

        return result_node;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 924: Minimize Malware Spread - Detailed explanation and solution approaches.

Topics

Array Hash Table Depth-First Search Breadth-First Search Union Find Graph

Companies

DoorDashDropbox

Stats

Difficulty:Hard

Languages:4

Companies:2

Problem #:924

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a DSU data structure (parent array and size array). The parent array initially points each node to itself (making it the root of its own set), and the size array is initialized to 1 for each node.
2
Step 2: Iterate through the adjacency matrix and build the connected components using the `union` operation of the DSU. If `graph[i][j] == 1`, it means nodes `i` and `j` are connected, so we merge their sets.
3
Step 3: Count the number of initially infected nodes in each connected component. Iterate through the `initial` array, find the root of each node using the `find` operation, and increment the count for that root in a `infected_counts` map.
4
Step 4: Sort the `initial` array to ensure that if multiple nodes result in the same minimum infected nodes, we return the one with the smallest index.
5
Step 5: Iterate through the sorted `initial` array. For each node, find its root and check if the `infected_counts` for that root is 1 (meaning it's the only infected node in that component). If it is, compare the size of that component with the current `max_saved_size`. If the component size is greater, update `max_saved_size` and the `result_node`.
6
Step 6: Return the `result_node`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N^2)

💾

Space Complexity

O(N)

📝

Why?

The nested loops in the first part of the algorithm (building connected components) contribute O(N^2). The other loops and map operations are O(N) or less. Therefore, the overall time complexity is O(N^2). The space complexity comes from storing the `parent`, `sz`, and `infected_counts` data structures, each of which requires O(N) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS) or Breadth-First Search (BFS)

Instead of DSU, you can use DFS or BFS to find connected components. For each initial node to potentially remove, perform DFS/BFS to find the size of the connected component it belongs to. Keep track of the connected components that share more than one initial node.

Time: O(N^2), where N is the number of nodes in the graph. In the worst case, DFS/BFS might explore the entire graph for each component.Space: O(N), where N is the number of nodes in the graph. This is due to the adjacency list representation of the graph and the visited set used in DFS/BFS.

Trade-offs: DFS/BFS might be more intuitive for some people to implement than DSU, but they generally have similar performance characteristics for this problem. The DSU approach is preferred due to code simplicity and readability.

✨

Key Insights

1Insight 1: The problem can be efficiently solved using the Disjoint Set Union (DSU) data structure to find connected components in the graph.
2Insight 2: We need to count how many initially infected nodes belong to each connected component.
3Insight 3: Removing a node from an initial set has a significant impact only if that node is the *only* infected node in its connected component. In that case, the entire connected component is saved from infection.
4Insight 4: When choosing which node to remove, prioritize those within connected components having only one infected node and select the node associated with the largest component size.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: The graph is fully disconnected. In this case, each node is its own connected component, and removing any infected node will only save that node itself. The algorithm will return the smallest index among the initial infected nodes.
Edge case 2: All nodes are connected and initially infected. In this case, removing any node will have no effect on the final number of infected nodes (since they will all still be infected). The algorithm will return the smallest index among the initial infected nodes.
Edge case 3: Initial is empty. The problem statement says `1 <= initial.length <= n`, so this is not a valid edge case. The provided solution assumes `initial` is never empty, so an empty input for `initial` would lead to incorrect behaviour.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the `initial` array. The problem specifies that if multiple nodes result in the same minimum infected nodes, the node with the smallest index should be returned. Sorting `initial` ensures this condition is met.

✗Common mistake 2: Not considering the case where a connected component has multiple initially infected nodes. Removing one of them in that case will *not* prevent the spread of malware to that component, as others will still trigger infection. The algorithm correctly handles this by only saving the component size if the count of infected nodes is exactly 1.

✗Common mistake 3: Not freeing allocated memory in C, leading to memory leaks. The C version should have `free(parent)`, `free(sz)` and `free(infected_counts)`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network security. Identifying critical nodes in a computer network that, if compromised, could lead to widespread infection. The algorithm could help determine which nodes to protect most aggressively to minimize the overall impact of a potential malware outbreak.

🏦Real-world scenario 2: Epidemiology. Modeling the spread of a disease in a population. The graph represents connections between individuals (e.g., social contacts). Identifying individuals whose removal (e.g., quarantine) would most effectively limit the spread of the disease.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Minimize Malware Spread"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?