Graphs/Trees Coding Questions

LiveRunGrow

81 min readMay 30, 2020

Recap on Java basics for coding interview

1. Basic class code

medium.com

int graph [][]={{1,1,1,1,0},{1,1,0,1,0},{1,1,0,0,0},{0,0,0,0,0}};

顶点 ding dian： Nodes

边: Edge (这条边)

访问 Visit

且相领顶点 qie xiang ling ding dian 不能染相同的颜色：Neighbouring nodes cannot be coloured the same

深度优先搜索: Depth First Search

广度优先搜索: Breadth First Search

Important Algorithms/Data Structures and their complexity

BFS & DFS

Fail in a graph with more than 1 connected component
O(V+E). O(V) is because each vertex is added to the queue once. After it is added, it will be marked as visited and not added again. O(E) is because each list of neighbours is enumerated once when V is removed from the queue.
BFS uses queue and DFS uses stack
DFS on a binary tree generally requires less memory than BFS.
Because the tree’s breadth can as much as double each time it gets one level deeper, depth-first traversal is likely to be more space-efficient than breadth-first traversal, though they are strictly both O(n)O(n) additional space in the worst case. The space savings are obvious if we know our binary tree is balanced — its depth will be O(\lg{n})O(lgn) and its breadth will be O(n)O(n).
DFS does not necessarily find the shorted path to a node, while BFS does.

Djikstra algorithm

Does not work for negative weights.
Recall that in Dijkstra’s algorithm, once a vertex is marked as “closed” (and out of the open set) -it assumes that any node originating from it will lead to greater distance so, the algorithm found the shortest path to it, and will never have to develop this node again, but this doesn’t hold true in case of negative weights.

Binary Tree

Property 1: The number of total nodes on each level doubles as we move down the tree
Property 2: The number of nodes on the last level is equal to the sum of the number of nodes in the other levels + 1. This means about half of our nodes are on the last level.
Calculations: The number of nodes on the last level is n, then we know that the total number of nodes in the tree is (n-1)+n=2n-1.
Calculations: nodes = 2^h -1, where h is the height of the tree

Graph

Graphs are ideal for cases where you are working with things that connect to other things.
Scaling Challenges: Most graph algorithms are O(n*lg(n)) or even slower.
Terminology(Always analyse qns with the below type)
Directed vs Undirected
Acyclic vs Cyclic(no repeating nodes or edges that connects back to itself e.g: O=O)
Weighted Vs Unweighted
Legal coloring (No two adjacent nodes have the same color)
Representation:
Edge List (A list containing all the edges. Each element of the outer list is a sub-list containing the node numbers with links between them. For eg (2,3) means there is a link between node 2 and 3): int[][] graph = {{0, 1}, {1, 2}, {1, 3}, {2, 3}};
Adjacency List (A list where the index represents the node and the value at that index represents the list containing its’ neighbour nodes. Here, node 3 has edges to node 1 and 2): int[][] graph = {{1},{0, 2, 3},{1, 3}, {1, 2}};
We can also use a hashmap where the keys represent the node and the values are the lists of its neighbours:
O(1): Finding out all neighbours
O(n): Finding if 2 nodes are neighbours
Map<Integer, List<Integer>> graph = new HashMap<>() {
{
put(0, Arrays.asList(1));
put(1, Arrays.asList(0, 2, 3));
put(2, Arrays.asList(1, 3));
put(3, Arrays.asList(1, 2));
}
};

Map<String, String> map = ImmutableMap.of("key1", "value1", "key2", "value2");

Adjacency Matrix: A matrix of 0s and 1s.
O(1): Finding out if 2 nodes are neighbours
O(N): Finding all neighbours of a node
int[][] graph = {
{0, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1},
{0, 1, 1, 0},
};
Algorithms: BFS (Stack), DFS(Queue), Dijkstra(Weighted graph), Topological Sort(Directed graph), Minimum Spanning Tree(Weighted graph)

Topological Ordering

Sequential ordering of all nodes
Edges only point forward
Only possible if the graph is a Directed Acyclic Graph (No cycle)

Topological sort using DFS:
L = list()
while there are unvisited nodes
v = select unvisited node
DFS(G, v, L)

Bellman ford — Single Source Shortest Path

After 1 Iteration, all nodes that are 1 hop away from the source node have correct paths.
Keep running until V-1 and Bellman ford finds the shortest path from s to all other nodes.
O(VE)
No issue with negative weighted graph edges but not suitable for cycle graph.
Run Bellman-Ford for |V| iterations. If an estimate changes in the last iteration then negative weight cycle.

Go through all edges and relax them for every iteration.
https://www.youtube.com/watch?v=FtN3BYH2Zes

Prim, Minimum Spanning Tree, Kruskal

Check if the given binary tree is balanced?

Easy first approach:

This approach is O(N²). For each time we call getHeight on a node, the complexity is O(N). Since inside isBalanced, we will call getHeight for all the nodes in the tree, the total complexity is N * O(N) which is O(N²).

More time efficient approach:

Do a DFS recursion and return the height of the current node.

This approach is O(N).

Graph Colouring

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] colorMap = new int[graph.length]; // 0 means no color

        for(int i=0; i<graph.length; i++){
            int node = i;
            int[] neigh = graph[i];

            if(colorMap[node] != 0) continue;

            HashSet<Integer> invalidColors = new HashSet<>();
            if (neigh.length == 1) continue; 
            // if current node is only attached to 1 other node, 
            // we don't give it a color because it can take whatever color 
            // that it's neighbour is not taking. We don't want it to become 
            // a restriction for the neighbour.
            for(int n: neigh){
                if(n==node) return false;
                if(colorMap[n] != 0){
                    invalidColors.add(colorMap[n]);
                }
            }

            if(invalidColors.size() == 2) return false;
            if(invalidColors.size() == 0){
                colorMap[node]=1;
            } else if(invalidColors.contains(1)) {
                colorMap[node] = -1;
            } else if(invalidColors.contains(-1)) {
                colorMap[node] = 1;
            }

        }
        return true;
    }
}

Like the bipartite question.

Network (Can a message reach a node in the network?)

Finding duplicate in an int array in O(n) time

we were given an array of integers where:

the integers are in the range 1..n
the array has a length of n+1

I personally am not sure how this is graph..but the idea is just to create an additional array called count with the size of intArray+1.

Then, iterate through intArray and for each number i see, i do a count[num]+=1.

Lastly, iterate through count array and check if any value is >1.

If count[A]>1, it means value A is a duplicate. The key of count is the number while the value of count[X] is the number of times that the number appears.

Is this graph Bipartite? (Leetcode 785)

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

We can see that a graph is bipartite if neighbouring nodes are coloured differently. Hence this problem can be solved by assigning colours to each node and traversing using BFS.

The key to the solution is recognising that we need to account for cases where the graph might not be connected. There might be islands nodes or sets of nodes that are not connected to other nodes. Hence, we need the for loop.

Simplest answer:

public boolean isBipartite(int[][] graph) {
        HashMap<Integer, String> map = new HashMap<>();

        for(int i=0; i < graph.length; i++){
            int[] adjacentNodes = graph[i];
            System.out.println(map);
            if(!map.containsKey(i)){
                
                // find illegal color
                Set<String> illegalColors = new HashSet<>();
                for(int j=0; j<adjacentNodes.length; j++){
                    if(map.containsKey(adjacentNodes[j])){
                        illegalColors.add(map.get(adjacentNodes[j]));
                    }
                }

            
                if(illegalColors.size() > 1) return false;

                // illegalColors should only contain 1 element
                String illegalColorOfAdjacentNodes = "";
                for(String color: illegalColors){
                    illegalColorOfAdjacentNodes= color;
                }

                // if current node is only connected to 1 other node, then it means it can take
                // any color. We will just not assign it any color so that the other connected node
                // have freedom to choose colors based on its' other connected nodes other than this 
                // current node
                if(adjacentNodes.length == 1) continue;

                map.put(i, illegalColorOfAdjacentNodes == "blue" ? "red": "blue");
            }
        }

        return true;
    }

(Same as above, a previous qns on coloring)

class Solution {
    public boolean isBipartite(int[][] graph) {
        
        HashMap<Integer, Integer> nodeToColor = new HashMap<>();
        for(int i=0; i<graph.length; i++){
            int node = i;
            int[] neigh = graph[i];
            if(nodeToColor.containsKey(node)) continue;

            if(neigh.length == 1) continue; // skip assigning...

            int neighColor = -1; // unassigned
            for(int n: neigh){
                if(nodeToColor.containsKey(n)){
                    int currNeighColor = nodeToColor.get(n);
                    if(currNeighColor != neighColor && neighColor != -1){
                        return false;
                    }
                    neighColor = currNeighColor;
                }
            }

            int currColor = neighColor == 1 ? 2 : 1;
            nodeToColor.put(node, currColor);
        }

        return true;
    }
}

886. Possible Bipartition

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

class Solution {
   
    public boolean possibleBipartition(int n, int[][] dislikes) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for(int[] edge: dislikes){
            int a = edge[0];
            int b = edge[1];
            adj.computeIfAbsent(a, value -> new ArrayList<Integer>()).add(b);
            adj.computeIfAbsent(b, value -> new ArrayList<Integer>()).add(a);
        }

        int[] color = new int[n+1];
        Arrays.fill(color, -1); // 0 stands for red and 1 stands for blue

        for(int i=1; i<=n; i++){
            if(color[i] == -1){ //if node is unassigned a color...
                if(!bfs(i, adj, color)) return false;
            }
        }

        return true;
    }

    public boolean bfs(int source, Map<Integer, List<Integer>> adj, int[] color){
        Queue<Integer> q = new LinkedList<>();
        q.offer(source);
        color[source]=0;

        while(!q.isEmpty()){
            int node = q.poll();
            if(!adj.containsKey(node)){
                continue;
            }
            for(int neighbor: adj.get(node)){
                if(color[neighbor] == color[node]){
                    return false;
                }
                if(color[neighbor] == -1){
                    color[neighbor] = 1-color[node];
                    q.add(neighbor);
                }
            }
        }
        return true;
    }
    
}

684. Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3

Example 2:

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3

The idea is to traverse through every edge in the given input. For eg, edge e consist of [u, v]. We try to see if we are able to traverse from u to v with the current set of edges (not inclusive of the current e) by DFS. If we can, then it means the current edge e is a duplicate.

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int nodeCount = edges.length;
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        int[] result = new int[1]; 
        for(int[] edge: edges){
            int from = edge[0];
            int to = edge[1];
            HashMap<Integer, Boolean> visited = new HashMap<>();
            if(dfs(map, to, from, to, visited)){// can i get from to-from without this current node?
                result = edge;
            } 
            map.putIfAbsent(from, new ArrayList<>());
            map.putIfAbsent(to, new ArrayList<>());
            map.get(from).add(to);
            map.get(to).add(from);
        }

        return result;
    }

    public boolean dfs(HashMap<Integer, ArrayList<Integer>> map, int to, int from, int start, HashMap<Integer, Boolean> visited){
        if(start == from) return true; // can reach
        if (visited.getOrDefault(start, false)) return false;
        visited.put(start, true);
    
        ArrayList<Integer> neigh = map.getOrDefault(start, new ArrayList<Integer>());
        for(Integer n: neigh){
            if(dfs(map, to, from, n, visited)){
                return true;
            }
        }
        return false;
    }
 
}

