Connected Components

36. Number of Connected Components in an Undirected Graph (323)

1. Problem Description: "Number of Connected Components in an Undirected Graph"

The problem asks us to find the number of connected components in an undirected graph. The graph is represented as an edge list, where each element is a pair [u, v] representing an undirected edge connecting nodes u and v. The graph may contain self-loops and multiple edges between the same pair of nodes.

We need to return the number of connected components in the graph.

LeetCode Link: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

1. Optimized Java Code:

class Solution {
    public int countComponents(int n, int[][] edges) {
        // Step 1: Build the adjacency list representation of the graph
        List<List<Integer>> adjList = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }
        
        // Step 2: Initialize visited array to keep track of visited nodes
        boolean[] visited = new boolean[n];
        
        // Step 3: Perform DFS from each unvisited node and count number of components
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(adjList, visited, i);
                count++;
            }
        }
        
        return count;
    }
    
    private void dfs(List<List<Integer>> adjList, boolean[] visited, int node) {
        visited[node] = true;
        
        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfs(adjList, visited, neighbor);
            }
        }
    }
}

1. Algorithm Explanation:

The problem can be solved using Depth-First Search (DFS) algorithm.

We first build the adjacency list representation of the graph. Then, we initialize a visited array to keep track of the visited nodes.

Next, we perform DFS from each unvisited node and increment the count of components whenever a new connected component is encountered. In the DFS algorithm, we mark the current node as visited and recursively visit all its unvisited neighbors. This process ensures that we explore all nodes in the connected component.

Finally, we return the count of connected components.

During an interview, it is important to mention the approach and show understanding of graph theory concepts. Explaining the step-by-step process and complexity analysis would also help showcase problem-solving skills.

37. Friend Circles (547)

1. The problem "Friend Circles" can be found on LeetCode at the following link: https://leetcode.com/problems/friend-circles/

2. Here is the optimized Java code for the "Friend Circles" problem (547) on LeetCode, with detailed comments:

class Solution {
    public int findCircleNum(int[][] M) {
        int n = M.length; // number of students
        
        int count = 0; // count of friend circles
        
        boolean[] visited = new boolean[n]; // array to keep track of visited students
        
        // iterate through each student
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // if student i is not visited
                dfs(M, i, visited); // perform depth-first search for student i
                count++; // increment count of friend circles
            }
        }
        
        return count; // return the count of friend circles
    }
    
    private void dfs(int[][] M, int curr, boolean[] visited) {
        visited[curr] = true; // mark the current student as visited
        
        // iterate through each student
        for (int i = 0; i < M.length; i++) {
            if (M[curr][i] == 1 && !visited[i]) { // if student i is a friend of current student and is not visited
                dfs(M, i, visited); // perform depth-first search for student i
            }
        }
    }
}

1. Description of the algorithm and how to think through it during an interview process:

The problem "Friend Circles" can be approached using a graph traversal algorithm called depth-first search (DFS). Each student represents a node in the graph, and there is an edge between two students if they are friends. The goal is to count the number of friend circles in the given matrix, where a friend circle consists of a group of students who are directly or indirectly connected.

To solve this problem during an interview, follow these steps:

• Create a variable count to keep track of the number of friend circles.

• Create a boolean array visited to keep track of the visited status of each student. Initially, all elements of visited are set to false.

• Iterate through each student in the given matrix using a for loop.

  • If the student is not visited, perform depth-first search (DFS) starting from that student. In the DFS function, mark the current student as visited and recursively explore its friends. Increment count after the DFS function completes, as it means a new friend circle has been found. This ensures that every student is visited and included in a friend circle.

• Return the count, which represents the number of friend circles.

During the implementation, it is important to write clear and concise code with proper variable and function names. Adding comments to clarify the purpose of the code and provide additional details will also improve the understanding of the code during an interview.

38. Accounts Merge (721)

1. Problem description and link: The problem "Accounts Merge" can be found on LeetCode using the following link: https://leetcode.com/problems/accounts-merge/

