Topological Sorting

21. Course Schedule (207)

1. The problem "Course Schedule" can be found on LeetCode at the following link: https://leetcode.com/problems/course-schedule/

2. Here is the optimized Java code for the problem "Course Schedule (207)" with detailed comments:

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Build an adjacency list to store the prerequisite relationships
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // Populate the adjacency list
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            graph.get(course).add(prerequisiteCourse);
        }

        // Track the visited state of each course during DFS
        int[] visited = new int[numCourses];

        // Check for cycle in each course
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(graph, i, visited)) {
                return false;
            }
        }

        return true;
    }

    private boolean hasCycle(List<List<Integer>> graph, int course, int[] visited) {
        // If a course is being visited in the current DFS traversal, there is a cycle
        if (visited[course] == 1) {
            return true;
        }

        // If a course has already been visited in a previous DFS traversal, no cycle
        if (visited[course] == -1) {
            return false;
        }

        // Mark the current course as visited
        visited[course] = 1;

        // Traverse all prerequisite courses of the current course
        for (int prerequisiteCourse : graph.get(course)) {
            if (hasCycle(graph, prerequisiteCourse, visited)) {
                return true;
            }
        }

        // Mark the current course as visited in previous DFS traversal
        visited[course] = -1;

        return false;
    }
}

1. The algorithm used in this solution is based on the concept of topological sorting and cycle detection in a directed graph.

During an interview, you can explain the following approach to solve the problem:

• Build an adjacency list to represent the prerequisite relationships between courses.

• Use a depth-first search (DFS) approach to check for the presence of a cycle in the graph.

• For each course, recursively visit its prerequisite courses and mark them as visited.

• If a course is already visited during the current DFS traversal, it indicates the presence of a cycle and the dependencies cannot be satisfied.

• If a course has been visited in a previous DFS traversal, it means that there is no cycle and the course can be taken.

• The DFS continues until all courses have been visited.

• If a cycle is detected during the DFS traversal, the algorithm terminates and returns false, indicating that it is not possible to finish all courses.

• Otherwise, if the DFS traversal completes without detecting any cycles, the algorithm returns true, indicating that it is possible to finish all courses.

This approach has a time complexity of O(V + E), where V is the number of courses and E is the number of prerequisites. The space complexity is O(V + E) as well, due to the use of the adjacency list and the visited array.

By explaining the algorithm and thought process behind it, you can demonstrate your understanding of the problem and your ability to work with graph-related problems efficiently.

22. Alien Dictionary (269)

1. Problem Description: The Alien Dictionary problem (https://leetcode.com/problems/alien-dictionary/) asks us to determine the order of characters in an alien language based on a given list of words. Each word is sorted lexicographically, and we need to derive the character order from the given words.

2. Optimized Java Code with Detailed Comments:

import java.util.*;

class AlienDictionary {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        
        // Step 1: Create a hashmap to store the adjacency list
        HashMap<Character, List<Character>> adjList = new HashMap<>();
        
        // Step 2: Create a map to keep track of the indegree of each character
        HashMap<Character, Integer> indegree = new HashMap<>();
        
        // Step 3: Initialize the indegree map with all characters seen in the words
        for (String word : words) {
            for (char c : word.toCharArray()) {
                indegree.put(c, 0);
                adjList.put(c, new ArrayList<>());
            }
        }
        
        // Step 4: Build the adjacency list and update the indegree map
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            
            // check if word2 is a prefix of word1, in which case the order is invalid
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return "";
            }
            
            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                char parent = word1.charAt(j);
                char child = word2.charAt(j);
                
                // if we found a different character at the current index, update the adjacency list and indegree map
                if (parent != child) {
                    adjList.get(parent).add(child);
                    indegree.put(child, indegree.get(child) + 1);
                    break;
                }
            }
        }
        
        // Step 5: Perform topological sort to determine the character order
        StringBuilder charOrder = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        
        for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        
        while (!queue.isEmpty()) {
            char curr = queue.poll();
            charOrder.append(curr);
            
            for (char neighbor : adjList.get(curr)) {
                indegree.put(neighbor, indegree.get(neighbor) - 1);
                
                if (indegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // Step 6: Check if there is a cycle in the graph (invalid character order)
        if (charOrder.length() != indegree.size()) {
            return "";
        }
        
        return charOrder.toString();
    }
}

1. Detailed Description and Algorithm Walkthrough:

The Alien Dictionary problem requires us to determine the order of characters in an alien language based on a given list of words. To solve this problem, we can use a graph-based approach and perform a topological sort on the characters.

Algorithm:

1. Create a hashmap to store the adjacency list of the characters. Each character will be mapped to a list of characters it precedes.

2. Create another hashmap to keep track of the indegree of each character. Initialize the indegree of each character to 0.

3. Scan through the words and add all characters to both the adjacency list and indegree map.

4. Build the adjacency list and update the indegree map by comparing adjacent words. For each character at a particular index, if the characters differ, add an edge from the parent character to the child character (in the adjacency list) and increment the indegree of the child.

5. Perform a topological sort starting with all characters with an indegree of 0. Using a queue, enqueue these characters and process them one by one. While processing a character:

   • Append it to the character order.

   • For each neighbor, decrement its indegree.

   • If an adjacent character's indegree becomes 0, enqueue it.

6. After the topological sort is complete, check if the length of the character order matches the total number of characters in the indegree map. If they differ, it means there was a cycle in the graph, and we cannot determine the character order. In this case, return an empty string.

7. If the character order is valid, return it as a string.

By following this algorithm, we can determine the order of characters in the given alien language. This solution has a time complexity of O(N), where N is the total number of characters in the input.

23. Course Schedule II (210)

1. Problem Description:

The problem is called "Course Schedule II" and can be found on LeetCode using the following link: https://leetcode.com/problems/course-schedule-ii/.

In this problem, you are given a list of courses labeled from 0 to numCourses - 1 and a list of prerequisite pairs. You need to return the order in which you should take the courses in order to complete all of them. If it is impossible to finish all the courses, return an empty array.

1. Optimized Java Code:

Here is the optimized Java code for solving the "Course Schedule II" problem with detailed comments:

import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Create adjacency list to represent the graph
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // Build the graph from prerequisites
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            adjList.get(prerequisiteCourse).add(course);
        }
        
        // Create visited array to track visited nodes during DFS
        boolean[] visited = new boolean[numCourses];
        // Create stack for DFS traversal
        Stack<Integer> stack = new Stack<>();
        
        // Perform DFS on each unvisited course
        for (int course = 0; course < numCourses; course++) {
            if (!visited[course]) {
                performDFS(course, adjList, visited, stack);
            }
        }
        
        // If there are any back edges, it means a cycle exists
        // and it is not possible to finish all the courses
        if (stack.size() != numCourses) {
            return new int[0];
        }
        
        // Generate the course order from the stack (topological order)
        int[] courseOrder = new int[numCourses];
        int i = 0;
        while (!stack.isEmpty()) {
            courseOrder[i++] = stack.pop();
        }
        
        return courseOrder;
    }
    
    private void performDFS(int course, List<List<Integer>> adjList, boolean[] visited, Stack<Integer> stack) {
        visited[course] = true;
        
        for (int prerequisiteCourse : adjList.get(course)) {
            if (!visited[prerequisiteCourse]) {
                performDFS(prerequisiteCourse, adjList, visited, stack);
            }
        }
        
        stack.push(course);
    }
}