685. Redundant Connection II

https://leetcode.com/problems/redundant-connection-ii/

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi.

Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

The following solution is taken from a youtube tutorial video

Path with Maximum Gold (Leetcode 1219)

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

Every time you are located in a cell you will collect all the gold in that cell.
From your position you can walk one step to the left, right, up or down.
You can’t visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.Example 2:Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

class Solution {
    public int getMaximumGold(int[][] grid) {

        int max = 0;
        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                boolean [][] visited = new boolean[grid.length][grid[0].length];
                int gold = search(row, col, grid, 0, visited);
                max = Math.max(max, gold);
            }
        }
        return max;
    }
    public int search(int row, int col, int[][] grid, int goldCollectedSoFar, boolean[][] visited){
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited[row][col] || grid[row][col] == 0) return goldCollectedSoFar;
        visited[row][col] = true;

        int currGold = grid[row][col];
        int left = search(row, col-1, grid, goldCollectedSoFar + currGold, visited);
        int right = search(row, col+1, grid, goldCollectedSoFar + currGold, visited);
        int top = search(row-1, col, grid, goldCollectedSoFar + currGold, visited);
        int down = search(row+1, col, grid, goldCollectedSoFar + currGold, visited);
        visited[row][col] = false;

        return Math.max(left, Math.max(right, Math.max(top, down)));
    
    }
}

Remember to set visited[i][k]=false; when you are done with traversing all directions. This is so that other paths can visit that node.

Iterative Solution

Note that we cannot visit the same node in the same path. But from a given starting position of row, col, we can traverse different paths. And these different paths are all explored in the findPath() function. Hence, if we were to use the method of having a single visited[][] array in the entire findPath() function, it will not work. Because once a path visited a position, we mark visited[][] as true and the other paths cannot access it. Hence the idea here is to make sure that we only check for repeated visits for the single path that the current position is on and not across all paths. In a sense, we need to have multiple visited[][]. Here, we keep track of all previously visited nodes in the variable path and only check against it.

// Time limit exceeded....

class Solution {
    public int getMaximumGold(int[][] grid) {

        int max = 0;

        if(grid.length == 0 && grid[0].length ==0) return 0;

        for(int row=0; row<grid.length; row++){
            for(int col=0; col<grid[0].length; col++){
                if(grid[row][col] == 0) continue;
                int gold = search(row, col, grid);
                max = Math.max(max, gold);
            }
        }
        return max;
    }

    public int search(int row, int col, int[][] grid){
        int maxCost = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(row, col, grid[row][col], ""));

        while(!queue.isEmpty()){
            Node curr = queue.poll();
            int currRow = curr.row;
            int currCol = curr.col;
            String path = curr.path;

            String currPath = String.valueOf(currRow) + "-" + String.valueOf(currCol);
            if(path.indexOf(currPath) >= 0) continue;

            path += "#" + currPath;
            int value = curr.val;
            maxCost = Math.max(maxCost, value);

            if(currRow-1 >= 0 && grid[currRow-1][currCol] != 0){
                queue.add(new Node(currRow-1, currCol, value+grid[currRow-1][currCol], path));
            } 
            if(currRow+1<grid.length && grid[currRow+1][currCol] != 0) {
                queue.add(new Node(currRow+1, currCol, value+grid[currRow+1][currCol], path));
            }
            if(currCol+1<grid[0].length && grid[currRow][currCol+1] != 0){
                queue.add(new Node(currRow, currCol+1, value+grid[currRow][currCol+1], path));
            }
            if(currCol-1>=0 && grid[currRow][currCol-1]!=0){
                queue.add(new Node(currRow, currCol-1, value+grid[currRow][currCol-1], path));
            }
        }
        return maxCost;

    }

    public static class Node{
        int row;
        int col;
        int val;
        String path;

        public Node(int row, int col, int val, String path){
            this.row = row;
            this.col = col;
            this.val = val;
            this.path = path;
        }
    }
}

Number of Islands (Leetcode 200)

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 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Note that for this question, we do a recursion and the purpose of recursion is just to change the value from 1 to 0.
We always return a 1 as long as we go past the if loop

public int numIslands(char[][] grid) {
        int total = 0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == '0') continue;
                total += search(grid, i, j);
            }
        }
        return total;
}
public int  search(char[][] grid, int i, int j){
        if(i<0 || i>grid.length-1 || j<0 || j>grid[0].length-1 || grid[i][j] == '0') return 0;

        grid[i][j] = '0';
        int one = search(grid, i-1, j);
        int two = search(grid, i+1, j);
        int three = search(grid, i, j-1);
        int four = search(grid, i, j+1);
        return 1;
        
}

305. Number of Islands II

A 2d grid map of `m` rows and `n` columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. 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:
 m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]Output:
 [1,1,2,3]

Explanation:

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

Follow up:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

TODO: Use Union Find….

public List<Integer> numIslands2(int m, int n, int[][] positions) {

}

Going through an example….

In this case, the first node is [0,0]. To compute the ID, we use formula i*n+j, which equals to 0 here.

Perform step 7….

Update parents at index 0 to be 0 to indicate that parent of index i(which is 0) is 0.

class Solution {
  class UnionFind{
    int[] parents;
    int[] rank;
    int count = 0;
    int m, n;

    int[][]directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    
    UnionFind(int mGrid, int nGrid){
      m = mGrid;
      n = nGrid;
      parents = new int[m*n];
      rank = new int[m*n]; // initialised all to 0

      for(int i=0; i<m*n; i++){
        parents[i] = -1; // -1 indicate no parent for all index
      }
    }

    public int find(int positionIndex){
      // path compression
      if(parents[positionIndex] != positionIndex){
        parents[positionIndex] = find(parents[positionIndex]);
      }
      return parents[positionIndex];
    }

    public void union(int id1, int id2){
      // union with rank
      int rootIndex1 = find(id1);
      int rootIndex2 = find(id2);

      if(rootIndex1 != rootIndex2){
        if(rank[rootIndex1] > rank[rootIndex2]){
          parents[rootIndex2] = rootIndex1;
        } else if (rank[rootIndex2] > rank[rootIndex1]){
          parents[rootIndex1] = rootIndex2;
        } else {
          parents[rootIndex2] = rootIndex1;
          rank[rootIndex1] ++;
        }
        count --;
      }
    }

    public int place(int[] position){
      int i = position[0];
      int j = position[1];

      if(parents[i * n + j] == 1){
        count ++;
        parents[i * n + j] = i * n + j;  // set current node to be its own parent
      }

      for(int[] direction: directions){
        int i2 = i + direction[0];
        int j2 = j + direction[1];

        // check if there are any adjacent land nodes
        // if yes, join the lands
        if(i2 < m && i2 >= 0 && j2 < n && j2 >=0 && parents[i2 * n + j2] != -1){
          union(i * n + j, i2 * n + j2);
        }
      }
      return count;
    }
  }
   
  public List<Integer> numIslands2(int m, int n, int [][] positions){
    UnionFind uf = new UnionFind(m, n);
    int p = positions.length;
    List<Integer> result = new ArrayList<Integer>(p);

    for(int x = 0; x < p; x++){
      result.add(x, uf.place(positions[x]));
    }
    return result;
  }
}

class UnionFind{
        int[] parents;
        int[] rank;
        int count = 0; // num of total separate 
        int m;
        int n;

        public UnionFind(int n, int m){
            this.n=n;
            this.m=m;

            parents = new int[m*n];
            rank = new int[m*n];

            for(int i=0; i<parents.length; i++){
                parents[i] = -1; //indicate no parent
            }
        }

        public int find(int positionIndex){
            while(parents[positionIndex]!=positionIndex){
                parents[positionIndex]=find(parents[positionIndex]);
            }
            return parents[positionIndex];
        }

        public void union(int p1, int p2){
        
            int root1 = find(p1);
            int root2 = find(p2);

            if(root1!=root2){
                if(rank[p1]<rank[p2]){
                    parent[p1]=parent[p2];
                } else if (rank[p2]<rank[p1]){
                    parent[p2]=parent[p1];
                } else {
                    parent[p1]=parent[p2];
                    rank[p1]--;
                }
            }
            count--;
        }

        public int place(int[] position){
            int row = position[0];
            int col = position[1];

            int index = row*m + col;
            parent[index]=index; // assign oneself to be oneself parent
            count ++;

            // check if can merge with all 4 surroundings
            if(row-1>=0 && row-1<m){
                int newIndex = (row-1)*m+col;
                if (parent[newIndex] != -1){
                    union(index, newIndex);
                }
            }
            if(row+1>=0 && row+1<m){
                int newIndex = (row+1)*m+col;
                if (parent[newIndex] != -1){
                    union(index, newIndex);
                }
            }
            if(col-1>=0 && col-1<n){
                int newIndex = row*m+(col-1);
                if (parent[newIndex] != -1){
                    union(index, newIndex);
                }
            }
            if(col+1>=0 && col+1<n){
                int newIndex = row*m+(col+1);
                if (parent[newIndex] != -1){
                    union(index, newIndex);
                }
            }

            return count;
        }
    }

    public List<Integer> numIslands2(int m, int n, int[][] positions){
        UnionFind uf = new UnionFind(m, n);
        int p = positions.length;
        List<Integer> result = new ArrayList<Integer>(p);

        for(int x=0; x<p; x++){
            result.add(x, uf.place(positions[x]));
        }
        return result;
    }

Number of Distinct Islands (Leetcode 694) — Premium qns

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Return the number of distinct islands.

Example 1:

Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 1

Example 2:

Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output: 3

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

class Solution {
    HashSet<String> islands;
    public int numDistinctIslands(int[][] grid) {
        islands = new HashSet<>();
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == 1){
                   String path = traverse(i, j, grid, "");
                   islands.add(path);
                }
            }
        }
        System.out.println(islands);
        return islands.size();
    }

    public String traverse(int row, int col, int[][]grid, String direction){
        if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0){
            return direction;
        }

        grid[row][col]=0; // change to visited
        String up = traverse(row-1, col, grid, "#up");
        String down = traverse(row+1, col, grid, "#down");
        String left = traverse(row, col-1, grid, "#left");
        String right = traverse(row, col+1, grid, "#right");
        return direction + up + down + left + right;
    }
}

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Please memorise how to do inOrder, preOrder traversal…don’t assume you know.