2. Optimized Java code for "Accounts Merge" with detailed comments:

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        // Create a map to store email-to-name relation
        Map<String, String> emailToName = new HashMap<>();
        // Create a map to store email-to-email relation
        Map<String, String> emailToEmail = new HashMap<>();

        // Traverse through the given accounts
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                emailToName.put(email, name);
                emailToEmail.put(email, email);
            }
        }

        // Perform union find to merge the accounts
        UnionFind uf = new UnionFind(emailToEmail.keySet());
        for (String email : emailToEmail.keySet()) {
            String parentEmail = uf.find(email);
            String representativeEmail = emailToEmail.get(parentEmail);
            uf.union(email, representativeEmail);
        }

        // Create a map to store the merged accounts
        Map<String, List<String>> mergedAccounts = new HashMap<>();
        for (String email : emailToEmail.keySet()) {
            String parentEmail = uf.find(email);
            mergedAccounts.computeIfAbsent(parentEmail, k -> new ArrayList<>()).add(email);
        }

        // Create the output list by combining the name and merged emails
        List<List<String>> combinedAccounts = new ArrayList<>();
        for (List<String> emails : mergedAccounts.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<>();
            account.add(name);
            account.addAll(emails);
            combinedAccounts.add(account);
        }

        return combinedAccounts;
    }

    // UnionFind data structure implementation
    class UnionFind {
        private Map<String, String> parent;

        public UnionFind(Set<String> elements) {
            parent = new HashMap<>();
            for (String element : elements) {
                parent.put(element, element);
            }
        }

        public String find(String element) {
            if (!parent.get(element).equals(element)) {
                parent.put(element, find(parent.get(element)));
            }
            return parent.get(element);
        }

        public void union(String element1, String element2) {
            parent.put(find(element1), find(element2));
        }
    }
}

1. Detailed description of the algorithm and interview approach: The problem "Accounts Merge" can be solved using the Union-Find data structure. The main idea is to merge accounts that share at least one email address.

To solve this problem, we can follow these steps:

• Create two maps, emailToName and emailToEmail, to store the relations between emails and names, and emails and emails, respectively.

• Traverse through the given accounts and populate the maps.

• Perform a union find on the email-to-email relation map to merge the accounts that share common email addresses. Here, we initialize a UnionFind data structure with the set of unique email addresses.

• Iterate through the email-to-email map and find the representative email for each email. Then, perform a union operation to merge the emails.

• Create a map, mergedAccounts, to store the merged accounts.

• Iterate through the email-to-email map again and find the parent email for each email using the UnionFind data structure. Add the email to the corresponding merged account in the mergedAccounts map.

• Create the final output by sorting the emails within each merged account, retrieving the corresponding name using the emailToName map, and combining them into a list.

• Return the list of combined accounts.

During an interview process, it is important to have a clear understanding of the problem and the specified input/output format. It is also crucial to explain the chosen algorithm, such as Union-Find in this case, and walk through the code with detailed comments. Handling edge cases and discussing the runtime and space complexity analysis is also recommended.

39. Redundant Connection (684)

1. Problem description:

The problem "Redundant Connection" (LeetCode #684) states that given an undirected graph, we need to find and remove an edge that causes the graph to become a tree. If there are multiple answers, we can remove any of them. The input will be in the form of an array where each element represents an edge and its two vertices.

Link to the problem: https://leetcode.com/problems/redundant-connection/

1. Optimized Java code for "Redundant Connection" (684) with detailed comments:

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1]; // parent array to store the parent of each node
        for (int i = 1; i <= n; i++) {
            parent[i] = i; // initially, each node is its own parent
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int parentU = findParent(parent, u); // find the parent of u
            int parentV = findParent(parent, v); // find the parent of v

            if (parentU == parentV) { // If the parent of u and v is same, it means an edge between u and v will create a cycle
                return edge; // Return the redundant edge
            }

            union(parent, parentU, parentV); // union the parent of u and v
        }

        return new int[2]; // If no redundant edge found, return empty array
    }

    private int findParent(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = findParent(parent, parent[x]); // path compression
        }
        return parent[x];
    }

    private void union(int[] parent, int u, int v) {
        int parentU = findParent(parent, u);
        int parentV = findParent(parent, v);
        parent[parentU] = parentV; // set parent of parentU as parentV
    }
}

