133. Clone Graph Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. 1 2 3 4 class Node { public int val; public List<Node> neighbors; } Test case format: For simplicity sake, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on....
1514. Path with Maximum Probability You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i]. Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability....
1306. Jump Game III Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0. Notice that you can not jump outside of the array at any time. 1 2 3 4 5 6 7 8 Example 1: Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true Explanation: All possible ways to reach at index 3 with value 0 are: index 5 -> index 4 -> index 1 -> index 3 index 5 -> index 6 -> index 4 -> index 1 -> index 3 1 2 3 4 5 6 7 Example 2: Input: arr = [4,2,3,0,3,1,2], start = 0 Output: true Explanation: One possible way to reach at index 3 with value 0 is: index 0 -> index 4 -> index 1 -> index 3 1 2 3 4 5 Example 3: Input: arr = [3,0,2,1,2], start = 2 Output: false Explanation: There is no way to reach at index 1 with value 0....
1584. Min Cost to Connect All Points You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points....
1813. Sentence Similarity III A sentence is a list of words that are separated by a single space with no leading or trailing spaces. For example, “Hello World”, “HELLO”, “hello world hello world” are all sentences. Words consist of only uppercase and lowercase English letters. Two sentences sentence1 and sentence2 are similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal....
872. Leaf-Similar Trees Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi. Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists. Notice that you can return the vertices in any order. 1 2 3 4 5 Example 1: Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3] Explanation: It's not possible to reach all the nodes from a single vertex....
1254. Number of Closed Islands Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s. Return the number of closed islands. 1 2 3 4 5 6 Example 1: Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2 Explanation: Islands in gray are closed because they are completely surrounded by water (group of 1s)....
695. Max Area of Island Given a non-empty 2D array grid of 0’s and 1’s, 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. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.) 1 2 3 4 5 6 7 8 9 10 Example 1: [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] Given the above grid, return 6....
1302. Deepest Leaves Sum Given the root of a binary tree, return the sum of values of its deepest leaves. 1 2 3 4 Example 1: Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15 1 2 3 4 Example 2: Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 19 Constraints: The number of nodes in the tree is in the range [1, 104]. 1 <= Node.val <= 100 Solution 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 38 /** * Definition for a binary tree node....
797. All Paths From Source to Target Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j])....
207. Course Schedule There are a total of n courses you have to take labelled from 0 to n - 1. Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai. Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses....
210. Course Schedule II There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses....
114. Flatten Binary Tree to Linked List Given the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. 1 2 3 4 Example 1: Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6] 1 2 3 4 Example 2: Input: root = [] Output: [] 1 2 3 4 Example 3: Input: root = [0] Output: [0] Constraints:...
107. Binary Tree Level Order Traversal II Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root). 1 2 3 4 Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]] 1 2 3 4 Example 2: Input: root = [1] Output: [[1]] 1 2 3 4 Example 3: Input: root = [] Output: [] Constraints:...
102. Binary Tree Level Order Traversal Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level). 1 2 3 4 Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] 1 2 3 4 Example 2: Input: root = [1] Output: [[1]] 1 2 3 4 Example 3: Input: root = [] Output: [] Constraints: The number of nodes in the tree is in the range [0, 2000]....