1. Algorithm Explanation:

To solve this problem, we need to find a valid order in which to take the courses based on the given prerequisites. We can approach this problem using a depth-first search (DFS) algorithm.

The algorithm starts by building an adjacency list from the given prerequisites. Each course is represented as a node in the graph, and the prerequisites are represented as edges between the nodes. The adjacency list helps us quickly access the prerequisite courses for each course.

The algorithm then performs a depth-first search starting from each unvisited course. During the DFS, we mark the visited courses and recursively traverse through their prerequisite courses. The DFS ensures that we explore all possible paths in the graph.

If there is a back edge found during the DFS traversal, it means that a cycle exists in the graph. In this case, it is not possible to finish all the courses, so we return an empty array.

If there is no cycle in the graph, we generate the course order from the stack used in the DFS. The stack contains the courses in reverse topological order. We pop the courses from the stack and store them in the course order array.

Finally, we return the course order array as the solution to the problem.

During the interview process, it is important to understand the problem requirements and constraints before starting to write the code. It is also crucial to think about the problem from different angles and come up with different algorithmic approaches. Discussing the approach and the trade-offs with the interviewer can help showcase your problem-solving skills and demonstrate your understanding of the problem.

24. Sequence Reconstruction (444)

1. Problem Description and LeetCode Link: The problem "Sequence Reconstruction" (444) on LeetCode involves reconstructing a sequence from a given set of sequences and checking if it is the unique or valid topological order of a directed graph. The problem link is: https://leetcode.com/problems/sequence-reconstruction/