1. Algorithm Explanation:

• We use a union-find algorithm to solve this problem.

• Initially, we assume each node is its own parent.

• For each edge, we find the parent of the two vertices and check if they have the same parent (i.e., in the same connected component).

• If they have the same parent, it means the edge will create a cycle in the graph.

• In this case, we return the current edge as the redundant edge, as removing it will make the graph a tree.

• Otherwise, we union the two vertices by setting the parent of the parent of one vertex to be the parent of the other vertex.

• Finally, if no redundant edge is found, we return an empty array.

During an interview, it is important to discuss the problem requirements, clarify any doubts or assumptions, and then propose and explain the optimized solution using appropriate data structures and algorithms.

40. Network Delay Time (743)

1. Problem Description: The problem "Network Delay Time (743)" is taken from Leetcode. The problem statement and link can be found here: https://leetcode.com/problems/network-delay-time/

2. Optimized Java Code with Detailed Comments:

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // Step 1: Create an adjacency list to represent the network
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : times) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            
            // If source node already exists, add the destination node and weight to its adjacency list
            if (!graph.containsKey(u)) {
                graph.put(u, new ArrayList<>());
            }
            graph.get(u).add(new int[]{v, w});
        }
        
        // Step 2: Create a priority queue to store the nodes to be visited
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, K}); // distance from K to K is 0
        
        // Step 3: Create a distance array to store the minimum distances
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        
        // Step 4: Perform Dijkstra's algorithm
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currNode = curr[1];
            int currDist = curr[0];
            
            // If the current distance is greater than the distance already stored, skip
            if (currDist > dist[currNode]) {
                continue;
            }
            
            // Traverse all neighbors of the current node
            if (graph.containsKey(currNode)) {
                for (int[] neighbor : graph.get(currNode)) {
                    int neighborNode = neighbor[0];
                    int neighborDist = neighbor[1];
                    
                    // Update the distance if a shorter path is found
                    if (currDist + neighborDist < dist[neighborNode]) {
                        dist[neighborNode] = currDist + neighborDist;
                        pq.offer(new int[]{dist[neighborNode], neighborNode});
                    }
                }
            }
        }
        
        // Step 5: Find the maximum distance from the source node to any other node
        int maxDist = 0;
        for (int i = 1; i <= N; i++) {
            maxDist = Math.max(maxDist, dist[i]);
        }
        
        // Step 6: Check if there exists a node that is not reachable from the source node
        if (maxDist == Integer.MAX_VALUE) {
            return -1;
        }
        
        return maxDist;
    }
}

1. Detailed Description of the Algorithm and Thought Process during an Interview:

   • The problem is a variation of the Dijkstra's algorithm, which is commonly used to find the shortest path in a weighted graph.

   • The goal is to find the minimum time needed to send a signal from a source node to all other nodes in the network.

   • To solve this problem, we can use Dijkstra's algorithm to find the shortest path from the source node to all other nodes.

   • The steps to solve the problem are as follows:

     1. Create an adjacency list to represent the network. Each node is associated with a list of its neighbors and the corresponding weights.

     2. Create a priority queue to store the nodes to be visited. The priority queue is sorted based on the distance from the source node. Initially, add the source node with a distance of 0.

     3. Create a distance array to store the minimum distances from the source node to each node. Initialize all distances to infinity, except for the source node which is set to 0.

     4. Perform Dijkstra's algorithm:

        • While the priority queue is not empty, remove the node with the smallest distance from the priority queue.

        • Traverse all neighbors of the current node and update their distances if a shorter path is found. Add the updated neighbors to the priority queue.

     5. Find the maximum distance from the source node to any other node. This represents the minimum time needed to send a signal to all other nodes.

     6. If there exists a node that is not reachable from the source node, return -1. Otherwise, return the maximum distance calculated in step 5.

   • It's important to explain and discuss the time and space complexity of the algorithm during the interview. The time complexity of this algorithm is O((E + V) log V), where E is the number of edges and V is the number of vertices. The space complexity is O(V), where V is the number of vertices.