Problem 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. The area of an island is the number of cells with a value 1 in the island. Return the maximum area of an island in grid. If there is no island, return 0. ...
Problem 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. ...
Sum of Distances in Tree Problem Problem There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes. ...
Problem On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed. ...
Problem Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense). ...
Problem 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. Otherwise, return false. ...
Problem 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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array. ...
Graph - Breadth First Search OR BFS Traversal The Idea Compared to depth first search (DFS), this traversal method prioritizes exploring closer neighbours first. It ensures that all nodes at a similar distance from the starting point are visited before moving on to nodes further away. This creates a wave-like expansion outward, visiting all nodes at a specific distance before progressing to the next layer. Examples Example 1 We can thing of breadth first search as a “wave” walk through the graph. In other words we go level by level, as shown on the picture below. ...
Problem Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. Definition Lowest Common Ancestor Definition Examples Example 1: graph TD; 6; 6 --- 2; 6 --- 8; 2 --- 0; 2 --- 4; 8 --- 7; 8 --- 9; 4 --- 3; 4 --- 5; style 2 fill:#FF9933 style 8 fill:#FF9933 style 6 fill:#3399FF ...
Problem Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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. Examples 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 ...