Graph Traversal

1. Number of Islands (200)

1. Problem Description and Leetcode Link: The problem is called "Number of Islands" and the link to the problem on LeetCode is: https://leetcode.com/problems/number-of-islands/

Given a 2D grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example: Input: 11110 11010 11000 00000

Output: 1

1. Optimized Java Code with Detailed Comments:

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int numRows = grid.length;
        int numCols = grid[0].length;
        int numIslands = 0;
        
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return numIslands;
    }
    
    private void dfs(char[][] grid, int row, int col) {
        int numRows = grid.length;
        int numCols = grid[0].length;
        
        // Check if the current cell is out of bounds or not a part of the island
        if (row < 0 || col < 0 || row >= numRows || col >= numCols || grid[row][col] == '0') {
            return;
        }
        
        // Mark the current cell as visited (water)
        grid[row][col] = '0';
        
        // Explore adjacent cells (horizontal and vertical)
        dfs(grid, row + 1, col); // Down
        dfs(grid, row - 1, col); // Up
        dfs(grid, row, col + 1); // Right
        dfs(grid, row, col - 1); // Left
    }
}

1. Detailed Description of Algorithm and Thinking Process: The problem of counting the number of islands can be solved using a popular graph traversal algorithm called Depth-First Search (DFS). The idea is to traverse through the grid, and whenever we encounter a land cell (marked as '1'), we explore its adjacent cells using DFS to find the connected component (island) formed by that cell.

Here's how the algorithm works:

1. First, we check if the grid is empty or null. If it is, we return 0 as there are no islands.

2. We initialize variables for the number of rows, number of columns, and the number of islands.

3. We iterate over each cell of the grid and check if it is land ('1') or water ('0'). If it is land, we increment the island count by 1 and perform a DFS on the current cell.

4. The DFS function takes the current cell's row and column indices as inputs. It checks if the cell is out of bounds or if it is water ('0'). If either condition is true, it returns and stops the recursion.

5. If the cell is part of an island ('1'), we mark it as visited by changing its value to '0'.

6. We then recursively call the DFS function on the four adjacent cells: up, down, left, and right. This ensures that we explore the entire connected component (island) formed by the initial land cell.

7. Finally, we return the island count as the result.

During interviews, it is crucial to explain the algorithm step by step, describing the purpose of each code block and why it is necessary. Emphasize the use of DFS to explore the grid and find connected land cells. Also, mention the importance of marking visited cells as '0' to avoid counting them again. It's always a good idea to test the code with different examples to ensure its correctness and explain the time and space complexity. In this case, the time complexity of the algorithm is O(MN), where M and N are the number of rows and columns in the grid, respectively. The space complexity is O(MN) as well, due to the implicit call stack during recursion.

2. Course Schedule (207)

1. Problem description and problem link: Problem: Course Schedule (207) Link: https://leetcode.com/problems/course-schedule/

Description: You are given a list of courses, where each course is represented by a pair of integers [courseId, prerequisiteId]. There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example, if prerequisites[i] = [a, b] this means you must take the course b before the course a.

Return true if it is possible to finish all courses, or false otherwise.

1. Optimized Java code with detailed comments:

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Step 1: Create an adjacency list to represent the graph
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // Step 2: Populate the adjacency list with prerequisite relationships
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            adjList.get(course).add(prerequisiteCourse);
        }
        
        // Step 3: Track the status of each course while performing DFS traversal
        int[] visited = new int[numCourses];
        
        // Step 4: Apply DFS traversal on each course
        for (int course = 0; course < numCourses; course++) {
            if (visited[course] == 0 && hasCycle(adjList, visited, course)) {
                return false; // Cycle detected, not possible to finish all courses
            }
        }
        
        return true; // No cycle detected, possible to finish all courses
    }
    
    private boolean hasCycle(List<List<Integer>> adjList, int[] visited, int course) {
        visited[course] = 1; // Mark the course as visiting
        
        // Perform DFS traversal on prerequisites of current course
        for (int prerequisiteCourse : adjList.get(course)) {
            if (visited[prerequisiteCourse] == 1) {
                return true; // Cycle detected
            } else if (visited[prerequisiteCourse] == 0 && hasCycle(adjList, visited, prerequisiteCourse)) {
                return true; // Cycle detected in the prerequisite DFS traversal
            }
        }
        
        visited[course] = -1; // Mark the course as visited
        
        return false; // No cycle detected for the current course
    }
}

1. Description on the algorithm and interview process:

The problem "Course Schedule" can be solved using graph traversal, specifically Depth First Search (DFS). The goal is to determine if there exists a cycle in the directed graph formed by the course prerequisites.