Course Schedule Leetcode 207

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5

Solution:

What algorithm should we use for a graph question which uses some sort of ordering? THINK…THINK.. THINK

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
       
        int[] incoming = new int[numCourses];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for(int[] pre: prerequisites){
            int to = pre[0];
            int from = pre[1];

            incoming[to]++;
            map.putIfAbsent(from, new ArrayList<Integer>());
            map.get(from).add(to);
        }

        Queue<Integer> q = new LinkedList();
        for(int i=0; i<numCourses; i++){
            if(incoming[i] == 0) q.add(i);
        }
        
        HashSet<Integer> visitedNodes = new HashSet<>();
        int count = 0;
        while(!q.isEmpty()){
            Integer node = q.poll();
            count ++;
            if(visitedNodes.contains(node)) continue;
            visitedNodes.add(node);
            for(Integer n: map.getOrDefault(node, new ArrayList<>())){
                incoming[n] --;
                if (incoming[n] == 0) q.add(n);
            }

        }
        
        return count == numCourses;
    }
}

Extension Leetcode 210 Course Schedule II

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Things to note:

returning an empty int[] return new int[0]
Converting an arraylist to int[] arraylistName.stream().mapToInt(i->i).toArray()

Not needed: if(prerequisites.length==0) return new int[0];

Construct Binary Tree from Preorder and Inorder Traversal

Preorder tells me what my curr root index is
I use inorder to find out where my left and right subtree node is positioned in the preorder array

How to get Left child index?

I know that the node index right next to me on RHS in the preorder array gives me the left root.

How to get the index of the right child?

Our aim is to find out the index of the right child for our current node in the preorder array.
We know the index of the current node in the preorder array — name it as the preStart variable.
Remember the preorder traversal array always visits all the node on the left branch before going to the right. Thus, we can get the immediate right child index by skipping all the nodes on the left branches of the current node.
We need to know the size of left subtree :)
The inorder array has this information.
Thus the immediate right child index is preStart + numsOnLeft + 1 (remember in preorder traversal array, the root is always ahead of children nodes but you don’t know which one is the left child and which one is the right, and this is why we need inorder array)
numsOnLeft = inRoot— inStart, inRoot is the index of root in inorder array.

Leetcode 106 Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(postorder.length-1, 0, inorder.length-1, inorder, postorder);
    }

    // inorder: left root right
    // postorder: left right root

    public static TreeNode helper(int postStart, int inStart, int inEnd, int[] inorder, int[] postorder){
        if(inStart>inEnd || postStart<0) return null;

       TreeNode root = new TreeNode(postorder[postStart]);

       int inRoot = 0;
       for(int i=inStart; i<=inEnd; i++){
           if(inorder[i]==postorder[postStart]){
               inRoot=i;
           }
       }

       root.right = helper(postStart-1, inRoot+1, inEnd, inorder, postorder);
       int rightSize = inEnd-inRoot+1;
       root.left = helper(postStart-rightSize, inStart, inRoot-1, inorder, postorder);

       return root;
    }
}

Note the first 3 parameters of the function:

preIndex: The index of the root in postorder array
inStart: The start index f the range of indices in inorder array to find left/right subtree
inEnd: The end index of the range of indices in inorder array to find left/right subtree

The inorder array is used to find the size of left subtree and right subtree

inIndex -> Index of curr root in inorder array

Note that inorder array is arranged in LEFT-ROOT-RIGHT

right subtree size: (inEnd-inIndex)

After finding size of right subtree, we can find the index of left child root from the postorder array and the right child root. Right child root is always the one immediately to the left of the tree’s current root. Left child root is the one immediately to the left of all the elements in the right subtree. Note that in the postorder array, all the elements in the left subtree are to the left of all the elements in the right subtree and root in the rightmost.

889. Construct Binary Tree from Preorder and Postorder Traversal

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int preIndex = 0;
    int postIndex = 0;
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        // pre: root left right
        // post: left right root

        TreeNode root = new TreeNode(preorder[preIndex++]);
        if(root.val != postorder[postIndex]){
            root.left = constructFromPrePost(preorder, postorder);
        }
        if(root.val != postorder[postIndex]){
            root.right = constructFromPrePost(preorder, postorder);
        }
        postIndex++;
        return root;
    }
}

// This is quite hard to understand.

Read all the preorder first, then read postorder.

Finish all LEFT, then finish all RIGHT.

The first node of PREORDER is the root. What follows next, is the ROOT of the LEFT SUB TREE. Whatever that is below in the POSTORDER is the LEFT SUB TREE.

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        // pre: root left right
        // post: left right root

        return dfs(preorder, 0, preorder.length-1, postorder, 0, preorder.length -1);
    }

    private TreeNode dfs(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd){
        if(preStart>preEnd) return null;
        TreeNode root = new TreeNode(pre[preStart]);

        if (preStart == preEnd) return root; // To prevent out of bound in while loop below

        int postIndex = postStart;
        while(post[postIndex] != pre[preStart+1]) postIndex++; // move until postIndex is pointing to the root
        // of the left sub tree of current root.

        int sizeOfLeftSubTree = postIndex - postStart + 1; 
        root.left = dfs(pre, preStart+1, preStart+sizeOfLeftSubTree, post, postStart, postEnd);
        root.right = dfs(pre, preStart+sizeOfLeftSubTree+1, preEnd, post, postIndex+1, postEnd-1);
        // postIndex + 1: postIndex is the root of left sub tree...the one right next to it in postorder
        // will be the rhs in right sub tree.

        return root;
    }
}

1008. Construct Binary Search Tree from Preorder Traversal

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.

A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

// Initial wrong solution….

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
       
        return helper(preorder, 0, 0, preorder.length-1);
    }

    public TreeNode helper(int[] preorder, int index, int start, int end){

        if(index>=preorder.length || start>end ) return null;

        System.out.println("++++");
        System.out.println(start);
        System.out.println(end);
        
        int rootVal = preorder[index];
        TreeNode root = new TreeNode(rootVal);
        if(start==end) return root;

        int rightIndex = index+1;
        while(true){
            int right = rightIndex+1;
            if(right>end || preorder[right] >= rootVal){
                break;
            }
            rightIndex++;
        }

        
        root.left = helper(preorder, index+1, start, rightIndex);
        if(rightIndex != index+1) {
            root.right = helper(preorder, rightIndex+1, rightIndex+1, end);
        }
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int index;
    public TreeNode bstFromPreorder(int[] preorder) {
        index=0;
        return helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public TreeNode helper(int[] preorder, int min, int max){
        if(index == preorder.length) return null;
        int val = preorder[index];

        if(val<min || val>max) return null;

        index++;
        TreeNode root = new TreeNode(val);
        root.left = helper(preorder, min, val);
        root.right = helper(preorder, val, max);
        return root;
        
    }
}

12. Leetcode 127 Word Ladder

This question needs graph even though it is not obvious.

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]Output: 5Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Intuition

Start from beginWord and search the endWord using BFS.

Algorithm

Do the pre-processing on the given wordList and find all the possible generic/intermediate states. Save these intermediate states in a dictionary with key as the intermediate word and value as the list of words which have the same intermediate word.
Push a tuple containing the beginWord and 1 in a queue. The 1 represents the level number of a node. We have to return the level of the endNode as that would represent the shortest sequence/distance from the beginWord.
To prevent cycles, use a visited dictionary.
While the queue has elements, get the front element of the queue. Let’s call this word as current_word.
Find all the generic transformations of the current_word and find out if any of these transformations is also a transformation of other words in the word list. This is achieved by checking the all_combo_dict.
The list of words we get from all_combo_dict are all the words which have a common intermediate state with the current_word. These new set of words will be the adjacent nodes/words to current_word and hence added to the queue.
Hence, for each word in this list of intermediate words, append (word, level + 1) into the queue where level is the level for the current_word.
Eventually if you reach the desired word, its level would represent the shortest transformation sequence length.
Termination condition for standard BFS is finding the end word.

Note that we cannot use a variable that is defined outside of the while loop to track the number of sequence counts. This is because the increment logic will be wrong.

Word Ladder 2

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 1000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.

My Time limit exceeded solution:

Failed this:

“qa”
“sq”
[“si”,”go”,”se”,”cm”,”so”,”ph”,”mt”,”db”,”mb”,”sb”,”kr”,”ln”,”tm”,”le”,”av”,”sm”,”ar”,”ci”,”ca”,”br”,”ti”,”ba”,”to”,”ra”,”fa”,”yo”,”ow”,”sn”,”ya”,”cr”,”po”,”fe”,”ho”,”ma”,”re”,”or”,”rn”,”au”,”ur”,”rh”,”sr”,”tc”,”lt”,”lo”,”as”,”fr”,”nb”,”yb”,”if”,”pb”,”ge”,”th”,”pm”,”rb”,”sh”,”co”,”ga”,”li”,”ha”,”hz”,”no”,”bi”,”di”,”hi”,”qa”,”pi”,”os”,”uh”,”wm”,”an”,”me”,”mo”,”na”,”la”,”st”,”er”,”sc”,”ne”,”mn”,”mi”,”am”,”ex”,”pt”,”io”,”be”,”fm”,”ta”,”tb”,”ni”,”mr”,”pa”,”he”,”lr”,”sq”,”ye”]

Solution from leetcode discussions:

/**
 * High level design: BFS + DFS
 * 
 * Step 1: use BFS to build graph (adjacency list of each word), as well as calculating distance from beginWord to 
 * each node in the graph (should store minimum distance)
 * 
 * Step 2: use DFS to traverse and record path from beginWord to endWord with shortest path. We can use distance map
 * to control every next word. 
 * */
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    if (wordList.size() == 0) {
        return new ArrayList<>();
    }

    /**
     * @param result: result list to store final return list
     * @param graph: adjacency list of key - store all neighbors of each word (neighbor means all words in dictionary 
     *             that only has one character difference with key)
     * @param distance: distance between beginWord and current key word, used for tracing path when we do DFS
     * @param dict: word dictionary, efficient for searching purpose
     * */
    List<List<String>> result = new ArrayList<>();
    Map<String, Set<String>> graph = new HashMap<>();
    Map<String, Integer> distance = new HashMap<>();
    Set<String> dict = new HashSet<>(wordList);

    bfs(beginWord, endWord, dict, graph, distance);
    dfs(result, graph, distance, endWord, beginWord, new ArrayList<>(Arrays.asList(beginWord)));
    return result;
}