2. Optimized Java Code with Detailed Comments:

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        // Step 1: Create the adjacency list for the graph
        Map<Integer, List<Integer>> adjList = new HashMap<>();

        // Step 2: Create the indegree array for the graph
        int[] indegree = new int[org.length + 1];

        // Step 3: Populate the adjacency list and indegree array
        for (List<Integer> seq : seqs) {
            if (seq.size() == 1) {
                // If the sequence has only one element, add it to the adjacency list
                if (!adjList.containsKey(seq.get(0))) {
                    adjList.put(seq.get(0), new ArrayList<>());
                }
            } else {
                // Add the edges to the adjacency list and update the indegree array
                for (int i = 0; i < seq.size() - 1; i++) {
                    int from = seq.get(i);
                    int to = seq.get(i + 1);

                    if (!adjList.containsKey(from)) {
                        adjList.put(from, new ArrayList<>());
                    }
                    adjList.get(from).add(to);
                    indegree[to]++;
                }
            }
        }

        // Step 4: Check if the org sequence is valid
        if (org.length != adjList.size()) {
            return false; // If the size of org is not equal to the number of nodes in the graph, it is invalid
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int num : org) {
            if (indegree[num] == 0) {
                // Add nodes with indegree 0 to the queue
                queue.add(num);
            }
        }

        int index = 0;
        int count = 0;

        // Step 5: Topological sorting algorithm
        while (!queue.isEmpty()) {
            if (queue.size() > 1) {
                return false; // If more than one element has indegree 0, the org sequence is not unique
            }
            
            int curr = queue.poll();
            if (curr != org[index++]) {
                return false; // If the current node does not match the corresponding element in org, it's invalid
            }
            
            count++;
            
            // Remove the current node and update the indegree array
            if (adjList.containsKey(curr)) {
                for (int neighbor : adjList.get(curr)) {
                    indegree[neighbor]--;
                    if (indegree[neighbor] == 0) {
                        queue.add(neighbor);
                    }
                }
            }
        }

        // Step 6: Check if the entire org sequence is valid and unique
        return count == org.length;
    }
}

1. Detailed Description and Approach: The problem can be tackled using the topological sorting algorithm and graph theory concepts. The goal is to check if the given org sequence is a valid and unique topological order of a directed graph based on the given set of sequences.

The steps involved in solving the problem are as follows:

1. Create an adjacency list to represent the graph. Each node will be a key in the map, and its corresponding value will be a list of its neighbors.

2. Create an indegree array to represent the count of incoming edges for each node in the graph.

3. Populate the adjacency list and indegree array while processing each of the given sequences.

4. Check if the size of the org sequence matches the number of nodes in the graph. If not, return false.

5. Perform a topological sorting algorithm using a queue. Add all nodes with an indegree of 0 to the queue. Iterate through the queue and remove each node, updating the indegree array and adding new nodes with an indegree of 0 to the queue as necessary. Verify that each removed node matches the corresponding element in the org sequence. If not, return false. If more than one element has an indegree of 0, return false as well.

6. Finally, check if all elements in the org sequence have been processed. If the count matches the length of the org sequence, return true. Otherwise, return false.

During an interview, it is important to understand the problem requirements, break down the problem into smaller steps, and explain the algorithm and the reasoning behind it step by step. By following this approach and providing a well-commented code solution, you can demonstrate your problem-solving skills and your ability to think through complex algorithms.

25. Minimum Height Trees (310)

1. Problem Description and Problem Link: The problem "Minimum Height Trees (310)" on Leetcode asks us to find the minimum height trees in a given undirected graph. The problem link is as follows: https://leetcode.com/problems/minimum-height-trees/

2. Optimized Java code for Minimum Height Trees (310):

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Collections.singletonList(0);
        }

        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new HashSet<>());
        }

        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (adj.get(i).size() == 1) {
                leaves.add(i);
            }
        }

        while (n > 2) {
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = adj.get(leaf).iterator().next();
                adj.get(neighbor).remove(leaf);
                if (adj.get(neighbor).size() == 1) {
                    newLeaves.add(neighbor);
                }
            }
            leaves = newLeaves;
        }

        return leaves;
    }
}

1. Detailed Explanation and Algorithm Thinking Process:

During an interview, it is important to approach this problem effectively and efficiently. Below is a step-by-step algorithm to solve the problem "Minimum Height Trees":

• To find the minimum height trees, we need to identify the "centroid" of the given undirected graph. The centroid is defined as a node that, when removed, splits the remaining graph into trees of equal or almost equal heights. Since the input graph can have multiple centroids, we need to find all the possible centroids.

• First, we handle some special cases. If the given graph has only one node (n = 1), then the centroid itself is the minimum height tree. So, we return [0].

• Next, we initialize an adjacency list adj, which is a list of sets representing the graph. We populate this list by iterating through the given array edges. For each edge (u, v), we add v to the adjacency list of u and vice versa. This creates an undirected graph representation.

• Then, we need to identify leaves of the graph with only one neighbor. We initialize an empty list called leaves. We iterate through all the nodes from 0 to n-1. For each node, if the size of its adjacency set is 1, then it is a leaf, so we add it to the leaves list.

• Now, we need to prune the leaves from the graph until we are left with only the centroid(s). We repeat the following steps while the number of nodes in the graph is greater than 2:

  • Reduce n by the number of leaves.

  • Initialize an empty list called newLeaves to store the next level of leaves.

  • Iterate through each leaf in the leaves list:

    • Get its only neighbor using adj.get(leaf).iterator().next().

    • Remove the current leaf from its neighbor's adjacency set.

    • If the size of the neighbor's adjacency set becomes 1, then it becomes a new leaf, so we add it to the newLeaves list.

  • Update the leaves list to contain the new leaves.

• Finally, we return the leaves list, which contains the centroid(s) of the graph.

This algorithm has a time and space complexity of O(n), where n is the number of nodes in the graph, as we iterate through all the nodes and edges of the graph.