Han Zhu's Study Notes

Given  n  nodes labeled from  0  to  n - 1  and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given  n = 5  and  edges = [[0, 1], [0, 2], [0, 3], [1, 4]] , return  true . Given  n = 5  and  edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] , return  false . Note : you can assume that no duplicate edges will appear in  edges . Since all edges are undirected,  [0, 1]  is the same as  [1, 0] and thus will not appear together in  edges . Thought process: A tree is a graph that doesn't have a cycle. BFS. When a node is polled from queue, iterate through its neighbors. If any of them is visited but not the node's parent, there is a cycle. If there are no edges, then the graph is a tree only if it has only one node. Build graph. Use a map of int -> list of int. Iterate through the edg...

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: 11110 11010 11000 00000 Answer: 1 Example 2: 11000 11000 00100 00011 Answer: 3 Thought process: BFS. islands = 0. Iterate through every number on the grid. For each number, if it's 1: islands++. Change the number to 0. For each neighbor of the number, if it's 1, offer it to the queue. Return islands. Solution 1 (BFS): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { private final int [][] directions = { { - 1 , 0 }, { 0 , - 1 }, { 1 , 0 }, { 0 , 1 } }; public int numIslands ( char [][] grid) { int num = 0 ; for ( int i = 0 ; i < grid....

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given  [100, 4, 200, 1, 3, 2] , The longest consecutive elements sequence is  [1, 2, 3, 4] . Return its length:  4 . Your algorithm should run in O( n ) complexity. Thought process: Iterate through the array, use a hashset to store all the numbers. Iterate through the array again, when I see a number, I check if number-- is in the set until it's not. If it's in the set, remove it from the set. Check number++ in the same fashion. This gives me O(n) time complexity because every number is iterated at most once. Solution 1 (Set): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class Solution { public int longestConsecutive ( int [] nums ) { Set < Integer > set = new HashSet <>(); for ( int num : nums ) { set . add ( num ); } ...

Given  n  nodes labeled from  0  to  n - 1  and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1: 0 3 | | 1 --- 2 4 Given  n = 5  and  edges = [[0, 1], [1, 2], [3, 4]] , return  2 . Example 2: 0 4 | | 1 --- 2 --- 3 Given  n = 5  and  edges = [[0, 1], [1, 2], [2, 3], [3, 4]] , return  1 . Note: You can assume that no duplicate edges will appear in  edges . Since all edges are undirected,  [0, 1]  is the same as  [1, 0]  and thus will not appear together in  edges . Thought process: This question is a good practice on union-find. The idea is to think of each connected component as a tree. As we iterate through the edges, we set one of the node as the parent node of the other and decrement n. This ...