// step 1
public void bfs(String beginWord, String endWord, Set<String> dict, Map<String, Set<String>> graph, Map<String, Integer> distance) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    distance.put(beginWord, 0);
    
    while (!queue.isEmpty()) {
        boolean reachEnd = false;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curWord = queue.poll();
            
            /* try all possible substitution (26 characters) in every position of current word, if newWord exists in dictionary, 
               we add it to the adjacency list of curWord */
            for (int j = 0; j < curWord.length(); j++) {
                char[] curWordArr = curWord.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    curWordArr[j] = c;
                    String newWord = new String(curWordArr);
                    if (dict.contains(newWord)) {
                        graph.putIfAbsent(curWord, new HashSet<>());
                        graph.get(curWord).add(newWord);
                        // to indicate that currWord can lead to newWord
                    }
                }
            }
            
            // traverse all neighbors of current word, update distance map and queue for next ladder (level)
            // WARNING: DO NOT USE visited set, since it is hard to deal with end word if endWord is visited
            for (String neighbor : graph.get(curWord)) {
                if (!distance.containsKey(neighbor)) {
                    distance.put(neighbor, distance.get(curWord) + 1);
                    if (neighbor.equals(endWord)) {
                        reachEnd = true;
                    }
                    else {
                        queue.offer(neighbor);
                    }
                }
            }
            if (reachEnd) {
                break;
            }
        }
    }
}

// step 2
public void dfs(List<List<String>> result, Map<String, Set<String>> graph, Map<String, Integer> distance,
                String endWord, String curWord, List<String> tempList) {
    if (curWord.equals(endWord)) {
        result.add(new ArrayList<>(tempList));
        return;
    }
    
    for (String nextWord : graph.get(curWord)) {
        // only if next node is on the minimum path to the endWord, we can traverse it
        if (distance.get(nextWord) == distance.get(curWord) + 1) {
            tempList.add(nextWord);
            dfs(result, graph, distance, endWord, nextWord, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }
}

TODO:

Minimum Genetic Mutation - LeetCode

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'. Suppose we…

leetcode.com

13. Leetcode 365 Water and Jug Platform

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

We first add 0 to the queue -> 0 water in jug
Then we enter a while loop where in each iteration, we will use all the values inside the queue and apply the four operations to try to form the value z.
We have a visited value -> So that we do not repeatedly check for the same numbers.

https://www.math.tamu.edu/~dallen/hollywood/diehard/diehard.htm

Weird question….

14. Leet code 314 Binary Tree Inorder

Note that this is like depth-first-search. We traverse all the way to the end until there is no child nodes.
First we keep adding all the nodes on the left of root to the stack until we reach the end.
When current node is null(We are at the NULL, NULL level), we will then pop out the item in the stack (The parent of NULL NULL, which is the leftmost node). The first item to be popped will be the leftmost node. After wards, we will print it. And at this level of NULL NULL, we will assign the root as the root node’s right child.
If this is empty, we will repeat the previous section and we find that the next node to be popped out will be the node above the previously popped node. We then print the value and reassign root to be that new node’s right child.

15. Binary Tree PostOrder

To get the idea of how to write the code, draw out the List and Stack and try out the steps.

16. Binary Tree PreOrder

17. Depth First Search

18. Breadth First Search

19. Topological Sort

20. Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // Not able to sort a TreeMap by its value.
    TreeMap<Integer, List<Pair<Integer, Integer>>> map;

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map = new TreeMap();

        List<List<Integer>> list = new LinkedList();

        traverse(root, 0, 0);

        for(Map.Entry<Integer, List<Pair<Integer, Integer>>> entry: map.entrySet()){
            LinkedList<Integer> allNodesAtCol = new LinkedList();
            List<Pair<Integer, Integer>> pairs = entry.getValue();
            Collections.sort(pairs, (node1, node2) -> {
                // Compare by key first then if both items have same key (height), compare by its' value.
            
                if(node1.getKey() < node2.getKey()){
                    return -1;
                }
                if (node1.getKey() > node2.getKey()){
                    return 1;
                }
                if(node1.getValue() < node2.getValue()){
                    return -1;
                }
                return 1;
            });
            for(Pair<Integer, Integer> pair: pairs){
                allNodesAtCol.add(pair.getValue());
            }
            list.add(allNodesAtCol);
        }
        return list;
    }

    public void traverse(TreeNode root, int row, int col){
        if(root == null) return;

        map.putIfAbsent(col, new LinkedList<Pair<Integer, Integer>>());
        map.get(col).add(new Pair(row, root.val));

        traverse(root.left, row+1, col-1);
        traverse(root.right, row+1, col+1);
    }
}

21. Insertion to BST

Just insert it to the end of the tree. Insert to the last node.
Idea: Start from the root node. Then compare left and right to see which side to traverse.
When reach the end, just create new Node and put it as the last leaf node.

    void insert(int key){
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key){
        if(root == null) return new Node(key);

        if(root.val<key){
            root.right = insertRec(root.right, key);
        } else {
            root.left = insertRec(root.left, key);
        }
        return root;
    }

22. Check that a tree is symmetric

Full code in git-hub repository

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return check(root.left, root.right);
    }
    public boolean check(TreeNode left, TreeNode right){
        if(left == null && right == null) return true;
        if (left == null && right != null) return false;
        if (right == null && left != null) return false;
        if (left.val != right.val) return false;
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

Leetcode 96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Note that we need to have a valid BST. Some nodes cannot be placed on the left of the node etc.
We can think of this problem to be like, selecting a root node for every possible positions of 1…n. Once we select a root node, those nodes that can be on the left would be numbers smaller than the root. Similar for right subtree.
First note that dp[k] represents the number of BST trees built from 1….k;
Then assume we have the number of the first 4 trees: dp[1] = 1 ,dp[2] =2 ,dp[3] = 5, dp[4] =14 , how do we get dp[5] based on these four numbers is the core problem here.
The essential process is: to build a tree, we need to pick a root node, then we need to know how many possible left sub trees and right sub trees can be held under that node, finally multiply them.
To build a tree containing {1,2,3,4,5}. First we pick 1 as root, for the left sub tree, there are none; for the right sub tree, we need to count how many possible trees are there constructed from {2,3,4,5}. This is the same number as the number of trees we can construct from the tree{1,2,3,4}.
So the total number of trees with the root as “1” picked and of size 5 is dp[0] * dp[4] = 14. 0 nodes on the left and 4 nodes on the right.
Similarly, for the size of 5, root 2 has dp[1]*dp[3] = 5 trees. root 3 has dp[2]*dp[2] = 4, root 4 has dp[3]*dp[1]= 5 and root 5 has dp[0]*dp[4] = 14. Finally sum the up and it’s done.

public int numTrees(int n) {
    int[] dp = new int[n+1]; // of size n+1 because we want to have numbers from 0,1,2...n
    dp[0] = 1; // Tree with 0 node
    dp[1] = 1; // Tree with 1 node
    for(int size= 2; size <= n; size++) // size of tree with n nodes
        for(int root = 1; root<= size; root++) // choosing root
            dp[size] += dp[root-1] * dp[size-root];
    return dp[n];
}

Here, we have 2 for loops. The first topmost for-loop is to traverse through all possible sizes of the tree. The second for-loop is to try out different positions of roots, choosing from nodes [1,…n].
When size = 2, we can choose the root from the nodes: {1,2}. When root=1, dp[2] += dp[1–1] * dp[2–1] = 1+1 = 2. When root=2, dp[2] += dp[2–1] * dp[2–2] = 1+1=2.
dp[2] = 2+2=4

Leet Code 95 Generate all Unique Binary Search Tree Sequence

In line 27, we repeatedly assign a value in the range of [1,2…n] as the root. Then we get the left sub tree and right sub tree.
Since we need to track all possible combinations, we will do so using the List of result.
Each time we get back a left list and right list from the recursive functions, we will add the list to the current root node. Each of these left list and right list contains all possible arrangements of the tree nodes.
In the case where the two lists are non empty, we will try out different combinations of left and right with the two for-loops.

Leetcode 572 Subtree of another tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

The first thought that came to mind is to use inorder traversal. But later, you realise that inorder does not work. One has to use preorder instead because preorder is Root-Left-Right while inorder is Left-Root-Right….not too sure why….

But the best solution is not to use inorder or preorder.

Leet Code 235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

For clarity, the variable named root should be renamed as currNode

Leet Code 236. Lowest Common Ancestor of a Binary Tree

This question is similar to the previous one except that it is for a Binary Tree, not Binary Search Tree. We cannot make use of BST properties.

Here, we return a value when we have found the node p or q. Then as the recursion backtracks and returns, at each position, we will check the return values of the root.left and root.right that the functions are being called. If both left and right are not null, then it means we have found either p or q on both sides. Hence the current root we are at, is the lowest common ancestor.

298. Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example 1:

Input:
   1
    \
     3
    / \
   2   4
        \
         5
Output:
3
Explanation: Longest consecutive sequence path is 
3-4-5, so return 3.

Example 2:

Input:
   2
    \
     3
    / 
   2    
  / 
 1
Output: 2 Explanation: 
Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

class Solution {
    int longest;
    public int longestConsecutive(TreeNode root) {
        longest = 0;
        helper(root, -1, 0);
        return longest;
    }
    public void helper(TreeNode root, int prev, int len){
        if(root == null) {
            longest = Math.max(longest, len);
            return;
        }
        longest = Math.max(longest, len);
        if(root.val != prev+1){
            len = 0;
        }

        helper(root.left, root.val, len+1);
        helper(root.right, root.val, len+1);
    }
}

Leet Code 109. Convert Sorted List to Binary Search Tree

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [0]
Output: [0]

Example 4:

Input: head = [1,3]
Output: [3,1]

Note that for constructing BST or tree, it is always the same pattern of initialising the current node as root. Then root.left = XX and root.right = YY.

Over here, the middle node is always the root node. Then the section on its’ left would be it’s left child and the section on its’ right would be it’s right child.

We use the concept of fast and slow pointers here to find out which is the middle node. The slow pointer will be the one pointing to the middle node.

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode middle = findMiddle(head);
        TreeNode root = new TreeNode(middle.val);
        if(head==middle) return root; // IMPT!!! to prevent stack overflow
        root.left=sortedListToBST(head); // we can pass head here becos in line 47, we set prev.next to null..
        root.right=sortedListToBST(middle.next);
        return root;
    }

    public ListNode findMiddle(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;

        while(fast!=null && fast.next!=null){
            prev=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        if(prev!=null) prev.next=null;
        return slow;
    }
}

114. Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten it to a linked list in-place.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Note that we need to traverse the tree in a preorder manner to form the sorted linked list.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        preorder(root);
    }
    public TreeNode preorder(TreeNode root){
        if(root==null) return null;

        TreeNode right = root.right;

        TreeNode nextNode = preorder(root.left);
        root.right = nextNode; // curr left become new right of root
        root.left = null; // set curr left of root to empty

       
        if (nextNode != null){
            while(nextNode.right != null){
                nextNode = nextNode.right;
            }
            nextNode.right = preorder(right); // right become bottom of root's new right (previously left).
        } else {
            root.right = preorder(right);
        }
        return root;
    }
}

(1)The LEFT_SUBTREE of ROOT will be positioned to the RIGHT position of the root in the LinkedList.