To solve the problem, we can follow the steps below:

1. Create an adjacency list to represent the graph: In the adjacency list, each course is represented by an index and the associated prerequisites are stored as adjacent nodes.

2. Populate the adjacency list with prerequisite relationships: Iterate over the prerequisites array and add the prerequisite courses to the adjacency list.

3. Track the status of each course: We need to keep track of the status of each course during the DFS traversal. We can use an array called "visited" for this purpose. Initially, all courses are marked as not visited (0).

4. Apply DFS traversal on each course: Iterate over the courses and for each unvisited course, perform a DFS traversal to check if there is a cycle. If a cycle is detected during the DFS traversal for any course, return false. Otherwise, return true.

During an interview, it's important to explain the overall approach to the problem and then dive into the details of each step. Interviewers often focus on evaluating the candidate's problem-solving skills and understanding of algorithms rather than just the code implementation. Therefore, it's vital to explain the algorithm using appropriate terminology and to demonstrate a clear thought process.

Additionally, it's beneficial to discuss the time and space complexity of the solution. The time complexity of this solution is 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, considering the adjacency list and the visited array.

Remember to test the code with different test cases and edge cases to ensure its correctness and efficiency.

3. Surrounded Regions (130)

Sure! Here is the optimized Java code for the LeetCode problem "Surrounded Regions" (130):

Problem Description: Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. The cells outside the surrounded regions should not be flipped.

Problem Link: https://leetcode.com/problems/surrounded-regions/

Java Code:

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        
        int rows = board.length;
        int cols = board[0].length;
        
        // Change all 'O' connected to 4 boundaries to *
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O')
                dfs(board, i, 0);
            if (board[i][cols-1] == 'O')
                dfs(board, i, cols - 1);
        }
        
        for (int j = 0; j < cols; j++) {
            if (board[0][j] == 'O')
                dfs(board, 0, j);
            if (board[rows-1][j] == 'O')
                dfs(board, rows - 1, j);
        }
        
        // Change all remaining 'O' to 'X' and all '*' to 'O'
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == '*')
                    board[i][j] = 'O';
            }
        }
    }
    
    private void dfs(char[][] board, int row, int col) {
        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != 'O')
            return;
        
        board[row][col] = '*';
        
        dfs(board, row - 1, col);
        dfs(board, row + 1, col);
        dfs(board, row, col - 1);
        dfs(board, row, col + 1);
    }
}

Explanation: The problem is solved by using a Depth-First Search (DFS) algorithm. The algorithm works as follows:

1. Check if the board is null or empty. If so, return.

2. Get the number of rows and columns in the board.

3. Traverse the first and last column and mark all 'O' cells and their connected 'O' cells as '*'.

4. Traverse the first and last row and mark all 'O' cells and their connected 'O' cells as '*'.

5. Traverse the entire board again, changing all remaining 'O' cells to 'X' and all '*' cells to 'O'.

During an interview, it's important to explain the algorithm step-by-step and highlight the key insights such as traversing the boundaries and marking the connected cells. Additionally, discussing the time and space complexity of the algorithm (which is O(rows * cols)) can also be beneficial.

4. Pacific Atlantic Water Flow (417)

1. Problem Description and Link: The problem "Pacific Atlantic Water Flow" is described as follows:

• Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific Ocean" touches the left and top edges of the matrix, and the "Atlantic Ocean" touches the right and bottom edges.

• Water can only flow in four directions: up, down, left, or right. Water flows from a cell to its neighboring cells with lower or equal heights.

• Return a list of grid coordinates where water can flow from the Pacific to the Atlantic, or vice versa.

Problem Link: https://leetcode.com/problems/pacific-atlantic-water-flow/

1. Optimized Java Code with Comments:

import java.util.*;

class Solution {
    
    // Global variables
    int[][] matrix;
    int m, n;
    
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> result = new ArrayList<>();
        
        // Check if the matrix is empty
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        
        // Assign the matrix and its dimensions
        this.matrix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        
        // Create boolean arrays to track the reachable cells from Pacific and Atlantic
        boolean[][] pacificReachable = new boolean[m][n];
        boolean[][] atlanticReachable = new boolean[m][n];
        
        // Traverse the top and bottom rows for Pacific Ocean
        for(int i = 0; i < m; i++) {
            dfs(i, 0, pacificReachable);
            dfs(i, n - 1, atlanticReachable);
        }
        
        // Traverse the left and right columns for Pacific Ocean
        for(int j = 0; j < n; j++) {
            dfs(0, j, pacificReachable);
            dfs(m - 1, j, atlanticReachable);
        }
        