(2) We set LEFT of ROOT to be right once we have obtained (1)

(3) If LEFT_SUBTREE of ROOT is empty, then we know that in the Linked List, the right of ROOT will be the current RIGHT_SUBTREE of ROOT. Hence, we simply pass right to preorder function.

(4) If LEFT_SUBTREE of ROOT is non empty, then we need to arrange the LEFT_SUBTREE to be the ROOT.RIGHT. Then, we get to the endmost of this “LEFT_SUIBTREE” and set the LAST_NODE.RIGHT to be ROOT’s previous’ RIGHT_SUBTREE.

Pictorial representation of what we are trying to achieve

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        preorder(root);
    }

    TreeNode* preorder(TreeNode* root){
        if (root == nullptr) return nullptr;

        TreeNode* tempRight = root->right;
        TreeNode* left = root->left;

        TreeNode* flattenLeft = preorder(left);
        root->right = flattenLeft;
        root->left = nullptr;

        // go to the rightmost of flattenLeft
        TreeNode* end = flattenLeft;
        if(end != nullptr){
            while(end->right !=nullptr){
                end = end->right;
            }
            end->right = preorder(tempRight);
        } else {
            root -> right = preorder(tempRight);
        }
        return root;
    }
};

116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Solution:

The idea is that if i am currently the right node, then my next node will be pointing to the left child of its’ parent node. This parent node is the next node of my parent node.

117. Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

You may only use constant extra space.
Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

The difference from the previous question is that the tree is not full binary tree. There might be null nodes.

To make sure that the array list of nodes contains the rightmost node to be at the front of the list, for the given height, we traverse right then left.

(A) We are reading the last node in the list which gives us the right node that is closest to current node. The node that was added previously to rightside list was the node that is to the right of the current node.

(B) We are adding the current node to the Hash Map for future use.

Solutions from the Editorial

class Solution {
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // Initialize a queue data structure which contains
        // just the root of the tree
        Queue<Node> Q = new LinkedList<Node>(); 
        Q.add(root);
        
        // Outer while loop which iterates over 
        // each level
        while (Q.size() > 0) {
            
            // Note the size of the queue
            int size = Q.size();
            
            // Iterate over all the nodes on the current level
            for(int i = 0; i < size; i++) {
                
                // Pop a node from the front of the queue
                Node node = Q.poll();
                
                // This check is important. We don't want to
                // establish any wrong connections. The queue will
                // contain nodes from 2 levels at most at any
                // point in time. This check ensures we only 
                // don't establish next pointers beyond the end
                // of a level
                if (i < size - 1) {
                    node.next = Q.peek();// we previously added from left 
                  // to right..so the existing queue items are nodes on the right of the 
                  // current node
                }
                
                // Add the children, if any, to the back of
                // the queue
                if (node.left != null) {
                    Q.add(node.left);
                }
                if (node.right != null) {
                    Q.add(node.right);
                }
            }
        }
        
        // Since the tree has now been modified, return the root node
        return root;
    }
}

//O(N) space

I don’t really understand the solution given for O(1) Space………

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        int sum = 0;
        Queue<TreeNodeWrapper> queue = new LinkedList();
        queue.add(new TreeNodeWrapper(root, ""));
        while(!queue.isEmpty()){
            TreeNodeWrapper curr = queue.poll();
            if (curr.node.left == null && curr.node.right == null){
                // leaf node
                sum += Integer.parseInt(curr.sumSoFar);
                continue;
            }
            if (curr.node.left != null){
                queue.add(new TreeNodeWrapper(curr.node.left, curr.sumSoFar));
            }
            if (curr.node.right != null){
                queue.add(new TreeNodeWrapper(curr.node.right, curr.sumSoFar));
            }
        }
        return sum;
    }

    public static class TreeNodeWrapper {
        public TreeNode node;
        public String sumSoFar;
        public TreeNodeWrapper(TreeNode node, String toAdd){
        
            this.node = node;
            this.sumSoFar = toAdd + String.valueOf(node.val);
        }
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int sum;
    int sumNumbers(TreeNode* root) {
        sum = 0;
        if(!root) return sum;
        move(root, "");
        return sum;
    }
    void move(TreeNode* root, string val){
        if (!root) return;
        if(!root->left && !root->right){ // check for next level null, so we don't double count
            int v = stoi(val+ to_string(root->val));
            sum += v;
            return;
        }
      
        move(root->left, val+to_string(root->val));
        move(root->right, val+to_string(root->val));
    }
};

130. Surrounded Regions

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.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Solution:

Initially, i was thinking of using 2 for loops and then doing BFS to find those ‘O’s that are connected. But then…i realise, i dont know what is the terminating condition and also how to do?…..

Then, i went to see leet code discussion and found a superb solution.

The idea is to first find all ‘O’s on the edge, and do BFS from these ‘O’s. Keep adding ‘O’s into the queue in the BFS, and mark it as ‘F’. Since these ‘O’s are found by doing BFS from the ‘O’s on the edge, it means they are connected to the edge ‘O’s. so they are the ‘O’s that will remain as ‘O’ in the result.

After BFS, there are some ‘O’s can not be reached, they are the ‘O’s that need to be turned as ‘X’.

310. Minimum Height Trees

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs’ root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Example 3:

Input: n = 1, edges = []
Output: [0]

Example 4:

Input: n = 2, edges = [[0,1]]
Output: [0,1]

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

        int[] degree = new int[n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<n; i++) map.put(i, new ArrayList<>());
        for(int[] pair: edges){
            map.get(pair[0]).add(pair[1]);
            map.get(pair[1]).add(pair[0]);
            degree[pair[0]]++;
            degree[pair[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i<n; i++){
            if(degree[i]==1) queue.add(i);
        }
        while(!queue.isEmpty()){
            List<Integer> leaves = new ArrayList<>();
            int size = queue.size();
            for(int i=0; i<size; i++){
                int leaf = queue.poll();
                leaves.add(leaf);
                for(int neigh: map.get(leaf)){
                    degree[neigh]--;
                    if(degree[neigh] == 1) queue.add(neigh);
                }
            }
            result = leaves; // The last set of nodes that become leaves are those in the middle of the tree
        }
        return result;
    }
}

so hard…

The solution is to first identify all the leaf nodes. Remove them, slowly move to it’s parent nodes. The last set of leaf nodes are the nodes in the middle.

We see that the nodes in the middle of the tree will be the node that can form the lowest tree height.

323. Number of Connected Components in an Undirected Graph

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

class Solution {
    HashSet<Integer> visited;
    HashMap<Integer, List<Integer>> map;
    public int countComponents(int n, int[][] edges) {
        map = new HashMap<>();

        for(int[] e: edges){
            map.putIfAbsent(e[0], new ArrayList<>());
            map.get(e[0]).add(e[1]);
            map.putIfAbsent(e[1], new ArrayList<>());
            map.get(e[1]).add(e[0]);
            // Need to be bidirectional
        }

        visited = new HashSet<>();
        int count = 0;
        for(Map.Entry<Integer, List<Integer>> entry: map.entrySet()){
            if(visited.contains(entry.getKey())){
                continue;
            }
            traverse(entry.getKey());
            count++;
        }
        return count + (n-visited.size()); // There might be a case where a node is in n but not in edges
    }

    public void traverse(int key){
        if(visited.contains(key)){
            return;
        }

        visited.add(key);
        List<Integer> neigh = map.getOrDefault(key, new LinkedList<>());
        for(int n: neigh){
            traverse(n);
        }

    }
}

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {

        unordered_map<int, vector<int>> map;
        // NEED TO BE BI-DIRECTIONAL...so that the ordering of which node in the graph was looked at does
        // not matter
        for(vector<int> e: edges){
            if(map.count(e[0]) > 0){
                vector<int> ls = map[e[0]];
                ls.push_back(e[1]);
                map[e[0]] = ls;
            } else {
                vector<int> newList;
                newList.push_back(e[1]);
                map[e[0]] = newList;
            }

            if(map.count(e[1]) > 0){
                vector<int> ls = map[e[1]];
                ls.push_back(e[0]);
                map[e[1]] = ls;
            } else {
                vector<int> newList;
                newList.push_back(e[0]);
                map[e[1]] = newList;
            }
        }

        int count = 0;
        set<int> visited;
        for(int i=0; i<n; i++){
            int root = i;
            if(visited.find(root) != visited.end()){
                continue;
            }
            queue<int> q;
            q.push(root);
            count++;
            while(!q.empty()){
                int curr = q.front();
                q.pop(); // rmb queue pop from front...
                visited.insert(curr);
                if(map.count(curr) > 0){
                    vector<int> neighs = map[curr];
                    for(int i=0; i<neighs.size(); i++){
                        
                        if(visited.find(neighs[i]) != visited.end()){
                            continue;
                        }
                       
                        q.push(neighs[i]);
                    }
                }
            }

            
            cout << endl;
        }
        return count;
    }
};

662. Maximum Width of Binary Tree

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).

// SOLUTION 1: BFS

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }

        LinkedList<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        Integer maxWidth = 0;

        queue.addLast(new Pair<>(root, 0));
        while(queue.size() > 0){
            Pair<TreeNode, Integer> head = queue.getFirst();
            Pair<TreeNode, Integer> elem = null;
            Integer currLevelSize = queue.size();
            for (int i = 0; i < currLevelSize; ++i) {
                elem = queue.removeFirst();
                TreeNode node = elem.getKey();
                if(node.left != null){
                    queue.addLast(new Pair<>(node.left, 2 * elem.getValue()));
                }
                if(node.right != null){
                    queue.addLast(new Pair<>(node.right, 2 * elem.getValue() + 1));
                }
            }
            // elem holds the last value...
            maxWidth = Math.max(maxWidth, elem.getValue() - head.getValue() + 1);
        }

        return maxWidth;
    }

}

I found the solution below to be easier….DFS…

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxWidth;
    HashMap<Integer, Integer> map;
    public int widthOfBinaryTree(TreeNode root) {
       
        map = new HashMap<>();
        maxWidth = 1;
        traverse(root, 0, 0);
        return maxWidth;
    }

    public void traverse(TreeNode root, int levelIndex, int colIndex){
       
        if(root==null){
            return;
        }

        // is leftmost node on level
        if(!map.containsKey(levelIndex)){
            map.put(levelIndex, colIndex);
        } 

        maxWidth = Math.max(maxWidth, colIndex - map.get(levelIndex) + 1);

        traverse(root.left, levelIndex+1, 2*colIndex);
        traverse(root.right, levelIndex+1, 2*colIndex+1);
    }
}

994. Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

This question is similar to another question…but i don’t remember which. Nevermind.

The idea is that, we first populate the queue with all the rotten oranges. At each iteration, for each orange in the queue, we will try to see if it’s neighbour can become rotten. If yes, mark it as rotten and add it to the queue.

Each iteration will result in an increase in variable level, to mark the “minutes”.

At the end, if there are any fresh orange remaining, we just return -1. Otherwise return level.

Overall, this question is like a graph traversal question.

class Solution {
    public int orangesRotting(int[][] grid) {
        int level = 0;
        Queue<Info> queue = new LinkedList<>();
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j]==2){
                    queue.add(new Info(i, j));
                }
            }
        }

        while(!queue.isEmpty()){
            
            int size=queue.size();
            while(size>0){ // only pop oranges added in prev iteration
                Info neigh = queue.poll();
                // find all neighs, mark them as 2
                if(neigh.col-1>=0 && grid[neigh.row][neigh.col-1]==1){
                    grid[neigh.row][neigh.col-1]=2;
                    queue.add(new Info(neigh.row, neigh.col-1));
                } 
                if(neigh.col+1<grid[0].length && grid[neigh.row][neigh.col+1]==1){
                    grid[neigh.row][neigh.col+1]=2;
                    queue.add(new Info(neigh.row, neigh.col+1));
                }
                if(neigh.row-1>=0 && grid[neigh.row-1][neigh.col]==1){
                    grid[neigh.row-1][neigh.col]=2;
                    queue.add(new Info(neigh.row-1, neigh.col));
                }
                if(neigh.row+1<grid.length && grid[neigh.row+1][neigh.col]==1){
                    grid[neigh.row+1][neigh.col]=2;
                    queue.add(new Info(neigh.row+1, neigh.col));
                }
                size--;
            }

            if(queue.size()>0){
                level++;
            }
        }

        
        // do one last check on grid
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j]==1){
                    return -1;
                }
            }
        }

        return level;
    }

    public class Info{
        int row;
        int col;

        public Info(int row, int col){
            this.row=row;
            this.col=col;
        }
    }
}

543. Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int diameter;
    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        longestPath(root);
        return diameter;
    }

    private int longestPath(TreeNode node){
        if(node == null) return 0;
        int left = longestPath(node.left);
        int right = longestPath(node.right);

        diameter = Math.max(diameter, left+right);
        
        return Math.max(left, right)+1;
    }
}

The key observation to make is: the longest path has to be between two leaf nodes. We can prove this with contradiction. Imagine that we have found the longest path, and it is not between two leaf nodes. We can extend that path by 1, by adding the child node of one of the end nodes (as at least one must have a child, given that they aren’t both leaves). This contradicts the fact that our path is the longest path. Therefore, the longest path must be between two leaf nodes.

Moreover, we know that in a tree, nodes are only connected with their parent node and 2 children. Therefore we know that the longest path in the tree would consist of a node, its longest left branch, and its longest right branch. So, our algorithm to solve this problem will find the node where the sum of its longest left and right branches is maximized. This would hint at us to apply Depth-first search (DFS) to count each node’s branch lengths, because it would allow us to dive deep into the leaves first, and then start counting the edges upwards.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameter;
    int diameterOfBinaryTree(TreeNode* root) {
        diameter = 0;
        traverse(root);
        return diameter;
    }
    int traverse(TreeNode* root){
        if(!root) return 0;
        int left = traverse(root -> left);
        int right = traverse(root -> right);
        diameter = max(diameter, left + right);
        return max(left, right) + 1;
    }
};

2257. Count Unguarded Cells in the Grid

You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith guard and jth wall respectively.

A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.

Return the number of unoccupied cells that are not guarded.

Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

Example 2:

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

Solution from leetcode

class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        int[][] res = new int[m][n];   //We create the matrix with the proper dimension
        int result = 0, cnti, cntj;
        for(int[] i : walls){       //We insert all the walls
            res[i[0]][i[1]] = 2;
        }
        for(int[] i : guards){      //We insert all the guards
            res[i[0]][i[1]] = 1;  
        }
        for(int i = 0; i < res.length;i++){
            for(int j = 0; j < res[i].length;j++){
                if(res[i][j] == 1){     //If we found a guard...
                    cnti = i;   //Position of the guard
                    cntj = j;   //Position of the guard
                    while(cnti-1 != -1 && res[cnti-1][cntj] != 2 && res[cnti-1][cntj] != 1){  //If we can go up in the matrix...
                        res[cnti-1][cntj] = 3;
                        cnti--;
                    }
                    cnti = i;  //We reset the value to the initial one
                    while(cnti+1 != m && res[cnti+1][cntj] != 2 && res[cnti+1][cntj] != 1){   //If we can go down in the matrix...
                        res[cnti+1][cntj] = 3;
                        cnti++;
                    }
                    cnti = i;  //We reset the value to the initial one
                    while(cntj-1 != -1 && res[cnti][cntj-1] != 2 && res[cnti][cntj-1] != 1){  //If we can go to left in the matrix...
                        res[cnti][cntj-1] = 3;
                        cntj--;
                    }
                    cntj = j;  //We reset the value to the initial one
                    while(cntj+1 != n && res[cnti][cntj+1] != 2 && res[cnti][cntj+1] != 1){  //If we can go to rigth in the matrix...
                        res[cnti][cntj+1] = 3;
                        cntj++;
                    }
                }
            }
        }
        for(int[] i : res){   //Once we have marked the correct squares in the matrix...
            for(int j : i){
                if(j == 0){   //If we find a '0', we add one to the counter as it is an unguarded cell
                    result++;
                }
            }
        }
        return result;  //We return the number of unguarded cells
    }
}

// Time limit exceeded solution

class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {

        HashMap<Integer, List<Integer>> rowMap = new HashMap<>();
        HashMap<Integer, List<Integer>> colMap = new HashMap<>();
        boolean [][]grid = new boolean[m][n];
        for(int[] w: walls){
            rowMap.putIfAbsent(w[0], new LinkedList());
            colMap.putIfAbsent(w[1], new LinkedList());
            rowMap.get(w[0]).add(w[1]);
            colMap.get(w[1]).add(w[0]);
            grid[w[0]][w[1]]=true;
        }

        // for every guard position, check all 4 directions
       
        for(int[] g: guards){
            int row=g[0];
            int col=g[1];
            grid[row][col]=true;

            // top
            int top = 0;
            if(colMap.containsKey(col)){
                List<Integer> topRows = colMap.get(col);
                for(Integer t: topRows){
                    if (t<row){
                        top = Math.max(t+1, top);
                    }
                }
            } 
            for(int i=row-1; i>=top; i--){
                grid[i][col]=true; // guarded
            }
            // right
            int right = n-1;
            if(rowMap.containsKey(row)){
                List<Integer> rightCols = rowMap.get(row);
                for(Integer r: rightCols){
                    if (r>col){
                        right = Math.min(r-1, right);
                    }
                }
            } 
            for(int i=col+1; i<=right; i++){
                grid[row][i]=true; // guarded
            }

            // bottom
            int bottom = m-1;
            if(colMap.containsKey(col)){
                List<Integer> bottomRows = colMap.get(col);
                for(Integer r: bottomRows){
                    if (r>row){
                        bottom = Math.min(r-1, bottom);
                    }
                }
            } 
            for(int i=row+1; i<=bottom; i++){
                grid[i][col]=true; // guarded
            }

            // left
            int left = 0;
            if(rowMap.containsKey(row)){
                List<Integer> leftCols = rowMap.get(row);
                for(Integer l: leftCols){
                    if (l<col){
                        left = Math.max(l+1, left);
                    }
                }
            } 
            for(int i=col-1; i>=left; i--){
                grid[row][i]=true; // guarded
            }
        }


        int count = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!grid[i][j]){
                    count++;
                }
            }
        }
      
        return count;
    }
}

112. Path sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return false;
        if(root->left == nullptr && root->right == nullptr){
            return targetSum == root->val;
        }
        bool result = false;
        if(root->left!=nullptr){
            result = result || hasPathSum(root ->left, targetSum-root->val);
        }
        if(root->right!=nullptr){
            result = result || hasPathSum(root->right, targetSum-root->val);
        }
        return result;
    }
};

113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return result;
        vector<int> path;
        traverse(root, targetSum, path);
        return result;
    }
    void traverse(TreeNode* root, int targetSum, vector<int> path){
        
        if(root == nullptr) return;
        if(root->left == nullptr && root->right==nullptr){
            if(root->val == targetSum){
                std::vector<int> copyVec(path);
                copyVec.push_back(root->val);
                result.push_back(copyVec);
            }
            return;
        }

        if(root->left!=nullptr){
            std::vector<int> copyVec(path);
            copyVec.push_back(root->val);
            traverse(root->left, targetSum-root->val, copyVec);
        }
        if(root->right!=nullptr){
            std::vector<int> copyVec(path);
            copyVec.push_back(root->val);
            traverse(root->right, targetSum-root->val, copyVec);
        }
    }
};

437. Path Sum III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int count;
    int pathSum(TreeNode* root, int targetSum) {
        count = 0;
        vector<long int> allSums;
        traverse(root, targetSum, allSums);
        return count;
    }

    void traverse(TreeNode* root, long int targetSum, vector<long int> allSums){
        if(root == nullptr) return;

        for(auto it: allSums){
            if(it+root->val == targetSum){
                count++;
            }
        }

        if(root->val == targetSum){
            count++;
        }

        if(root->left != nullptr){
            vector<long int> allSumsCopyLeft(allSums);
            for(auto& it: allSumsCopyLeft){
                it = it + root->val;
            }
            allSumsCopyLeft.push_back(root->val);
            traverse(root->left, targetSum, allSumsCopyLeft);
        }

        if(root->right != nullptr){
            vector<long int> allSumsCopyRight(allSums);
            for(auto& it: allSumsCopyRight){
                it = it + root->val;
            }
            allSumsCopyRight.push_back(root->val);
            traverse(root->right, targetSum, allSumsCopyRight);
        }
    }
};

Check if current value is equal to target. Add current value to allSums and check again.

In the next iteration, add current value as a single element in the allSums, then add current value to the end of every list in sumList.

666. Path Sum IV

If the depth of a tree is smaller than 5, then this tree can be represented by an array of three-digit integers. For each integer in this array:

The hundreds digit represents the depth d of this node where 1 <= d <= 4.
The tens digit represents the position p of this node in the level it belongs to where 1 <= p <= 8. The position is the same as that in a full binary tree.
The units digit represents the value v of this node where 0 <= v <= 9.

Given an array of ascending three-digit integers nums representing a binary tree with a depth smaller than 5, return the sum of all paths from the root towards the leaves.

It is guaranteed that the given array represents a valid connected binary tree.

Example 1:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

Example 2:

Input: nums = [113,221]
Output: 4
Explanation: The tree that the list represents is shown. 
The path sum is (3 + 1) = 4.