        // Check all the cells and add the reachable ones from both oceans to the result
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        
        return result;
    }
    
    private void dfs(int i, int j, boolean[][] reachable) {
        // Mark current cell as reachable
        reachable[i][j] = true;
        
        // Define the four possible directions for water flow
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        
        // Explore each direction
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            
            // Check if the next cell is valid and not already reachable
            if(x >= 0 && x < m && y >= 0 && y < n && !reachable[x][y] && matrix[x][y] >= matrix[i][j]) {
                dfs(x, y, reachable);
            }
        }
    }
}

1. Algorithm Explanation:

• The problem can be solved with a depth-first search (DFS) approach.

• To approach this problem during an interview, start by understanding the problem requirements and constraints.

• Break down the problem into smaller sub-tasks. In this case, the sub-tasks are to determine the reachable cells from the Pacific Ocean and from the Atlantic Ocean.

• Create a boolean matrix to track the reachable cells from each ocean.

• Traverse the top and bottom rows, as well as the left and right columns, one by one, and mark each cell as reachable using the DFS algorithm.

• Finally, check all the cells and add the ones that are reachable from both oceans to the result list.

• During an interview, it is important to communicate your thoughts, explain the algorithm step by step, and discuss the time and space complexity of the solution.

5. Word Search II (212)

1. Problem Description:

The problem "Word Search II" (212) on LeetCode asks us to find all the words from a given list in a given two-dimensional board of letters. We can move in any of the four directions (up, down, left, or right) to form a word. The output should be a list of all the words that can be found in the board.

LeetCode Link to the problem: Word Search II

1. Optimized Java Solution with Detailed Comments:

class Solution {

    // Trie node data structure
    class TrieNode {
        TrieNode[] children;
        String word;

        TrieNode() {
            children = new TrieNode[26];
            word = null;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        
        // Construct the trie using words from the input
        TrieNode root = buildTrie(words);
        
        // Traverse each cell in the board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // Call the backtracking method for each cell
                backtrack(board, i, j, root, result);
            }
        }
        
        return result;
    }

    // Method to build the trie data structure
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        
        // Traverse each word in the input array
        for (String word : words) {
            TrieNode current = root;
            
            // Insert each character of the word into the trie
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                
                // Create a new node if it doesn't exist for the character
                if (current.children[index] == null) {
                    current.children[index] = new TrieNode();
                }
                
                // Move to the next node
                current = current.children[index];
            }
            
            // Set the word field of the leaf node to the current word
            current.word = word;
        }
        
        return root;
    }

    // Backtracking algorithm to find words in the board
    private void backtrack(char[][] board, int i, int j, TrieNode node, List<String> result) {
        char currentChar = board[i][j];
        
        // Check if the current character is already visited or doesn't exist in the trie
        if (currentChar == '#' || node.children[currentChar - 'a'] == null) {
            return;
        }
        
        // Move to the next node in the trie
        node = node.children[currentChar - 'a'];
        
        // Check if a word is found
        if (node.word != null) {
            result.add(node.word);
            // Set the word field of the leaf node to null to avoid duplicates
            node.word = null;
        }
        
        // Mark the current cell as visited
        board[i][j] = '#';
        
        // Explore the neighbors of the current cell
        if (i > 0) {
            backtrack(board, i - 1, j, node, result); // Up
        }
        if (j > 0) {
            backtrack(board, i, j - 1, node, result); // Left
        }
        if (i < board.length - 1) {
            backtrack(board, i + 1, j, node, result); // Down
        }
        if (j < board[0].length - 1) {
            backtrack(board, i, j + 1, node, result); // Right
        }
        
        // Restore the current cell after backtracking
        board[i][j] = currentChar;
    }
}

1. Algorithm and Interview Thought Process:

The given problem can be solved using a backtracking algorithm along with a trie data structure. The backtracking algorithm is used to traverse each cell of the board, while the trie data structure helps in efficient word searching.

During an interview, here are the steps you can follow to approach and solve this type of problem:

• Understand the problem statement completely and ask any clarifying questions if necessary.

• Identify the key components of the problem and consider possible data structures to use. In this problem, the key components are the board and the list of words.

• Think about how a trie data structure can be useful to speed up the process of word search on the board.

• Implement the trie data structure and the backtracking algorithm.

• During the implementation, pay attention to the control flow and ensure that all the required conditions are properly handled.

• Test your implementation with different test cases, including edge cases, to validate its correctness and efficiency.

• Optimize the solution if possible by identifying any redundant or unnecessary steps in the code.

• Discuss the time complexity and space complexity of the solution, highlighting any trade-offs made.

• Be prepared to explain your thought process and walk through the code during the interview. Provide clear and concise explanations, focusing on the algorithm's logic and how it solves the problem efficiently.

By following this approach and understanding the optimization techniques involved, you will be able to solve the "Word Search II" problem on LeetCode effectively.

1. Reorder Routes to Make All Paths Lead to the City Zero

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Solution:

import java.util.*;

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] connection : connections) {
            int u = connection[0];
            int v = connection[1];
            graph.get(u).add(new int[]{v, 1}); // road from u to v
            graph.get(v).add(new int[]{u, 0}); // reversed road from v to u
        }
        return dfs(0, -1, graph);
    }
    
    private int dfs(int node, int parent, List<List<int[]>> graph) {
        int count = 0;
        for (int[] neighbor : graph.get(node)) {
            int v = neighbor[0];
            int isForward = neighbor[1];
            if (v != parent) {
                count += isForward + dfs(v, node, graph);
            }
        }
        return count;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 6;
        int[][] connections = {{0,1},{1,3},{2,3},{4,0},{4,5}};
        System.out.println(solution.minReorder(n, connections)); // Output should be 3
    }
}

Explaination:

1. Building the Graph:

   • We start by constructing an adjacency list representation of the tree. The graph is represented using a list of lists (List<List<int[]>>). Each index in the list represents a city, and each element of the inner list represents an edge from that city to its neighboring cities. Each edge is represented by an array of size 2, containing the neighbor city and a flag indicating whether the edge is in the original direction (1) or reversed (0).

2. Depth-First Search (DFS):

   • We perform a depth-first search (DFS) starting from city 0, recursively visiting each city and its neighbors.

   • During the DFS traversal, we keep track of the number of edges that need to be reversed to reach city 0. We maintain a count variable initialized to 0.

   • At each step, when visiting a neighbor of the current city, we check whether the edge is in the original direction or reversed. If it's in the original direction (flag = 1), we increment the count by 1 because we need to reverse this edge to travel towards city 0.

   • We continue this process until we traverse all cities reachable from city 0.

3. Returning the Minimum Number of Edges Changed:

   • After the DFS traversal is complete, the count variable holds the total number of edges that need to be reversed to reach city 0 from all other cities.

   • We return this count as the minimum number of edges that need to be changed to enable every city to visit city 0.

4. Main Method:

   • In the main method, we create an instance of the Solution class and call the minReorder method with the provided parameters (number of cities n and the array of connections).

   • We then print the result obtained from the minReorder method.

Overall, the solution utilizes DFS to traverse the tree and counts the number of edges that need to be reversed to ensure that every city can visit city 0. It returns the minimum number of edges that need to be changed for this purpose.

Other solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // Build the directed graph
        for (int[] connection : connections) {
            graph.get(connection[0]).add(connection[1]);
            graph.get(connection[1]).add(-connection[0]); // Mark reverse edge with a negative value
        }

        return dfs(graph, 0, new boolean[n]);
    }

    private int dfs(List<List<Integer>> graph, int node, boolean[] visited) {
        int changeCount = 0;
        visited[node] = true;

        for (int neighbor : graph.get(node)) {
            if (!visited[Math.abs(neighbor)]) {
                // If the edge is positive, it means we need to reverse it
                changeCount += (neighbor > 0) ? 1 : 0;
                changeCount += dfs(graph, Math.abs(neighbor), visited);
            }
        }

        return changeCount;
    }
}

BFS solution:

class Solution {
  public int minReorder(int n, int[][] connections) {
    LinkedList<int[]>[] g = new LinkedList[n];
    for(int i = 0; i != n; ++i) g[i] = new LinkedList<>();  //create graph   
    for(int[] c: connections){             //put all edges 
      g[c[0]].add(new int[]{c[1], 1});     //index[1] == 1 - road is present
      g[c[1]].add(new int[]{c[0], 0});     //index[1] == 0 - road is absent
    }  

    int[] vis = new int[n];
    int reorderRoads = 0;
    LinkedList<Integer> q = new LinkedList<>();             //queue for BFS
    q.add(0);
    while(! q.isEmpty()){                                   //BFS  
      int city = q.poll();
      if(vis[city] == 1) continue;
      vis[city] = 1;

      for(int[] neib: g[city])
        if(vis[neib[0]] == 0){
          q.add(neib[0]);
          if(neib[1] == 1) ++reorderRoads;
        }
    }

    return reorderRoads;
  }
}