// correct answer
class Solution {
public:
    unordered_map<int, int> values;
    int ans;
    int pathSum(vector<int>& nums) {
        ans=0;
        for(int n: nums){
            values[n/10]=n%10; // level+position -> value
        }
        dfs(nums[0]/10, 0);
        return ans;
    }
    void dfs(int node, int sum){
        if(values.count(node)==0) return;
        sum+=values[node];

        int depth = node/10;
        int position = node%10;
        int left = (depth+1)*10 + 2 * position -1; 
        // formula to get left child
        // when using a number starting from index 1
        int right = left + 1;

        if(values.count(left)==0 && values.count(right)==0){
            // current node is leaf
            ans+=sum;
        } else {
            dfs(left, sum);
            dfs(right, sum);
        }
    }
};

class Solution {
    public int pathSum(int[] nums) {
        HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
        int lastRow = 0;
        for(int num: nums){
            int depth = num/100;
            int position = (num/10)%10;
            int val = num%10;
            HashMap<Integer, Integer> next = map.getOrDefault(depth, new HashMap<>());
            int parentVal = 0;
            if(depth-1 >= 1){
                if(position%2!=0){
                    // check parent node
                    parentVal = Math.max(map.get(depth-1).getOrDefault((position/2+1), 0), parentVal);
                } else {
                    parentVal = Math.max(map.get(depth-1).getOrDefault((position/2), 0), parentVal);
                }   
            }
            next.put(position, val+parentVal);
            map.put(depth, next);
            lastRow = depth;
        }

        int sum = 0;

        for(int i=1; i<=lastRow; i++){
            HashMap<Integer, Integer> val = map.get(i);
            for(Map.Entry<Integer, Integer> each: val.entrySet()){
                if(map.get(i+1) == null || (map.get(i+1).get((each.getKey()*2)) == null && map.get(i+1).get((each.getKey()*2)-1) == null )){ // next row            
                    sum+=each.getValue(); // add if it is leaf
                } 
            }
        }

        return sum;
    }
}

226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

At every level, we just need to swap left and right child nodes.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

1615. Maximal Network Rank

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Need to read the question properly….pairs of nodes doesn’t need to be connected

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();

        for(int i=0; i<roads.length; i++){
            int from = roads[i][0];
            int to = roads[i][1];

            map.putIfAbsent(from, new HashSet<Integer>());
            map.putIfAbsent(to, new HashSet<Integer>());

            map.get(from).add(to);
            map.get(to).add(from);
        }

        int max = 0;
        for(Map.Entry<Integer, HashSet<Integer>> entry: map.entrySet()){
            int key = entry.getKey();
            HashSet<Integer> neighs = entry.getValue();
            for(int otherNodes=0; otherNodes<n; otherNodes++){ // Pairs of nodes doesn't need to be connected
                if(otherNodes == key) continue;
                HashSet<Integer> neighsNeighs = map.getOrDefault(otherNodes, new HashSet<>());
                int totalSize = neighsNeighs.size() + neighs.size();
                if(neighsNeighs.contains(key)) totalSize--; // remove duplicate edge
                max = Math.max(max, totalSize);
            }

        }
        return max;
    }
}

124. Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<TreeNode, Integer> map; // value: Max value one get by including the node in it's path
    int maxVal = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        map = new HashMap<>();
        traverse(root);
        return maxVal;
    }

    public int traverse(TreeNode root){
        if(root == null) return 0;
        if(map.containsKey(root)) return map.get(root);
        int leftSum = traverse(root.left);
        int rightSum = traverse(root.right);
       
        int currMax = Math.max(root.val, Math.max(leftSum+root.val, rightSum+root.val));
        map.put(root, currMax);
        maxVal = Math.max(maxVal, Math.max(currMax, leftSum+rightSum+root.val));
        return currMax;
    }
}

The Map will only contain, for each node, the maximum value that a path can be if another node (parent) includes that node in it’s path. NOTE, that it is not representing the maximum PATH value one can get by including that node.

In currMax, we only take either the current node or the path on it’s left or right. We never take both left and right path since it violates the constraints of the question, if we happen to have a parent node that includes this current node. (it does not form a proper single line path)

Not sure if i am clear above but just read the code and go through an example.

We keep a separate variable, called maxVal which contains the maximum value of a possible path. Here, we can include the scenario where we sum up both left and right path because in this case, it forms a valid path.

742. Closest Leaf in a Binary Tree

Given the root of a binary tree where every node has a unique value and a target integer k, return the value of the nearest leaf node to the target k in the tree.

Nearest to a leaf means the least number of edges traveled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

Example 1:

Input: root = [1,3,2], k = 1
Output: 2
Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.

Example 2:

Input: root = [1], k = 1
Output: 1
Explanation: The nearest leaf node is the root node itself.

Example 3:

Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2
Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, List<TreeNode>> graph = new HashMap();
        // convert tree to graph 
        dfs(graph, root, null);

        Queue<TreeNode> queue = new LinkedList();
        Set<TreeNode> seen = new HashSet();
        // Find target node
        for (TreeNode node: graph.keySet()) {
            if (node != null && node.val == k) {
                queue.add(node);
                seen.add(node);
            }
        }

        // find nearest node
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                if (graph.get(node).size() <= 1)
                    return node.val; // is leaf, and nearest 🍃 
                for (TreeNode nei: graph.get(node)) {
                    if (!seen.contains(nei)) {
                        seen.add(nei);
                        queue.add(nei);
                    }
                }
            }
        }
        throw null;
    }

    public void dfs(Map<TreeNode, List<TreeNode>> graph, TreeNode node, TreeNode parent) {
        if (node != null) {
            if (!graph.containsKey(node)) graph.put(node, new LinkedList<TreeNode>());
            if (!graph.containsKey(parent)) graph.put(parent, new LinkedList<TreeNode>());
            graph.get(node).add(parent);
            graph.get(parent).add(node);
            dfs(graph, node.left, node);
            dfs(graph, node.right, node);
        }
    }
}

Time Complexity: O(N) where N is the number of nodes in the given input tree. 
We visit every node a constant number of times.

Space Complexity: O(N), the size of the graph.

Instead of a binary tree, if we converted the tree to a general graph, we could find the shortest path to a leaf using breadth-first search.

Algorithm

We use a depth-first search to record in our graph each edge travelled from parent to node.

After we use a breadth-first search on nodes that started with a value of k, so that we are visiting nodes in order of their distance to k. When the node is a leaf (it has one outgoing edge, where the root has a "ghost" edge to null), it must be the answer.

269. Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are

sorted lexicographically

by the rules of this new language.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there are multiple solutions, return any of them.

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

Solution — copied from editorial

Approach 2: Depth-First Search

Intuition

Another approach to the third part is to use a depth-first search. We still need to extract relations and then generate an adjacency list in the same way as before, but this time we don’t need the indegrees map.

Recall that in a depth-first search, nodes are returned once they either have no outgoing links left, or all their outgoing links have been visited. Therefore, the order in which nodes are returned by the depth-first search will be the reverse of a valid alphabet order.

Algorithm

If we made a reverse adjacency list instead of a forward one, the output order would be correct (without needing to be reversed). Remember that when we reverse the edges of a directed graph, the nodes with no incoming edges became the ones with no outgoing edges. This means that the ones at the start of the alphabet will now be the ones returned first.

One issue we need to be careful of is cycles. In directed graphs, we often detect cycles by using graph coloring. All nodes start as white, and then once they’re first visited they become grey, and then once all their outgoing nodes have been fully explored, they become black. We know there is a cycle if we enter a node that is currently grey (it works because all nodes that are currently on the stack are grey. Nodes are changed to black when they are removed from the stack).

class Solution {
    Map<Character, List<Character>> reverseAdjList = new HashMap<>();
    Map<Character, Boolean> seen = new HashMap<>();
    StringBuilder output = new StringBuilder();

    public String alienOrder(String[] words) {
        for(String word: words){
            for(char c : word.toCharArray()){
                reverseAdjList.putIfAbsent(c, new LinkedList<>());
            }
        }

        // Step 1: Find all edges and add reverse edges to reverseAdjList.
        for(int i=0; i<words.length-1; i++){
            String word1 = words[i];
            String word2 = words[i+1];
            // Check that word2 is not a prefix of word1.
            if(word1.length() > word2.length() && word1.startsWith(word2)){
                return "";
            }
            // Find the first non match and insert the corresponding relation.
            for(int j=0; j<Math.min(word1.length(), word2.length()); j++){
                if(word1.charAt(j) != word2.charAt(j)){
                    reverseAdjList.get(word2.charAt(j)).add(word1.charAt(j));
                    break;
                }
            }
        }

        for(Character c : reverseAdjList.keySet()){
            boolean result = dfs(c);
            if(!result) return "";
        }
        return output.toString();
    }

    private boolean dfs(Character c){
        if(seen.containsKey(c)){
            return seen.get(c);
        }
        seen.put(c, false);
        for(Character next: reverseAdjList.get(c)){
            boolean result = dfs(next);
            if(!result) return false;
        }
        seen.put(c, true);
        output.append(c);
        return true;
    }

}

261. Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // A tree should not have cycles, connected, single root
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for(int i=0; i<n; i++){
            adjacencyList.add(new LinkedList<>());
        }

        for(int[] e: edges){
            adjacencyList.get(e[0]).add(e[1]);
            adjacencyList.get(e[1]).add(e[0]);
        }
        // Use a stack to keep track of unexplored nodes.
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        
        // Use a map to keep track of how we got into each node.
        Map<Integer, Integer> parent = new HashMap<>();
        parent.put(0, -1);

        // While there are nodes remaining on the stack...
        while (!stack.isEmpty()) {
            int node = stack.pop(); // Take one off to visit.
            // Check for unseen neighbours of this node:
            for (int neighbour : adjacencyList.get(node)) {
                // Don't look at the trivial cycle.
                if (parent.get(node) == neighbour) {
                    continue;
                }
                // Check if we've already seen this node.
                if (parent.containsKey(neighbour)) {
                    return false; // There must be a cycle.
                }
                // Otherwise, put this neighbour onto stack
                // and record that it has been seen.
                stack.push(neighbour);
                parent.put(neighbour, node);
            }
        }

        return parent.size() == n;


    }
}

2101. Detonate the Maximum Bombs

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

class Solution {
HashSet<Integer> visited;
    public int maximumDetonation(int[][] bombs) {
        // compute min distance between 2 centers of 2 bombs
        // if the min distance is shorter than R1, then R1 can detonate R2.
        // For each bomb, we compute how many detonation it can cause. Then, put all these into a list
        // Perform DFS to see which will result in a maximum detonation
       
        HashMap<Integer, List<Integer>> bombsMap = new HashMap<>();
        for(int i=0; i<bombs.length; i++){
            List<Integer> impact = new LinkedList<>();
            for(int j=0; j<bombs.length; j++){
                if(j==i) continue;
                if(checkIfCanDetonate(bombs[i], bombs[j])){
                    impact.add(j);
                }
            }
            impact.add(i);
            bombsMap.put(i, impact);
        }
        int maxCount = 1;
        
        for(int i=0; i<bombs.length; i++){
            // for each bomb, traverse to see the max count;
            visited = new HashSet<>();
            int count = traverse(bombsMap, i);
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }
    public boolean checkIfCanDetonate(int[] bomb1, int[] bomb2){
        double dis = Math.sqrt(Math.pow(bomb1[0]-bomb2[0],2)+Math.pow(bomb1[1]-bomb2[1],2));
        return dis <= bomb1[2]; // no need to do || dis <= bomb2[2];
        /*
         * To determine whether bomb 1 detonates bomb 2, we can compare the Euclidean distance 
         * between their centers and the radius of bomb 1. If the distance is less than or equal
         * to the radius of bomb 1, then bomb 1 can detonate bomb 2. Note that this relationship 
         * is not commutative: bomb 1 detonating bomb 2 does not necessarily imply the converse is also true.
         */
    }
    public int traverse(HashMap<Integer, List<Integer>> bombsMap, int root){
     
        visited.add(root);
        List<Integer> neigh = bombsMap.get(root);
        if(neigh.size() == 0){
            return 0;
        };
        int count = 1;
        for(int n: neigh){
            if(n!=root && !visited.contains(n)){
                count += traverse(bombsMap, n);
            }
        }
        return count;
        
    }
}

Similar qns. Except here, each router has the same range of 10.

2285. Maximum Total Importance of Roads

ou are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.

You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.

Return the maximum total importance of all roads possible after assigning the values optimally.

Example 1:

Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 43
Explanation: The figure above shows the country and the assigned values of [2,4,5,3,1].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.

Example 2:

Input: n = 5, roads = [[0,3],[2,4],[1,3]]
Output: 20
Explanation: The figure above shows the country and the assigned values of [4,3,2,5,1].
- The road (0,3) has an importance of 4 + 5 = 9.
- The road (2,4) has an importance of 2 + 1 = 3.
- The road (1,3) has an importance of 3 + 5 = 8.
The total importance of all roads is 9 + 3 + 8 = 20.
It can be shown that we cannot obtain a greater total importance than 20.

Constraints:

2 <= n <= 5 * 104
1 <= roads.length <= 5 * 104
roads[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
There are no duplicate roads.

class Solution {

    public long maximumImportance(int n, int[][] roads) {
        long[] degree = new long[n];

        for (int[] edge : roads) {
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        Arrays.sort(degree);

        long value = 1;
        long totalImportance = 0;
        for (long d : degree) {
            totalImportance += (value * d);
            value++;
        }

        return totalImportance;
    }
}

// Time limit exceeded solution
class Solution {
    public long maximumImportance(int n, int[][] roads) {
        // the city that has the most connection should take the highest number first.

        
        PriorityQueue<Node> queue = new PriorityQueue<>((Node n1, Node n2) -> {
            return n2.getConnections().compareTo(n1.getConnections());
        }); 
        HashMap<Integer, Node> nodes = new HashMap<>();

        for(int i=0; i<roads.length; i++){
            Node node1 = nodes.getOrDefault(roads[i][0], new Node(roads[i][0]));
            Node node2 = nodes.getOrDefault(roads[i][1], new Node(roads[i][1]));
            node1.addConnection();
            node2.addConnection();
            
            queue.remove(node1);
            queue.remove(node2);
            queue.add(node1);
            queue.add(node2); 
            // the priority queue does not support reordering based
            // on the updated state of its elements.
            // Need to remove and add it

            nodes.put(roads[i][0], node1);
            nodes.put(roads[i][1], node2);

        }
        int queueSize = queue.size(); 
        int count = 0;
        int importance = n;
        while(!queue.isEmpty()){
            Node curr = queue.poll();
            count += (curr.connections * importance);
            importance--;
        }
        return count;
    }

    public class Node {
        int node;
        Integer connections;

        public Node(int node){
            this.node = node;
            this.connections = 0;
        }

        public void addConnection(){
            this.connections += 1;
        }

        public Integer getConnections(){
            return this.connections;
        }

        public String toString(){
            return String.valueOf(this.node) + " with connections " + String.valueOf(connections);
        }
    }
}

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

Alice and Bob have an undirected graph of n nodes and three types of edges:

Type 1: Can be traversed by Alice only.
Type 2: Can be traversed by Bob only.
Type 3: Can be traversed by both Alice and Bob.

Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

Example 1:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Example 2:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Example 3:

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

Solution from the Editorial

Intuition

We have N nodes connected via bidirectional edges; the edges can be of three types:

Type 1: Can be traversed by Alice only.
Type 2: Can be traversed by Bob only.
Type 3: Can be traversed by both Alice and Bob

We need to find the maximum number of edges that can be removed and still both Alice and Bob can reach any node starting from any node via the remaining edges. We can assume that there are two graphs, one for Alice and another one for Bob, the first graph for Alice has edges only of Type 1 & 3 and the second graph for Bob will have edges only of Type 2 & 3.

An edge is useful only if it connects two nodes that are not already connected via some other edge or path. How can we find if an edge is useful? The Disjoint Set Union data structure is very useful in solving these kind of problems. If you are not familiar with DSU, please go through our Explore Card. We will not talk about implementation details here and assume you are already familiar with the interface of DSU. The Disjoint Set Union can detect if two nodes are connected via some path or not in O(α(N)). (Here, α(N) is the extremely fast inverse Ackermann function).

We can use DSU to perform the union of two nodes for an edge and if the nodes were not connected earlier i.e. they have a different representative then we will know this edge is needed. For every edge, if the two nodes were not connected earlier, we know this edge is required. To get the answer, we can subtract the number of required edges from the total number of edges.

Since we need the minimum number of edges to connect all the nodes, the Type 3 edges are the most useful as one Type 3 edge adds two edges, one for Alice and one for Bob. Hence, we will first iterate over the edges of Type 3, and for these edges we will add the edge to both graphs.

In the end, we need to check if the graph for both Alice and Bob is connected or not. If yes, we can say the edges that we didn’t connect can be removed. To check if the individual graphs are connected we will check if the number of components in the graph is 1 or not.

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        // Different objects for Alice and Bob.
        UnionFind Alice = new UnionFind(n);
        UnionFind Bob = new UnionFind(n);

        int edgesRequired = 0;
        // Perform union for edges of type = 3, for both Alice and Bob.
        for (int[] edge : edges) {
            if (edge[0] == 3) {
                edgesRequired += (Alice.performUnion(edge[1], edge[2]) | Bob.performUnion(edge[1], edge[2]));
            }
        }

        // Perform union for Alice if type = 1 and for Bob if type = 2.
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                edgesRequired += Alice.performUnion(edge[1], edge[2]);
            } else if (edge[0] == 2) {
                edgesRequired += Bob.performUnion(edge[1], edge[2]);
            }
        }

        // Check if the Graphs for Alice and Bob have n - 1 edges or is a single component.
        if (Alice.isConnected() && Bob.isConnected()) {
            return edges.length - edgesRequired;
        }
        
        return -1;
    }

    private class UnionFind {
        int[] representative;
        int[] componentSize;
        // Number of distinct components in the graph.
        int components;

        // Initialize the list representative and componentSize
        // Each node is representative of itself with size 1.
        public UnionFind(int n) {
            components = n;
            representative = new int[n + 1];
            componentSize = new int[n + 1];

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

        // Get the root of a node.
        int findRepresentative(int x) {
            if (representative[x] == x) {
                return x;
            }

            // Path compression.
            return representative[x] = findRepresentative(representative[x]);
        }
        
        // Perform the union of two components that belongs to node x and node y.
        int performUnion(int x, int y) {       
            x = findRepresentative(x); y = findRepresentative(y);

            if (x == y) {
                return 0;
            }

            if (componentSize[x] > componentSize[y]) {
                componentSize[x] += componentSize[y];
                representative[y] = x;
            } else {
                componentSize[y] += componentSize[x];
                representative[x] = y;
            }

            components--;
            return 1;
        }

        // Returns true if all nodes get merged to one.
        boolean isConnected() {
            return components == 1;
        }
    }
}

Graphs/Trees Coding Questions

Recap on Java basics for coding interview

1. Basic class code

Important Algorithms/Data Structures and their complexity

Check if the given binary tree is balanced?

Graph Colouring

Network (Can a message reach a node in the network?)

Finding duplicate in an int array in O(n) time

Is this graph Bipartite? (Leetcode 785)

886. Possible Bipartition

684. Redundant Connection

685. Redundant Connection II

Path with Maximum Gold (Leetcode 1219)

Number of Islands (Leetcode 200)

305. Number of Islands II

Number of Distinct Islands (Leetcode 694) — Premium qns

Kth Smallest Element in a BST

Course Schedule Leetcode 207

Extension Leetcode 210 Course Schedule II

Construct Binary Tree from Preorder and Inorder Traversal

Leetcode 106 Construct Binary Tree from Inorder and Postorder Traversal

889. Construct Binary Tree from Preorder and Postorder Traversal

1008. Construct Binary Search Tree from Preorder Traversal

12. Leetcode 127 Word Ladder

Word Ladder 2

Minimum Genetic Mutation - LeetCode

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'. Suppose we…

13. Leetcode 365 Water and Jug Platform

14. Leet code 314 Binary Tree Inorder

15. Binary Tree PostOrder

16. Binary Tree PreOrder

17. Depth First Search

18. Breadth First Search

19. Topological Sort

20. Vertical Order Traversal of a Binary Tree

21. Insertion to BST

22. Check that a tree is symmetric

Leetcode 96. Unique Binary Search Trees

Leet Code 95 Generate all Unique Binary Search Tree Sequence

Leetcode 572 Subtree of another tree

Leet Code 235. Lowest Common Ancestor of a Binary Search Tree

Leet Code 236. Lowest Common Ancestor of a Binary Tree

298. Binary Tree Longest Consecutive Sequence

Leet Code 109. Convert Sorted List to Binary Search Tree

114. Flatten Binary Tree to Linked List

116. Populating Next Right Pointers in Each Node

117. Populating Next Right Pointers in Each Node II

129. Sum Root to Leaf Numbers

130. Surrounded Regions

310. Minimum Height Trees

323. Number of Connected Components in an Undirected Graph

662. Maximum Width of Binary Tree

I found the solution below to be easier….DFS…

994. Rotting Oranges

543. Diameter of Binary Tree

2257. Count Unguarded Cells in the Grid

112. Path sum

113. Path Sum II

437. Path Sum III

666. Path Sum IV

226. Invert Binary Tree

1615. Maximal Network Rank

124. Binary Tree Maximum Path Sum

742. Closest Leaf in a Binary Tree

269. Alien Dictionary

Solution — copied from editorial

Approach 2: Depth-First Search

261. Graph Valid Tree

2101. Detonate the Maximum Bombs

2285. Maximum Total Importance of Roads

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

The End :)

Written by LiveRunGrow