Graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quick Find:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.root = [i for i in range(size)]\n",
    "\n",
    "    def find(self, x): #O(1)\n",
    "        return self.root[x]\n",
    "\t\t\n",
    "    def union(self, x, y): #O(n)\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            for i in range(len(self.root)):\n",
    "                if self.root[i] == rootY:\n",
    "                    self.root[i] = rootX\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quick Union"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.root = [i for i in range(size)]\n",
    "\n",
    "    def find(self, x): #search through parents, if not root go next O(N)\n",
    "        while x != self.root[x]:\n",
    "            x = self.root[x]\n",
    "        return x #found the root node\n",
    "    \n",
    "    def union(self, x, y): #<= O(N)\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            self.root[rootY] = rootX\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Union By Rank (optimize Quick Union)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.root = [i for i in range(size)]\n",
    "        self.rank = [1] * size # height of 1\n",
    "\n",
    "    def find(self, x): #O(log N)\n",
    "        while x != self.root[x]:\n",
    "            x = self.root[x]\n",
    "        return x\n",
    "    def union(self, x, y): #O(logN)\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY: #x and y not connected\n",
    "            if self.rank[rootX] > self.rank[rootY]: # taller tree wins\n",
    "                self.root[rootY] = rootX\n",
    "            elif self.rank[rootX] < self.rank[rootY]:\n",
    "                self.root[rootX] = rootY\n",
    "            else:\n",
    "                self.root[rootY] = rootX\n",
    "                self.rank[rootX] += 1 #height equal needs augment\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Path Compression (optimize Quick Union to deal with long pathes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.root = [i for i in range(size)]\n",
    "\n",
    "    def find(self, x): #use recursion to directly get to root node.\n",
    "        if x == root[x]:\n",
    "            return x\n",
    "        self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "    def union(self, x, y): #<= O(logN)\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            self.root[rootY] = rootX\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Path Compression + Union By Rank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.root = [i for i in range(size)]\n",
    "        # Use a rank array to record the height of each vertex, i.e., the \"rank\" of each vertex.\n",
    "        # The initial \"rank\" of each vertex is 1, because each of them is\n",
    "        # a standalone vertex with no connection to other vertices.\n",
    "        self.rank = [1] * size\n",
    "\n",
    "    # The find function here is the same as that in the disjoint set with path compression.\n",
    "    def find(self, x):\n",
    "        if x == self.root[x]:\n",
    "            return x\n",
    "        self.root[x] = self.find(self.root[x])\n",
    "        return self.root[x]\n",
    "\n",
    "    # The union function with union by rank\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] > self.rank[rootY]:\n",
    "                self.root[rootY] = rootX\n",
    "            elif self.rank[rootX] < self.rank[rootY]:\n",
    "                self.root[rootX] = rootY\n",
    "            else:\n",
    "                self.root[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "\n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 947. Most Stones Removed with Same Row or Column\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.\n",
    "\n",
    "A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.\n",
    "\n",
    "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\n",
    "\n",
    "In the previous approaches, the building of the graph was a costly task: we had to iterate over every pair of stones to check if they share the row or column. Can we do better? Can we connect the stones in a different way without iterating over every pair? One thing to observe here is that we only care about the number of components not the structure of the graph. So as long as the number of components is the same, we can make it.\n",
    "\n",
    "We know the stones with the same row are connected, so instead of checking for all the pairs, we can use the row to represent the stones with this row, similarly for the same column. For example, if we have a stone at (x, y), then we connect all the stones with the same x coordinate, and similarly we connect all the stones with the same y coordinate. Now we can connect all the stones under the x-coordinate with those under the y-coordinate. This is equivalent to connecting the x and y itself.\n",
    "\n",
    "But we need a way to distinguish between the same value for x-coordinate and y-coordinate. For this, we add the value K = 10001K=10001 to the y-coordinates to map them in different ranges. We chose the value 1000110001 as the range for the coordinates is [0, 10000].\n",
    "\n",
    "## Algorithm\n",
    "\n",
    "\n",
    "Iterate over the stones and for each stone coordinate (x, y) add an edge in the adjacency list from x to y + K, here K is equal to 10001.\n",
    "Initialize a hashmap or array, visited, to track the visited vertices.\n",
    "Define a componentCount variable and initialize it to zero.\n",
    "Iterate over each stone from 0 to 2 * K + 1, and if the stone is not in visited, start a DFS from it. Add every stone visited during the DFS to the visited.\n",
    "Every time a new DFS starts, increment the counter variable componentCount by one.\n",
    "Return length(stones) - componentCount."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeStones(self, stones: List[List[int]]) -> int:\n",
    "    UF = {}\n",
    "    def find(x):\n",
    "        if x != UF[x]:\n",
    "            UF[x] = find(UF[x])\n",
    "        return UF[x]\n",
    "    def union(x, y):\n",
    "        UF.setdefault(x, x)\n",
    "        UF.setdefault(y, y)\n",
    "        UF[find(x)] = find(y)\n",
    "\n",
    "    for i, j in stones:\n",
    "        union(i, ~j)\n",
    "    return len(stones) - len({find(x) for x in UF})\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 990.Satisfiability of Equality Equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: \"xi==yi\" or \"xi!=yi\".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.\n",
    "\n",
    "Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def equationsPossible(self, equations: List[str]) -> bool:\n",
    "    root = list(range(26))\n",
    "\n",
    "    def find(x):\n",
    "        if x != root[x]:\n",
    "            root[x] = find(root[x])\n",
    "        return root[x]\n",
    "\n",
    "    def union(x, y):\n",
    "        x, y = find(x), find(y)\n",
    "        if root[x] != root[y]:\n",
    "            root[x] = y\n",
    "\n",
    "    for eqn in equations:\n",
    "        if eqn[1] == '=':\n",
    "            x, y = ord(eqn[0])-ord('a'), ord(eqn[3])-ord('a')\n",
    "            union(x, y)\n",
    "\n",
    "    for eqn in equations:\n",
    "        if eqn[1] == '!':\n",
    "            x, y = ord(eqn[0])-ord('a'), ord(eqn[3])-ord('a')\n",
    "            if find(x) == find(y):\n",
    "                return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def equationsPossible(self, equations: List[str]) -> bool:\n",
    "        graph = [[] for _ in range(26)]\n",
    "        for eqn in equations:\n",
    "            if eqn[1:3] == \"==\":\n",
    "                x = ord(eqn[0]) - ord('a')\n",
    "                y = ord(eqn[3]) - ord('a')\n",
    "                graph[x].append(y)\n",
    "                graph[y].append(x)\n",
    "        color = [-1] * 26\n",
    "        \n",
    "        def dfs(node, c):\n",
    "            if color[node] == -1:\n",
    "                color[node] = c\n",
    "                for nei in graph[node]:\n",
    "                    dfs(nei, c)\n",
    "                    \n",
    "        for i in range(26):\n",
    "            if color[i]== -1:\n",
    "                dfs(i, i)\n",
    "        \n",
    "        for eqn in equations:\n",
    "            if eqn[1] == \"!\":\n",
    "                x = ord(eqn[0]) - ord('a')\n",
    "                y = ord(eqn[3]) - ord('a')\n",
    "                if color[x] == color[y]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 399. Evaluate Division\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.\n",
    "\n",
    "You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.\n",
    "\n",
    "Return the answers to all queries. If a single answer cannot be determined, return -1.0.\n",
    "\n",
    "Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "        #adjacency list\n",
    "        val_dic = defaultdict(defaultdict)\n",
    "        for (source, dest), value in zip(equations, values):\n",
    "            val_dic[source][dest] = value\n",
    "            val_dic[dest][source] = 1/ value\n",
    "        \n",
    "        # print(val_dic)\n",
    "        \n",
    "        def backtrack_eval(curr, target, acc_product, visited):\n",
    "            visited.add(curr)\n",
    "            ret = -1.0\n",
    "            neighbors = val_dic[curr]\n",
    "            if target in neighbors:\n",
    "                ret = acc_product * neighbors[target]\n",
    "            else:\n",
    "                for neighbor, value in neighbors.items():\n",
    "                    if neighbor in visited:\n",
    "                        continue\n",
    "                    ret = backtrack_eval(neighbor, target, acc_product * value, visited)\n",
    "                    if ret != -1.0:\n",
    "                        break\n",
    "            visited.remove(curr)\n",
    "            return ret\n",
    "        \n",
    "        results = []\n",
    "        for divident, divisor in queries:\n",
    "            if divident not in val_dic or divisor not in val_dic:\n",
    "                ret = -1.0\n",
    "            elif divident == divisor:\n",
    "                ret = 1.0\n",
    "            else:\n",
    "                visited = set()\n",
    "                ret = backtrack_eval(divident, divisor, 1, visited)\n",
    "            results.append(ret)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Union Find Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:\n",
    "    gid_weight = {}\n",
    "\n",
    "    def find(node_id):\n",
    "        if node_id not in gid_weight:\n",
    "            gid_weight[node_id] = (node_id, 1)\n",
    "        group_id, node_weight = gid_weight[node_id]\n",
    "        if group_id != node_id:\n",
    "            new_group_id, group_weight = find(group_id)\n",
    "            gid_weight[node_id] = (new_group_id, node_weight * group_weight)\n",
    "        return gid_weight[node_id]\n",
    "\n",
    "    def union(dividend, divisor, value):\n",
    "        dividend_gid, dividend_weight = find(dividend)\n",
    "        divisor_gid, divisor_weight = find(divisor)\n",
    "        if dividend_gid != divisor_gid:\n",
    "            gid_weight[dividend_gid] = (divisor_gid, divisor_weight * value /dividend_weight)\n",
    "\n",
    "    for (dividend, divisor), value in zip(equations, values):\n",
    "        union(dividend, divisor, value)\n",
    "\n",
    "    results = []\n",
    "    for (dividend, divisor) in queries:\n",
    "        if dividend not in gid_weight or divisor not in gid_weight:\n",
    "            results.append(-1.0)\n",
    "        else:\n",
    "            dividend_gid, dividend_weight = find(dividend)\n",
    "            divisor_gid, divisor_weight = find(divisor)\n",
    "            if dividend_gid != divisor_gid:\n",
    "                results.append(-1.0)\n",
    "            else:\n",
    "                results.append(dividend_weight/divisor_weight)\n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 547. Number of Provinces\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findCircleNum(self, isConnected: List[List[int]]) -> int:\n",
    "    if not isConnected or len(isConnected) == 0:\n",
    "        return 0\n",
    "\n",
    "    length = len(isConnected)\n",
    "    parent = [i for i in range(length)]\n",
    "    count = length\n",
    "\n",
    "    def find(x):\n",
    "        if x != parent[x]:\n",
    "            parent[x] = find(parent[x])\n",
    "        return parent[x]\n",
    "\n",
    "    #union\n",
    "    def union(x, y):\n",
    "        nonlocal count\n",
    "        par_x = find(x)\n",
    "        par_y = find(y)\n",
    "        if par_x != par_y:\n",
    "            parent[par_x] = par_y\n",
    "            count-= 1\n",
    "\n",
    "    for row in range(length):\n",
    "        for col in range(row+1, length):\n",
    "            if isConnected[row][col] == 1:\n",
    "                union(row, col)\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 133. Clone Graph\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Given a reference of a node in a connected undirected graph.\n",
    "\n",
    "Return a deep copy (clone) of the graph.\n",
    "\n",
    "Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.\n",
    "\n",
    "class Node {\n",
    "    public int val;\n",
    "    public List<Node> neighbors;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "    def dfs(node, m):\n",
    "        for neigh in node.neighbors:\n",
    "            if neigh not in m:\n",
    "                m[neigh] = Node(neigh.val)\n",
    "                dfs(neigh, m)\n",
    "            m[node].neighbors.append(m[neigh])\n",
    "    if not node:\n",
    "        return node\n",
    "    m = {node: Node(node.val)}\n",
    "    dfs(node, m)\n",
    "    return m[node]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cloneGraph1(self, node): #DFS iteratively\n",
    "    if not node:\n",
    "        return node\n",
    "    m = {node: Node(node.val)}\n",
    "    stack = [node]\n",
    "    while stack:\n",
    "        n = stack.pop()\n",
    "        for neigh in n.neighbors:\n",
    "            if neigh not in m:\n",
    "                stack.append(neigh)\n",
    "                m[neigh] = Node(neigh.val)\n",
    "            m[n].neighbors.append(m[neigh])\n",
    "    return m[node]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cloneGraph2(self, node): # BFS \n",
    "        if not node:\n",
    "            return node\n",
    "        m = {node: Node(node.val)}\n",
    "        deque = collections.deque([node])\n",
    "        while deque:\n",
    "            n = deque.popleft()\n",
    "            for neigh in n.neighbors:\n",
    "                if neigh not in m:\n",
    "                    deque.append(neigh)\n",
    "                    m[neigh] = Node(neigh.val)\n",
    "                m[n].neighbors.append(m[neigh])\n",
    "        return m[node]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __init__(self):\n",
    "    # Dictionary to save the visited node and it's respective clone\n",
    "    # as key and value respectively. This helps to avoid cycles.\n",
    "    self.visited = {}\n",
    "\n",
    "def cloneGraph(self, node):\n",
    "    \"\"\"\n",
    "    :type node: Node\n",
    "    :rtype: Node\n",
    "    \"\"\"\n",
    "    if not node:\n",
    "        return node\n",
    "\n",
    "    # If the node was already visited before.\n",
    "    # Return the clone from the visited dictionary.\n",
    "    if node in self.visited:\n",
    "        return self.visited[node]\n",
    "\n",
    "    # Create a clone for the given node.\n",
    "    # Note that we don't have cloned neighbors as of now, hence [].\n",
    "    clone_node = Node(node.val, [])\n",
    "\n",
    "    # The key is original node and value being the clone node.\n",
    "    self.visited[node] = clone_node\n",
    "\n",
    "    # Iterate through the neighbors to generate their clones\n",
    "    # and prepare a list of cloned neighbors to be added to the cloned node.\n",
    "    if node.neighbors:\n",
    "        clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors]\n",
    "\n",
    "    return clone_node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* BFS Template need to remember"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "    if not node:\n",
    "        return node\n",
    "    queue = [node]\n",
    "    seen = {}\n",
    "    seen[node] = Node(node.val, [])\n",
    "    while queue:\n",
    "        curr_node = queue.pop(0)\n",
    "        for neighbor in curr_node.neighbors:\n",
    "            if neighbor not in seen:\n",
    "                seen[neighbor] = Node(neighbor.val, [])\n",
    "                queue.append(neighbor)\n",
    "            seen[curr_node].neighbors.append(seen[neighbor])\n",
    "    return seen[node]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 207. Course Schedule\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.\n",
    "Return true if you can finish all courses. Otherwise, return false."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numCourses = 2\n",
    "prerequisites = [[1,0]]\n",
    "# True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numCourses = 2\n",
    "prerequisites = [[1,0],[0,1]]\n",
    "# False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution1():    \n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        self.adj_dict = defaultdict(set)\n",
    "        for i, j in prerequisites:\n",
    "            self.adj_dict[i].add(j)\n",
    "\n",
    "        self.Visited = [0] * numCourses\n",
    "        self.Ans, self.FoundCycle = [], 0\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if self.FoundCycle == 1: break      # early stop if the loop is found\n",
    "            if self.Visited[i] == 0:\n",
    "                self.dfs(i)\n",
    "     \n",
    "        return [] if self.FoundCycle == 1 else self.Ans\n",
    "\n",
    "    def dfs(self, start):\n",
    "        if self.FoundCycle == 1:   return     # early stop if the loop is found    \n",
    "        if self.Visited[start] == 1:\n",
    "            self.FoundCycle = 1               # loop is found\n",
    "        if self.Visited[start] == 0:           # node is not visited yet, visit it\n",
    "            self.Visited[start] = 1             # color current node as gray\n",
    "            for neib in self.adj_dict[start]:   # visit all its neibours\n",
    "                self.dfs(neib)\n",
    "            self.Visited[start] = 2             # color current node as black\n",
    "            self.Ans.append(start)              # add node to answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#topological sort methods  We always take the courses with no unstudied prereqs and so on until no more courses we can take. \n",
    "#The oud[i] is the number of prereqs for course i and indegree keep a list of courses require course i.\n",
    "def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "    indegree = [set() for _ in range(numCourses)]\n",
    "    outdegree = [[] for _ in range(numCourses)]\n",
    "    for pre in prerequisites:\n",
    "        indegree[pre[0]].add(pre[1])\n",
    "        outdegree[pre[1]].append(pre[0])\n",
    "    start, count = [i for i in range(numCourses) if not indegree[i]], 0\n",
    "    while start: # start contains courses without prerequisites\n",
    "        newStart = []\n",
    "        for i in start:\n",
    "            count += 1 # add one course which can finish\n",
    "            for j in outdegree[i]:\n",
    "                indegree[j].remove(i)\n",
    "                if not indegree[j]:\n",
    "                    newStart.append(j)\n",
    "        start = newStart\n",
    "    return count == numCourses # all courses will be visited \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "def canFinish3(numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "\n",
    "    ind = [[] for _ in range(numCourses)]  # indegree\n",
    "    oud = [0] * numCourses  # outdegree\n",
    "    for preq in prerequisites:\n",
    "        oud[preq[0]] += 1\n",
    "        ind[preq[1]].append(preq[0])\n",
    "    dq = deque()\n",
    "    for i in range(numCourses):\n",
    "        if oud[i] == 0:\n",
    "            dq.append(i)\n",
    "    k = 0\n",
    "    while dq:\n",
    "        x = dq.popleft()\n",
    "        k += 1\n",
    "        for i in ind[x]:\n",
    "            oud[i] -= 1\n",
    "            if oud[i] == 0:\n",
    "                dq.append(i)\n",
    "    return k == numCourses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def canFinish2(numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "    graph = [[] for _ in range(numCourses)]\n",
    "    visited = [0 for _ in range(numCourses)]\n",
    "    for a, b in prerequisites:\n",
    "        graph[a].append(b)\n",
    "    \n",
    "    #dfs logic: one node has 3 states:0 not visited, 1 visited, -1 being visited             # state -1  : vertex is being processed. Either all of its descendants\n",
    "            #             are not processed or it's still in the function call stack.\n",
    "    def dfs(i):\n",
    "        if visited[i] == -1:    # This vertex is being processed and it means we have a cycle.\n",
    "            return False\n",
    "        if visited[i] == 1:\n",
    "            return True\n",
    "        visited[i] = -1\n",
    "        for neigh in graph[i]:\n",
    "            if not dfs(neigh):\n",
    "                return False\n",
    "        visited[i] = 1\n",
    "        return True\n",
    "    \n",
    "    for i in range(numCourses):\n",
    "        if not dfs(i):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "canFinish(numCourses, prerequisites)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "canFinish3(numCourses, prerequisites)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "canFinish2(numCourses, prerequisites)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Solution1().canFinish(numCourses, prerequisites)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 210. Course Schedule II\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numCourses = 4\n",
    "prerequisites = [[1,0],[2,0],[3,1],[3,2]]\n",
    "#Output: [0,2,1,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "    graph = [[] for _ in range(numCourses)]\n",
    "    visited = [0 for _ in range(numCourses)]\n",
    "    for preq in prerequisites:\n",
    "        graph[preq[0]].append(preq[1])\n",
    "    print('start:', graph, visited)\n",
    "\n",
    "    #dfs logic: one node has 3 states:0 not visited, 1 visited, -1 being visited             # state -1  : vertex is being processed. Either all of its descendants\n",
    "            #             are not processed or it's still in the function call stack.\n",
    "    def dfs(i, res):\n",
    "        if visited[i] == -1:    # This vertex is being processed and it means we have a cycle.\n",
    "            return False\n",
    "        if visited[i] == 1:\n",
    "            return res\n",
    "        visited[i] = -1\n",
    "        for neigh in graph[i]:\n",
    "            if not dfs(neigh, res):\n",
    "                return False\n",
    "        visited[i] = 1\n",
    "        print(visited)\n",
    "        res.append(i)\n",
    "        return res\n",
    "    res = []\n",
    "    for i in range(numCourses):\n",
    "        if not dfs(i, res):\n",
    "            return []\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findOrder(numCourses, prerequisites)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "    ind = [[] for _ in range(numCourses)]  # indegree\n",
    "    oud = [0] * numCourses  # outdegree\n",
    "    for preq in prerequisites:\n",
    "        oud[preq[0]] += 1\n",
    "        ind[preq[1]].append(preq[0])\n",
    "    print(ind, oud)\n",
    "    dq = deque()\n",
    "    for i in range(numCourses):\n",
    "        if oud[i] == 0:\n",
    "            dq.append(i)\n",
    "    k = 0\n",
    "    res = []\n",
    "    while dq:\n",
    "        print(dq)\n",
    "        x = dq.popleft()\n",
    "        res.append(x)\n",
    "        k += 1\n",
    "        for i in ind[x]:\n",
    "            oud[i] -= 1\n",
    "            if oud[i] == 0:\n",
    "                dq.append(i)\n",
    "    if k == numCourses:\n",
    "        return res\n",
    "    else:\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findOrder(numCourses, prerequisites)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review Kahan's Algorithm\n",
    "This approach is much easier to think about intuitively as will be clear from the following point/fact about topological ordering.\n",
    "\n",
    "The first node in the topological ordering will be the node that doesn't have any incoming edges. Essentially, any node that has an in-degree of 0 can start the topologically sorted order. If there are multiple such nodes, their relative order doesn't matter and they can appear in any order.\n",
    "\n",
    "Our current algorithm is based on this idea. We first process all the nodes/course with 0 in-degree implying no prerequisite courses required. If we remove all these courses from the graph, along with their outgoing edges, we can find out the courses/nodes that should be processed next. These would again be the nodes with 0 in-degree. We can continuously do this until all the courses have been accounted for.\n",
    "\n",
    "Algorithm\n",
    "\n",
    "1. Initialize a queue, Q to keep a track of all the nodes in the graph with 0 in-degree.\n",
    "2. Iterate over all the edges in the input and create an adjacency list and also a map of node v/s in-degree.\n",
    "3. Add all the nodes with 0 in-degree to Q.\n",
    "4. The following steps are to be done until the Q becomes empty.\n",
    "    1. Pop a node from the Q. Let's call this node, N.\n",
    "    2. For all the neighbors of this node, N, reduce their in-degree by 1. If any of the nodes' in-degree reaches 0, add it to the Q.\n",
    "    3. Add the node N to the list maintaining topologically sorted order.\n",
    "    4. Continue from step 4.1.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 785. Is Graph Bipartite?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:\n",
    "\n",
    "- There are no self-edges (graph[u] does not contain u).\n",
    "- There are no parallel edges (graph[u] does not contain duplicate values).\n",
    "- If v is in graph[u], then u is in graph[v] (the graph is undirected).\n",
    "- The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.\n",
    "A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.\n",
    "\n",
    "Return true if and only if it is bipartite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]\n",
    "Output: false\n",
    "Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n, colored = len(graph), {}\n",
    "        def dfs_color(color, idx, graph, colored):\n",
    "            if idx in colored:\n",
    "                return color == colored[idx]\n",
    "            colored[idx] = color                            \n",
    "            return all(dfs_color(-color, nb, graph, colored) for nb in graph[idx])\n",
    "    \n",
    "        return all(i in colored or dfs_color(1, i, graph, colored) for i in range(n)) \t\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBipartite(self, graph):\n",
    "        color = {}\n",
    "        def dfs(pos):\n",
    "            for i in graph[pos]:\n",
    "                if i in color:\n",
    "                    if color[i] == color[pos]:\n",
    "                        return False\n",
    "                else:\n",
    "                    color[i] = 1 - color[pos]\n",
    "                    if not dfs(i):\n",
    "                        return False\n",
    "            return True\n",
    "        for i in range(len(graph)):\n",
    "            if i not in color:\n",
    "                color[i] = 0\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # Dictionary to store all the nodes we have visited\n",
    "        color = {}\n",
    "        # Function to check if the visited node is valid\n",
    "        # input the node (pos) we want to validate\n",
    "        def dfs(pos):\n",
    "            # For all the nodes that are connected to the node we visit\n",
    "            for i in graph[pos]:\n",
    "                # If that node has been visited before\n",
    "                if i in color:\n",
    "                    # Check if the node is same color to the node we are visiting\n",
    "                    if color[i] == color[pos]:\n",
    "                        # If they are the same it is wrong\n",
    "                        # Return false\n",
    "                        return False\n",
    "                # If if has not been colored yet\n",
    "                else:\n",
    "                    # Color it with the color opposite to color[pos]\n",
    "                    color[i] = 1 - color[pos]\n",
    "                    # Continue to do DFS search with this node we just colored\n",
    "                    # If the check returns false\n",
    "                    if not dfs(i):\n",
    "                        # Return false\n",
    "                        return False\n",
    "            # If passed DFS, return True\n",
    "            return True\n",
    "        \n",
    "        # Go through all the nodes in the graph\n",
    "        for i in range(len(graph)):\n",
    "            # We will have to check if the node, and the nodes connected, are valid\n",
    "            # If this node is not visited\n",
    "            if i not in color:\n",
    "                # color the node with 0\n",
    "                color[i] = 0\n",
    "                # Then do the check\n",
    "                # If the check returns False\n",
    "                if not dfs(i):\n",
    "                    # Return False\n",
    "                    return False\n",
    "        # If all nodes pass, return True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n, colored = len(graph), {}\n",
    "        for i in range(n):\n",
    "            if i not in colored and graph[i]:\n",
    "                colored[i] = 1\n",
    "                q = collections.deque([i])\n",
    "                while q:\n",
    "                    cur = q.popleft()\n",
    "                    for nb in graph[cur]:\n",
    "                        if nb not in colored:\n",
    "                            colored[nb] = -colored[cur]\n",
    "                            q.append(nb)\n",
    "                        elif colored[nb] == colored[cur]:\n",
    "                            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### union find Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBipartite(self, graph):\n",
    "    length = len(graph)\n",
    "    parent = [i for i in range(length)]\n",
    "    \n",
    "    def find(x):\n",
    "        if x!=parent[x]:\n",
    "            parent[x]=find(parent[x])#rank compression\n",
    "        return parent[x]\n",
    "    \n",
    "    def union(x,y):\n",
    "        px,py=find(x),find(y)\n",
    "        if px!=py:\n",
    "            parent[px]=py\n",
    "           \n",
    "    for i in range(length):\n",
    "        pari=find(i)\n",
    "        for j in graph[i]:\n",
    "            if find(j)==pari:\n",
    "                return False\n",
    "            union(graph[i][0],j)\n",
    "            \n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 310. Minimum Height Trees\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "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).\n",
    "\n",
    "Return a list of all MHTs' root labels. You can return the answer in any order.\n",
    "\n",
    "The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 4\n",
    "edges = [[1,0],[1,2],[1,3]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 6\n",
    "edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMinHeightTrees(n: int, edges: List[List[int]]) -> List[int]:\n",
    "    \"\"\"\n",
    "    no cycle guaranteed, no need to check any more\n",
    "    eventually end up with 2 roots or 1 root\n",
    "    topological sort\n",
    "    return all the root labels as a List\n",
    "    \"\"\"\n",
    "    \n",
    "    #base case:\n",
    "    if n <=2:\n",
    "        return [i for i in range(n)]\n",
    "    neighbors = [set() for i in range(n)]\n",
    "    print(neighbors)\n",
    "    for edge in edges:\n",
    "        neighbors[edge[0]].add(edge[1])\n",
    "        neighbors[edge[1]].add(edge[0])\n",
    "    print(neighbors)\n",
    "    leaves = deque()\n",
    "    for i in range(n):\n",
    "        if len(neighbors[i]) == 1:\n",
    "            leaves.append(i)\n",
    "    print(leaves)\n",
    "    #start triming the leaves\n",
    "    remain_nodes = n\n",
    "    while remain_nodes > 2:\n",
    "        remain_nodes -= len(leaves)\n",
    "        print(remain_nodes)\n",
    "        new_leaves = []\n",
    "        while leaves:\n",
    "            print('leaves:',leaves)\n",
    "            leaf = leaves.popleft()\n",
    "            neighbor = neighbors[leaf].pop()\n",
    "            neighbors[neighbor].remove(leaf)\n",
    "            print('neighbors: ', neighbors)\n",
    "            if len(neighbors[neighbor])==1:\n",
    "                new_leaves.append(neighbor)\n",
    "        leaves = new_leaves\n",
    "    return leaves\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findMinHeightTrees(n, edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMinHeightTrees2(n: int, edges: List[List[int]]) -> List[int]:\n",
    "    \"\"\"\n",
    "    :type n: int\n",
    "    :type edges: List[List[int]]\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    if n == 1: return [0]\n",
    "    neighbors = collections.defaultdict(list)\n",
    "    degrees = collections.defaultdict(int)\n",
    "    for u, v in edges:\n",
    "        neighbors[u].append(v)\n",
    "        neighbors[v].append(u)\n",
    "        degrees[u] += 1\n",
    "        degrees[v] += 1\n",
    "    print('neighbors ', neighbors)\n",
    "    print('degrees: ', degrees)\n",
    "    # First find the leaves\n",
    "    preLevel, unvisited = [], set(range(n))\n",
    "    for i in range(n):\n",
    "        if degrees[i] == 1: preLevel.append(i)\n",
    "    print(preLevel, unvisited)\n",
    "    \n",
    "    while len(unvisited) > 2:\n",
    "        thisLevel = []\n",
    "        for leaf in preLevel:\n",
    "            unvisited.remove(leaf)\n",
    "            for v in neighbors[leaf]:\n",
    "                if v in unvisited: \n",
    "                    degrees[v] -= 1\n",
    "                    if degrees[v] == 1:\n",
    "                        thisLevel += [v]\n",
    "        print('this level:', thisLevel)\n",
    "        preLevel = thisLevel\n",
    "                \n",
    "    return preLevel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findMinHeightTrees2(n, edges)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "#backtrack dfs harder to understand and slower\n",
    "https://cs.stackexchange.com/questions/22855/algorithm-to-find-diameter-of-a-tree-using-bfs-dfs-why-does-it-work\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Start from any node and run dfs, which calculate distances for all other nodes from this node as well as create parent for each node. What our fucntion will return in the end is the index of farthest node (there can be more than one and it is OK for us).\n",
    "2. Now, we need to start our dfs all over again from this node (that is why we use dfs_helper function - we need to clean our distances and parents arrays. When we run our dfs second time, we again find the farthest node.\n",
    "3. Finally, we create path between the first node we found and the second and it will be our diameter: if it has even number of nodes, we return 2 middle nodes, in other case we return 1 middle node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMinHeightTrees(self, n, edges):\n",
    "    def dfs_helper(start, n):\n",
    "        self.dist, self.parent = [-1]*n, [-1]*n\n",
    "        self.dist[start] = 0\n",
    "        dfs(start)\n",
    "        return self.dist.index(max(self.dist))\n",
    "\n",
    "    def dfs(start):\n",
    "        for neib in Graph[start]:\n",
    "            if self.dist[neib] == -1:\n",
    "                self.dist[neib] = self.dist[start] + 1\n",
    "                self.parent[neib] = start\n",
    "                dfs(neib)\n",
    "\n",
    "    Graph = defaultdict(set)\n",
    "    for a,b in edges:\n",
    "        Graph[a].add(b)\n",
    "        Graph[b].add(a)\n",
    "\n",
    "    ind = dfs_helper(0,n)\n",
    "    ind2 = dfs_helper(ind, n)\n",
    "\n",
    "    path = []\n",
    "    while ind2 != -1:\n",
    "        path.append(ind2)           #backtracking to create path\n",
    "        ind2 = self.parent[ind2]\n",
    "\n",
    "    Q = len(path)\n",
    "    return list(set([path[Q//2], path[(Q-1)//2]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 886. Possible Bipartition\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "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.\n",
    "\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]\n",
    "Output: true\n",
    "Explanation: group1 [1,4] and group2 [2,3].\n",
    "Example 2:\n",
    "\n",
    "Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]\n",
    "Output: false\n",
    "Example 3:\n",
    "\n",
    "Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]\n",
    "Output: false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 5\n",
    "dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def possibleBipartition(n: int, dislikes: List[List[int]]) -> bool:\n",
    "    # Constant defined for color drawing to person\n",
    "    NOT_COLORED, BLUE, GREEN = 0, 1, -1\n",
    "\n",
    "    # -------------------------------------\n",
    "    def dfs(person_id, color ):\n",
    "        # Draw person_id as color\n",
    "        color_table[person_id] = color\n",
    "\n",
    "        # Draw the_other, with opposite color, in dislike table of current person_id\n",
    "        for the_other in dislike_table[ person_id ]:\n",
    "\n",
    "            if color_table[the_other] == color:\n",
    "                # the_other has the same color of current person_id\n",
    "                # Reject due to breaking the relationship of dislike\n",
    "                return False\n",
    "\n",
    "            if color_table[the_other] == NOT_COLORED and (not dfs( the_other, -color)):\n",
    "                # Other people can not be colored with two different colors. \n",
    "                # Therefore, it is impossible to keep dis-like relationship with bipartition.\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    # ------------------------------------------------\n",
    "\n",
    "    if n == 1 or not dislikes:\n",
    "        # Quick response for simple cases\n",
    "        return True\n",
    "\n",
    "    # each person maintain a list of dislike\n",
    "    dislike_table = collections.defaultdict( list )\n",
    "    # cell_#0 is dummy just for the convenience of indexing from 1 to N\n",
    "    color_table = [ NOT_COLORED for _ in range(n+1) ]\n",
    "    for p1, p2 in dislikes:\n",
    "        # P1 and P2 dislike each other\n",
    "        dislike_table[p1].append( p2 )\n",
    "        dislike_table[p2].append( p1 )\n",
    "    print('dislike table:', dislike_table)\n",
    "    print('color_table:', color_table)\n",
    "\n",
    "    # Try to draw dislike pair with different colors in DFS\n",
    "    for person_id in range(1, n+1):\n",
    "\n",
    "        if color_table[person_id] == NOT_COLORED and (not dfs( person_id, BLUE)):\n",
    "            # Other people can not be colored with two different colors. \n",
    "            # Therefore, it is impossible to keep dis-like relationship with bipartition.\n",
    "            return False \n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "possibleBipartition(n, dislikes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 200. Number of Island"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"1\",\"1\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numIslands(grid: List[List[str]]) -> int:\n",
    "    def dfs(i,j, grid):\n",
    "        print(f'point: {i},{j}')\n",
    "        if i < 0 or j < 0 or i>= len(grid) or j>= len(grid[0]) or grid[i][j]!='1':\n",
    "            return\n",
    "        grid[i][j] = '2'\n",
    "        dfs(i,j+1, grid)\n",
    "        dfs(i,j-1, grid)\n",
    "        dfs(i+1,j, grid)\n",
    "        dfs(i-1,j, grid)\n",
    "    island = 0\n",
    "    if not grid:\n",
    "        return island\n",
    "\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            if grid[i][j] == '1':\n",
    "                dfs(i, j, grid)\n",
    "                island+=1\n",
    "                print(island,grid)\n",
    "    return island"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 695. Max Area of Island\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "The area of an island is the number of cells with a value 1 in the island.\n",
    "\n",
    "Return the maximum area of an island in grid. If there is no island, return 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [[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]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxAreaOfIsland(grid: List[List[int]]) -> int:\n",
    "    def dfs(i,j, grid, area):\n",
    "        # print(f'point: {i},{j}')\n",
    "        if i < 0 or j < 0 or i>= len(grid) or j>= len(grid[0]) or grid[i][j]!=1:\n",
    "            return\n",
    "        grid[i][j] = 2\n",
    "        area.append(1)\n",
    "#         print(area)\n",
    "        dfs(i,j+1, grid, area)\n",
    "        dfs(i,j-1, grid, area)\n",
    "        dfs(i+1,j, grid, area)\n",
    "        dfs(i-1,j, grid, area)\n",
    "    islands = []\n",
    "    if not grid:\n",
    "        return islands\n",
    "\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            if grid[i][j] == 1:\n",
    "                area = []\n",
    "                dfs(i, j, grid, area)\n",
    "                islands.append(len(area))\n",
    "    return max(islands)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "maxAreaOfIsland(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 463. Island Perimeter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def islandPerimeter(grid):\n",
    "    \"\"\"\n",
    "    :type grid: List[List[int]]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    if not grid:\n",
    "        return 0\n",
    "\n",
    "    def sum_adjacent(i, j):\n",
    "        adjacent = (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1),\n",
    "        res = 0\n",
    "        for x, y in adjacent:\n",
    "            if x < 0 or y < 0 or x == len(grid) or y == len(grid[0]) or grid[x][y] == 0:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "    count = 0\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            if grid[i][j] == 1:\n",
    "                count += sum_adjacent(i, j)\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def islandPerimeter(grid):\n",
    "    m, n, Perimeter = len(grid), len(grid[0]), 0\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            Perimeter += 4*grid[i][j]\n",
    "            if i > 0:   Perimeter -= grid[i][j]*grid[i-1][j]\n",
    "            if i < m-1: Perimeter -= grid[i][j]*grid[i+1][j]\n",
    "            if j > 0:   Perimeter -= grid[i][j]*grid[i][j-1]\n",
    "            if j < n-1: Perimeter -= grid[i][j]*grid[i][j+1]\n",
    "\n",
    "    return Perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "islandPerimeter(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 261. Graph Valid Tree - Medium\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "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.\n",
    "\n",
    "For example:\n",
    "\n",
    "Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.\n",
    "\n",
    "Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.\n",
    "\n",
    "Show Hint 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 5\n",
    "edges = [[0,1], [0,2], [0,3], [1,4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 5\n",
    "edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validTree(n: int, edges: List[List[int]]) -> bool:\n",
    "    graph = [[] for _ in range(n)]\n",
    "    visited = [0 for _ in range(n)]\n",
    "    for a, b in edges:\n",
    "        graph[a].append(b)\n",
    "        graph[b].append(a)\n",
    "    print(graph, visited)\n",
    "    #dfs logic: one node has 3 states:0 not visited, 1 visited, -1 being visited             # state -1  : vertex is being processed. Either all of its descendants\n",
    "            #             are not processed or it's still in the function call stack.\n",
    "    def dfs(i):\n",
    "        print(visited[i])\n",
    "        if visited[i] == -1:    # This vertex is being processed and it means we have a cycle.\n",
    "            return False\n",
    "        if visited[i] == 1:\n",
    "            return True\n",
    "        visited[i] = -1\n",
    "        for neigh in graph[i]:\n",
    "            if not dfs(neigh):\n",
    "                return False\n",
    "        visited[i] = 1\n",
    "        return True\n",
    "    \n",
    "    for i in range(n):\n",
    "        if not dfs(i):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "A tree is a special undirected graph. It satisfy two properties\n",
    "It is connected\n",
    "It has no cycle.\n",
    "Being connected means you can start from any node and reach any other node. To prove it, we can do a DFS and add each node we visit to a set. After we visited all the nodes, we compare the number of nodes in the set with the total number of nodes. If they are the same then every node is accessible from any other node and the graph is connected.\n",
    "To prove an undirected graph having no cycle, we can also do a DFS. If a graph contains a cycle, then we would visit a certain node more than once. There is a minor caveat, since the graph is undirected, when we visit a child we would always add parent to the next visit list. This creates a trivial cycle and not the real cycle we want. We can avoid detecting trivial cycle but adding an additional parent state in the DFS call."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "validTree(n, edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### if nei is visited but not a parent, then cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validTree2(n: int, edges: List[List[int]]) -> bool:\n",
    "    from collections import defaultdict\n",
    "    graph = defaultdict(list)\n",
    "\n",
    "    # build the graph\n",
    "    for src, dest in edges:\n",
    "        graph[src].append(dest)\n",
    "        graph[dest].append(src)\n",
    "    print(graph)\n",
    "    visited = set()\n",
    "    def dfs(root, parent): # returns true if graph has no cycle\n",
    "        print(visited)\n",
    "        visited.add(root)\n",
    "        for node in graph[root]:\n",
    "            if node == parent: # trivial cycle, skip\n",
    "                continue\n",
    "            if node in visited:\n",
    "                return False\n",
    "\n",
    "            if not dfs(node, root):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    return dfs(0, -1) and len(visited) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "validTree2(n, edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Condition 2 no cycle can also be expressed as # of nodes == # of edges + 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validTree3(n: int, edges: List[List[int]]) -> bool:\n",
    "    from collections import defaultdict\n",
    "    graph = defaultdict(list)\n",
    "\n",
    "    # build the graph\n",
    "    for src, dest in edges:\n",
    "        graph[src].append(dest)\n",
    "        graph[dest].append(src)\n",
    "    print(graph)\n",
    "    visited = set()\n",
    "    def dfs(root):\n",
    "        visited.add(root)\n",
    "        for node in graph[root]:\n",
    "            if node in visited:\n",
    "                continue\n",
    "            dfs(node)\n",
    "\n",
    "    dfs(0)\n",
    "    return len(visited) == n and len(edges) == n - 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### union find"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validTree4(self, n: int, edges: List[List[int]]) -> bool:\n",
    "    # Condition 1: The graph must contain n - 1 edges.\n",
    "    if len(edges) != n - 1: return False\n",
    "    roots = list(range(n))\n",
    "    # Condition 2: The graph must contain a single connected component.\n",
    "    # Create a new UnionFind object with n nodes. \n",
    "    def find(a):\n",
    "        if roots[a] != a:\n",
    "            roots[a] = find(roots[a])\n",
    "        return roots[a]\n",
    "\n",
    "    def union(x, y):\n",
    "        par_x = find(x)\n",
    "        par_y = find(y)\n",
    "        if par_x == par_y:\n",
    "            return False\n",
    "        roots[par_x] = par_y\n",
    "        return True\n",
    "    # Add each edge. Check if a merge happened, because if it \n",
    "    # didn't, there must be a cycle.\n",
    "    for A, B in edges:\n",
    "        if not union(A, B):\n",
    "            return False\n",
    "    # If we got this far, there's no cycles!\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "validTree3(n, edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A 2d grid map ofmrows andncolumns is initially filled with water. We may perform anaddLandoperation 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#269"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 305. Number of Islands II "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).\n",
    "0 0 0 \n",
    "0 0 0\n",
    "0 0 0\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.\n",
    "1 0 0\n",
    "0 0 0   Number of islands = 1\n",
    "0 0 0\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.\n",
    "\n",
    "1 1 0\n",
    "0 0 0   Number of islands = 1\n",
    "0 0 0\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.\n",
    "\n",
    "1 1 0\n",
    "0 0 1   Number of islands = 2\n",
    "0 0 0"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.\n",
    "\n",
    "1 1 0\n",
    "0 0 1   Number of islands = 3\n",
    "0 1 0\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "We return the result as an array: [1, 1, 2, 3]\n",
    "\n",
    "Need to use unionfind algorithm. (Disjoint Set) <Friend circles, Graph Valid Tree, Redundant Connection II>\n",
    "https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/\n",
    "https://medium.com/@timothyhuang514/graph-number-of-islands-ii-21fe906e2b57"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "import collections, itertools, sys\n",
    "\n",
    "coordinate = collections.namedtuple('coordinate', ('r', 'c'))\n",
    "\n",
    "class Subset:\n",
    "    def __init__(self, node, rank):\n",
    "        self.parent = node\n",
    "        self.rank = rank\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.V = 1\n",
    "        self.islands = collections.defaultdict(set)\n",
    "\n",
    "class NumberOfIslandsII:\n",
    "\n",
    "    def _findParent(self, subsets, node):\n",
    "        if subsets[node].parent != node:\n",
    "            subsets[node].parent = self._findParent(subsets, subsets[node].parent)\n",
    "        return subsets[node].parent\n",
    "\n",
    "    def _union(self, head, p, subsets):\n",
    "        subsets[p].parent = head\n",
    "        if subsets[head].rank <= subsets[p].rank:\n",
    "            subsets[head].rank, subsets[p].rank = subsets[p].rank + 1, subsets[head].rank\n",
    "        return subsets\n",
    "\n",
    "    def numIslands22(self, m, n, positions):\n",
    "        if len(positions) <= 1:\n",
    "            return [len(positions)]\n",
    "\n",
    "        # Initialization\n",
    "        island_subsets = collections.defaultdict(Subset)\n",
    "        island_count = []\n",
    "        curr_island = 0\n",
    "        # Iterate thru the positions array\n",
    "        for pos in positions:\n",
    "            curr = coordinate(pos[0], pos[1])\n",
    "            # New node\n",
    "            if curr not in island_subsets.keys():\n",
    "                neighbors = set()\n",
    "                for neigh in [coordinate(curr.r, curr.c - 1), coordinate(curr.r, curr.c + 1),\n",
    "                              coordinate(curr.r - 1, curr.c), coordinate(curr.r + 1, curr.c)]:\n",
    "                    if neigh in island_subsets.keys():\n",
    "                        # Find the node's parent and add it to neighbors set\n",
    "                        neighbors.add(self._findParent(island_subsets, neigh))\n",
    "\n",
    "                # No neighbors -> new island\n",
    "                if len(neighbors) == 0:\n",
    "                    curr_island += 1\n",
    "                    head = curr\n",
    "                else:\n",
    "                    curr_island -= (len(neighbors) - 1)\n",
    "                    # Set the largest tree as the parent\n",
    "                    head = max(neighbors)\n",
    "                    neighbors.remove(head)\n",
    "\n",
    "                    # Merge graph\n",
    "                    for p in neighbors:\n",
    "                        island_subsets = self._union(head, p, island_subsets)\n",
    "\n",
    "                # Add current node to the head and island subset\n",
    "                island_subsets[curr] = Subset(head, 0)\n",
    "                island_subsets = self._union(head, curr, island_subsets)\n",
    "\n",
    "            # Update island count\n",
    "            island_count.append(curr_island)\n",
    "\n",
    "        return island_count\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1971. Find if Path Exists in Graph\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.\n",
    "\n",
    "You want to determine if there is a valid path that exists from vertex start to vertex end.\n",
    "\n",
    "Given edges and the integers n, start, and end, return true if there is a valid path from start to end, or false otherwise.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Input: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 6\n",
    "edges = [[0,1],[0,2],[3,5],[5,4],[4,3]]\n",
    "start = 0\n",
    "end = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validPath(n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        if not edges:\n",
    "            return True\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        def dfs(graph, curr, end, seen, switch):\n",
    "            if curr in seen:\n",
    "                return\n",
    "            seen.add(curr)\n",
    "            for child in graph[curr]:\n",
    "                if child == end:\n",
    "                    switch[0] = True\n",
    "                dfs(graph, child, end, seen, switch)\n",
    "            return switch[0]\n",
    "    \n",
    "        \n",
    "        return dfs(graph, start, end, set(), [False])\n",
    "#         print(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validPath(n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        graph = {}\n",
    "        for u, v in edges: \n",
    "            graph.setdefault(u, []).append(v)\n",
    "            graph.setdefault(v, []).append(u)\n",
    "        \n",
    "        seen = {start}\n",
    "        stack = [start]\n",
    "        while stack: \n",
    "            n = stack.pop()\n",
    "            if n == end: return True \n",
    "            for nn in graph.get(n, []): \n",
    "                if nn not in seen: \n",
    "                    seen.add(nn)\n",
    "                    stack.append(nn)\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "def validPath(n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        queue = deque()\n",
    "            \n",
    "        queue.append(start)\n",
    "        visited=set()\n",
    "        while queue:\n",
    "            currentNode=queue.popleft()\n",
    "            if currentNode==end:\n",
    "                return True\n",
    "            visited.add(currentNode)\n",
    "            for neighbor in graph[currentNode]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UnionFind: \n",
    "    \n",
    "    def __init__(self, n): \n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "        \n",
    "    def find(self, p): \n",
    "        if p != self.parent[p]: \n",
    "            self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "    \n",
    "    def union(self, p, q): \n",
    "        prt, qrt = self.find(p), self.find(q)\n",
    "        if prt == qrt: return False \n",
    "        if self.rank[prt] > self.rank[qrt]: prt, qrt = qrt, prt\n",
    "        self.parent[prt] = qrt\n",
    "        self.rank[qrt] += self.rank[prt]\n",
    "        return True \n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:\n",
    "        uf = UnionFind(n)\n",
    "        for u, v in edges: \n",
    "            uf.union(u, v)\n",
    "        return uf.find(start) == uf.find(end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "validPath(n, edges, start, end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# find simple paths between 2 vertexes. (Count all possible paths between two vertices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Create a recursive function that takes index of node of a graph and the destination index. Keep a global or a static variable count to store the count. Keep a record of the nodes visited in the current path by passing a visited array by value (instead of reference, which would not be limited to the current path).\n",
    "2. If the current nodes is the destination increase the count.\n",
    "3. Else for all the adjacent nodes, i.e. nodes that are accessible from the current node, call the recursive function with the index of adjacent node and the destination.\n",
    "4. Print the Count."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    " \n",
    "    def __init__(self, V):\n",
    "        self.V = V\n",
    "        self.adj = [[] for i in range(V)]\n",
    "     \n",
    "    def addEdge(self, u, v):\n",
    "         \n",
    "        # Add v to u’s list.\n",
    "        self.adj[u].append(v)\n",
    "     \n",
    "    # Returns count of paths from 's' to 'd'\n",
    "    def countPaths(self, s, d):\n",
    "         \n",
    "        # Mark all the vertices\n",
    "        # as not visited\n",
    "        visited = [False] * self.V\n",
    "     \n",
    "        # Call the recursive helper\n",
    "        # function to print all paths\n",
    "        pathCount = [0]\n",
    "        self.countPathsUtil(s, d, visited, pathCount)\n",
    "        return pathCount[0]\n",
    "     \n",
    "    # A recursive function to print all paths\n",
    "    # from 'u' to 'd'. visited[] keeps track \n",
    "    # of vertices in current path. path[]\n",
    "    # stores actual vertices and path_index\n",
    "    # is current index in path[]\n",
    "    def countPathsUtil(self, u, d,visited, pathCount):\n",
    "        visited[u] = True\n",
    "     \n",
    "        # If current vertex is same as\n",
    "        # destination, then increment count\n",
    "        if (u == d):\n",
    "            pathCount[0] += 1\n",
    "     \n",
    "        # If current vertex is not destination\n",
    "        else:\n",
    "             \n",
    "            # Recur for all the vertices\n",
    "            # adjacent to current vertex\n",
    "            i = 0\n",
    "            while i < len(self.adj[u]):\n",
    "                if (not visited[self.adj[u][i]]):\n",
    "                    self.countPathsUtil(self.adj[u][i], d,visited, pathCount)\n",
    "                i += 1\n",
    "     \n",
    "        visited[u] = False\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Driver Code\n",
    "if __name__ == '__main__':\n",
    " \n",
    "    # Create a graph given in the\n",
    "    # above diagram\n",
    "    g = Graph(4)\n",
    "    g.addEdge(0, 1)\n",
    "    g.addEdge(0, 2)\n",
    "    g.addEdge(0, 3)\n",
    "    g.addEdge(2, 0)\n",
    "    g.addEdge(2, 1)\n",
    "    g.addEdge(1, 3)\n",
    " \n",
    "    s = 2\n",
    "    d = 3\n",
    "    print(g.countPaths(s, d))\n",
    " \n",
    "# This code is contributed by PranchalK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Count all possible walks from a source to a destination with exactly k edges\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## important trick: to remember it as matrix multiplication, and diagonal matrix to speed up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Python3 program to count walks from\n",
    "# u to v with exactly k edges\n",
    " \n",
    "# Number of vertices in the graph\n",
    "V = 4\n",
    " \n",
    "# A naive recursive function to count\n",
    "# walks from u to v with k edges\n",
    "def countwalks(graph, u, v, k):\n",
    " \n",
    "    # Base cases\n",
    "    if (k == 0 and u == v):\n",
    "        return 1\n",
    "    if (k == 1 and graph[u][v]):\n",
    "        return 1\n",
    "    if (k <= 0):\n",
    "        return 0\n",
    "     \n",
    "    # Initialize result\n",
    "    count = 0\n",
    "     \n",
    "    # Go to all adjacents of u and recur\n",
    "    for i in range(0, V):\n",
    "         \n",
    "        # Check if is adjacent of u\n",
    "        if (graph[u][i] == 1):\n",
    "            count += countwalks(graph, i, v, k-1)\n",
    "     \n",
    "    return count\n",
    " \n",
    "# Driver Code\n",
    " \n",
    "# Let us create the graph shown in above diagram\n",
    "graph = [[0, 1, 1, 1, ],\n",
    "         [0, 0, 0, 1, ],\n",
    "         [0, 0, 0, 1, ],\n",
    "         [0, 0, 0, 0] ]\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def countwalks2(graph, u, v, k):\n",
    " \n",
    "    # Table to be filled up using DP.\n",
    "    # The value count[i][j][e] will/\n",
    "    # store count of possible walks\n",
    "    # from i to j with exactly k edges\n",
    "    count = [[[0 for k in range(k + 1)]\n",
    "              for i in range(V)]\n",
    "             for j in range(V)]\n",
    " \n",
    "    # Loop for number of edges from 0 to k\n",
    "    for e in range(0, k + 1):\n",
    "        # For Source\n",
    "        for i in range(V):\n",
    "            # For Desitination\n",
    "            for j in range(V):\n",
    "                # Initialize value\n",
    "                # count[i][j][e] = 0\n",
    " \n",
    "                # From base cases\n",
    "                if (e == 0 and i == j):\n",
    "                    count[i][j][e] = 1\n",
    "                if (e == 1 and graph[i][j] != 0):\n",
    "                    count[i][j][e] = 1\n",
    " \n",
    "                # Go to adjacent only when number\n",
    "                # of edges is more than 1\n",
    "                if (e > 1):\n",
    " \n",
    "                    for a in range(V):\n",
    " \n",
    "                        # Adjacent of i\n",
    "                        if (graph[i][a] != 0):\n",
    "                            count[i][j][e] += count[a][j][e - 1]\n",
    " \n",
    "    return count[u][v][k]\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "u = 0\n",
    "v = 3\n",
    "k = 2\n",
    "print(countwalks(graph, u, v, k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1791. Find Center of Star Graph\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.\n",
    "\n",
    "You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = [[1,2],[2,3],[4,2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findCenter(edges: List[List[int]]) -> int:\n",
    "    n = len(edges)+1\n",
    "    graph = {}\n",
    "    for u, v in edges: \n",
    "        graph.setdefault(u, []).append(v)\n",
    "        graph.setdefault(v, []).append(u)\n",
    "        \n",
    "# get key with max value\n",
    "    maxlen = 0\n",
    "    for ele in graph:\n",
    "        maxlen = max(len(graph[ele]), maxlen)\n",
    "    return [ele for ele in graph if len(graph[ele]) ==  maxlen][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findCenter(e):\n",
    "    return e[0][e[0][1] in e[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findCenter(e):\n",
    "    if e[0][0]==e[1][0] or e[0][0]==e[1][1]:\n",
    "        return e[0][0]\n",
    "    return e[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findCenter(edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 139. Word Break"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.\n",
    "\n",
    "Note that the same word in the dictionary may be reused multiple times in the segmentation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Input: s = \"leetcode\", wordDict = [\"leet\",\"code\"]\n",
    "Output: true\n",
    "Explanation: Return true because \"leetcode\" can be segmented as \"leet code\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"leetcode\"\n",
    "wordDict = [\"leet\", \"code\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# BFS Solution\n",
    "def wordBreak(s: str, wordDict: List[str]) -> bool:\n",
    "    q = deque([s])\n",
    "    seen = set() \n",
    "    while q:\n",
    "        print(q)\n",
    "        s = q.popleft()    # popleft() = BFS ; pop() = DFS\n",
    "        for word in wordDict:\n",
    "            if s.startswith(word):\n",
    "                new_s = s[len(word):]\n",
    "                if new_s == \"\": \n",
    "                    return True\n",
    "                if new_s not in seen:\n",
    "                    q.append(new_s)\n",
    "                    seen.add(new_s)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wordBreak(s, wordDict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#DP solution\n",
    "def wordBreak(self, s, wordDict):\n",
    "    \"\"\"\n",
    "    :type s: str\n",
    "    :type wordDict: Set[str]\n",
    "    :rtype: bool\n",
    "    \"\"\"\n",
    "    dp = [False] * (len(s) + 1) # dp[i] means s[:i+1] can be segmented into words in the wordDicts \n",
    "    dp[0] = True\n",
    "    for i in range(len(s)):\n",
    "        for j in range(i, len(s)):\n",
    "            if dp[i] and s[i: j+1] in wordDict:\n",
    "                dp[j+1] = True\n",
    "\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 140. Word Break II\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"catsanddog\"\n",
    "wordDict = [\"cat\",\"cats\",\"and\",\"sand\",\"dog\"]\n",
    "# [\"cats and dog\",\"cat sand dog\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def wordBreak(s: str, wordDict: List[str]) -> List[str]:\n",
    "    \"\"\"\n",
    "    :type s: str\n",
    "    :type wordDict: Set[str]\n",
    "    :rtype: List[str]\n",
    "    \"\"\"\n",
    "    return helper(s, wordDict, {})\n",
    "    \n",
    "def helper(s, wordDict, memo):\n",
    "    if s in memo: return memo[s]\n",
    "    if not s: return []\n",
    "    \n",
    "    res = []\n",
    "    for word in wordDict:\n",
    "        if not s.startswith(word):\n",
    "            continue\n",
    "        if len(word) == len(s):\n",
    "            res.append(word)\n",
    "        else:\n",
    "            resultOfTheRest = helper(s[len(word):], wordDict, memo)\n",
    "            for item in resultOfTheRest:\n",
    "                item = word + ' ' + item\n",
    "                res.append(item)\n",
    "    memo[s] = res\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wordBreak(s, wordDict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First of all, this problem is extention of problem 139. Word Break, where we need just to check if word can be broken into other words. Here we need to give all possible splits. Let us first put all words into set and create two lists:\n",
    "\n",
    "1. dp_solution[i] is all possible splits for first i symbols of s\n",
    "2. dp[i] is indicator if we can split word or not.\n",
    "\n",
    "Also we create this two lists with size (n+1) to handle border cases, in dp[-1] we will keep result for empty string \"\".\n",
    "\n",
    "1. First step is to check if our string can be splitted at all, using problem 139. We need to do it, to candle strings like aaaaa...aaab, with wordDict = [a, aa, aaa, ..., aa..aa]. In this case answer will be no, but if we try to build solution directly we will get MLE. Try to remove this lines of code from solution and you will see.\n",
    "2. Now, we do one more pass over data and start to build solutions: if we found that s[j: k + 1] in wordSet, then for every already built solution sol in dp_solution[j-1] we can add it to dp_solution[k].\n",
    "3. Finally, we have some extraspaces in the beginning of each solution, and instead of last element [-1] we need to return previous [-2], so we return return [s[1:] for s in dp_solution[-2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def wordBreak(self, s, wordDict):\n",
    "        wordSet = set(wordDict)\n",
    "        n = len(s)\n",
    "        dp_solution = [[] for _ in range(n)] + [[\"\"]]\n",
    "        dp = [0] * n + [1]\n",
    "        \n",
    "        for k in range(n):\n",
    "            for j in range(k,-1,-1):\n",
    "                if s[j: k + 1] in wordSet:\n",
    "                    dp[k] = max(dp[k], dp[j-1])\n",
    "\n",
    "        if dp[-2] == 0: return []\n",
    "\n",
    "        for k in range(n):\n",
    "            for j in range(k,-1,-1):\n",
    "                if s[j: k + 1] in wordSet:\n",
    "                    for sol in dp_solution[j-1]:\n",
    "                        dp_solution[k].append(sol + \" \" + s[j: k + 1])\n",
    "                        \n",
    "        return [s[1:] for s in dp_solution[-2]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 909. Snakes and Ladders\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.\n",
    "\n",
    "You start on square 1 of the board. In each move, starting from square curr, do the following:\n",
    "\n",
    "Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].\n",
    "This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.\n",
    "If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.\n",
    "The game ends when you reach the square n2.\n",
    "A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.\n",
    "\n",
    "Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.\n",
    "\n",
    "For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.\n",
    "Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]\n",
    "# return 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "board = [[-1,-1,-1],[-1,9,8],[-1,8,9]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "board =[[-1,1,2,-1],[2,13,15,-1],[-1,10,-1,-1],[-1,6,2,8]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thought process\n",
    "* simply apply BFS to find the length of shortest path from 1 to n*n\n",
    "* key point is to correctly compute the corresponding coordinates of the label\n",
    "* also remember to avoid circle by using a hashset to track visited positions\n",
    "\n",
    "time complexity: O(n^2), n is the width and height of the grid\n",
    "space complexity: O(n^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "from collections import deque\n",
    "def snakesAndLadders(board: List[List[int]]) -> int:\n",
    "    n = len(board)\n",
    "    def label_to_position(label):\n",
    "        '''\n",
    "        helper function to turn label position to 2d labels'''\n",
    "        r, c = divmod(label-1, n)\n",
    "        if r % 2 == 0:\n",
    "            return n-1-r, c\n",
    "        else:\n",
    "            return n-1-r, n-1-c\n",
    "\n",
    "    seen = set()\n",
    "    queue = deque()\n",
    "    queue.append((1, 0)) #label, step\n",
    "    while queue:\n",
    "        label, step = queue.popleft()\n",
    "        r, c = label_to_position(label)\n",
    "        if board[r][c] != -1:\n",
    "            label = board[r][c]\n",
    "        if label == n*n:\n",
    "            return step\n",
    "        for x in range(1, 7):\n",
    "            new_label = label + x\n",
    "            if new_label <= n*n and new_label not in seen:\n",
    "                seen.add(new_label)\n",
    "                queue.append((new_label, step+1))\n",
    "                print(f'x:{x},seen:{seen}, queue:{queue}')\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "    n = len(board)\n",
    "    coord = {}\n",
    "    for i in range(n*n):\n",
    "        if i // n % 2 == 0:\n",
    "            y = n-(i//n)-1\n",
    "            x = i %n\n",
    "            coord[i+1] = board[y][x]\n",
    "        else:\n",
    "            coord[i+1] = board[-(i//n) - 1][n- i%n - 1]\n",
    "    dist = [-1] * (n * n + 1)\n",
    "    q = collections.deque([1])\n",
    "    dist[1] = 0\n",
    "    while q:\n",
    "        curr = q.popleft()\n",
    "        for next in range(curr + 1, min(curr + 6, n**2) + 1):\n",
    "            destination = coord[next] if coord[next] != -1 else next\n",
    "            if dist[destination] == -1:\n",
    "                dist[destination] = dist[curr] + 1\n",
    "                q.append(destination)\n",
    "    return dist[n * n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def snakesAndLadders(board):\n",
    "    n = len(board)\n",
    "    need = {1: 0}\n",
    "    bfs = [1]\n",
    "    for x in bfs:\n",
    "        for i in range(x + 1, x + 7):\n",
    "            a, b = (i - 1) / n, (i - 1) % n\n",
    "            nxt = board[~a][b if a % 2 == 0 else ~b]\n",
    "            if nxt > 0: i = nxt\n",
    "            if i == n * n: return need[x] + 1\n",
    "            if i not in need:\n",
    "                need[i] = need[x] + 1\n",
    "                bfs.append(i)\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "snakesAndLadders(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 417. Pacific Atlantic Water Flow\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.\n",
    "\n",
    "The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).\n",
    "\n",
    "The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.\n",
    "\n",
    "Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]\n",
    "#[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:\n",
    "    def dfs(matrix, i, j, visited, m, n):\n",
    "        # when dfs called, meaning its caller already verified this point \n",
    "        visited[i][j] = True\n",
    "        for dirc in directions:\n",
    "            x, y = i + dirc[0], j + dirc[1]\n",
    "            if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] < matrix[i][j]:\n",
    "                continue\n",
    "            dfs(matrix, x, y, visited, m, n)\n",
    "\n",
    "    m = len(heights)\n",
    "    n = len(heights[0])\n",
    "    if not heights:\n",
    "        return []\n",
    "    \n",
    "    directions = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "    \n",
    "    \n",
    "    p_visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "    a_visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "    result = []\n",
    "\n",
    "    for i in range(m):\n",
    "        # p_visited[i][0] = True\n",
    "        # a_visited[i][n-1] = True\n",
    "        dfs(heights, i, 0, p_visited, m, n)\n",
    "        dfs(heights, i, n-1, a_visited, m, n)\n",
    "    for j in range(n):\n",
    "        # p_visited[0][j] = True\n",
    "        # a_visited[m-1][j] = True\n",
    "        dfs(heights, 0, j, p_visited, m, n)\n",
    "        dfs(heights, m-1, j, a_visited, m, n)\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if p_visited[i][j] and a_visited[i][j]:\n",
    "                result.append([i,j])\n",
    "    return result\n",
    "                  \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pacificAtlantic(heights)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pacificAtlantic(self, matrix):\n",
    "        if not matrix: return []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        def bfs(reachable_ocean):\n",
    "            q = collections.deque(reachable_ocean)\n",
    "            while q:\n",
    "                (i, j) = q.popleft()\n",
    "                for (di, dj) in [(0,1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                    if 0 <= di+i < m and 0 <= dj+j < n and (di+i, dj+j) not in reachable_ocean \\\n",
    "                        and matrix[di+i][dj+j] >= matrix[i][j]:\n",
    "                        q.append( (di+i,dj+j) )\n",
    "                        reachable_ocean.add( (di+i, dj+j) )\n",
    "            return reachable_ocean         \n",
    "        pacific  =set ( [ (i, 0) for i in range(m)]   + [(0, j) for j  in range(1, n)]) \n",
    "        atlantic =set ( [ (i, n-1) for i in range(m)] + [(m-1, j) for j in range(n-1)]) \n",
    "        return list( bfs(pacific) & bfs(atlantic) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs(matrix):\n",
    "    # 1. Check for an empty graph.\n",
    "    if not matrix:\n",
    "        return []\n",
    "\n",
    "    # 2. Initialize\n",
    "    rows, cols = len(matrix), len(matrix[0])\n",
    "    visited = set()\n",
    "    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "\n",
    "    def traverse(i, j):\n",
    "        # a. Check if visited\n",
    "        if (i, j) in visited:\n",
    "            return\n",
    "\t\t# b. Else add to visted\n",
    "        visited.add((i, j))\n",
    "\n",
    "        # c. Traverse neighbors.\n",
    "        for direction in directions:\n",
    "            next_i, next_j = i + direction[0], j + direction[1]\n",
    "            if 0 <= next_i < rows and 0 <= next_j < cols:\n",
    "                # d. Add in your question-specific checks.\n",
    "                traverse(next_i, next_j)\n",
    "\n",
    "    # 3. For each point, traverse it.\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            traverse(i, j)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        # Check for an empty graph.\n",
    "        if not matrix:\n",
    "            return []\n",
    "\n",
    "        p_visited = set()\n",
    "        a_visited = set()\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "\n",
    "        def traverse(i, j, visited):\n",
    "            if (i, j) in visited:\n",
    "                return\n",
    "            visited.add((i, j))\n",
    "            # Traverse neighbors.\n",
    "            for direction in directions:\n",
    "                next_i, next_j = i + direction[0], j + direction[1]\n",
    "                if 0 <= next_i < rows and 0 <= next_j < cols:\n",
    "                    # Add in your question-specific checks.\n",
    "                    if matrix[next_i][next_j] >= matrix[i][j]:\n",
    "                        traverse(next_i, next_j, visited)\n",
    "\n",
    "        for row in range(rows):\n",
    "            traverse(row, 0, p_visited)\n",
    "            traverse(row, cols - 1, a_visited)\n",
    "\n",
    "        for col in range(cols):\n",
    "            traverse(0, col, p_visited)\n",
    "            traverse(rows - 1, col, a_visited)\n",
    "\n",
    "        return list(p_visited & a_visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pacificAtlantic(self, M):\n",
    "    if not M or not M[0]: return []\n",
    "    m, n = len(M[0]), len(M)\n",
    "    \n",
    "    def bfs(starts):\n",
    "        queue = deque(starts)\n",
    "        visited = set(starts)\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            for dx, dy in [(x, y+1), (x, y-1), (x-1, y), (x+1, y)]:\n",
    "                if 0 <= dx < n and 0 <= dy < m and (dx, dy) not in visited and M[dx][dy] >= M[x][y]:\n",
    "                    queue.append((dx, dy))\n",
    "                    visited.add((dx, dy))\n",
    "\n",
    "        return visited\n",
    "\n",
    "    pacific  = [(0, i) for i in range(m)]   + [(i, 0) for i in range(1,n)]\n",
    "    atlantic = [(n-1, i) for i in range(m)] + [(i, m-1) for i in range(n-1)]\n",
    "\n",
    "    return bfs(pacific) & bfs(atlantic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        # Check edge case\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        # Initialize\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        directions = ((0, 1), (0, -1), (-1, 0), (1, 0))\n",
    "        visited = set()\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i, j, visited):\n",
    "            # Check if visited\n",
    "            if (i, j) in visited:\n",
    "                return 0\n",
    "\t\t\tvisited.add((i, j))\n",
    "            res = 1\n",
    "\n",
    "            # work with neighbors\n",
    "            for direction in directions:\n",
    "                next_i, next_j = i + direction[0], j + direction[1]\n",
    "\n",
    "                # for each direction we try to find a new count\n",
    "                direction_count = 0\n",
    "                if 0 <= next_i < rows and 0 <= next_j < cols:\n",
    "                    if matrix[i][j] < matrix[next_i][next_j]:\n",
    "                        direction_count = 1 + dfs(next_i, next_j, visited)\n",
    "\n",
    "                res = max(direction_count, res)\n",
    "\n",
    "            return res\n",
    "\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                res = max(dfs(row, col, visited), res)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#DFS with memoization\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        # Check edge case\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        # Initialize\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        directions = ((0, 1), (0, -1), (-1, 0), (1, 0))\n",
    "        memo = [[-1] * cols for _ in range(rows)]\n",
    "        res = 0\n",
    "\n",
    "        def dfs(i, j, visited):\n",
    "            # Check if visited\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "\n",
    "            res = 1\n",
    "\n",
    "            # work with neighbors\n",
    "            for direction in directions:\n",
    "                next_i, next_j = i + direction[0], j + direction[1]\n",
    "\n",
    "                # for each direction we try to find a new count\n",
    "                direction_count = 0\n",
    "                if 0 <= next_i < rows and 0 <= next_j < cols:\n",
    "                    if matrix[i][j] < matrix[next_i][next_j]:\n",
    "                        direction_count = 1 + dfs(next_i, next_j, visited)\n",
    "\n",
    "                res = max(direction_count, res)\n",
    "\n",
    "            memo[i][j] = res\n",
    "            return res\n",
    "\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                res = max(dfs(row, col, memo), res)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 36. Valid Sudoku\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:\n",
    "\n",
    "Each row must contain the digits 1-9 without repetition.\n",
    "Each column must contain the digits 1-9 without repetition.\n",
    "Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.\n",
    "https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValidSudoku(board: List[List[str]]) -> bool:\n",
    "    big = set()\n",
    "    for i in range(0,9):\n",
    "        for j in range(0,9):\n",
    "            if board[i][j]!='.':\n",
    "                cur = board[i][j]\n",
    "                if (i,cur) in big or (cur,j) in big or (i//3,j//3,cur) in big:\n",
    "                    return False\n",
    "                big.add((i,cur))\n",
    "                big.add((cur,j))\n",
    "                big.add((i//3,j//3,cur))#check in small 9 cells\n",
    "                print(i, j, big)\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValidSudoku2(board):\n",
    "    return (self.is_row_valid(board) and\n",
    "            self.is_col_valid(board) and\n",
    "            self.is_square_valid(board))\n",
    "\n",
    "def is_row_valid(self, board):\n",
    "    for row in board:\n",
    "        if not self.is_unit_valid(row):\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def is_col_valid(self, board):\n",
    "    for col in zip(*board):\n",
    "        if not self.is_unit_valid(col):\n",
    "            return False\n",
    "    return True\n",
    "    \n",
    "def is_square_valid(self, board):\n",
    "    for i in (0, 3, 6):\n",
    "        for j in (0, 3, 6):\n",
    "            square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]\n",
    "            if not self.is_unit_valid(square):\n",
    "                return False\n",
    "    return True\n",
    "    \n",
    "def is_unit_valid(self, unit):\n",
    "    unit = [i for i in unit if i != '.']\n",
    "    return len(set(unit)) == len(unit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "board = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "board = [[\"8\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "isValidSudoku(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1926. Nearest Exit from Entrance in Maze\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.\n",
    "maze = [[\"+\",\"+\",\".\",\"+\"],[\".\",\".\",\".\",\"+\"],[\"+\",\"+\",\"+\",\".\"]], entrance = [1,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "    rows, cols = len(maze), len(maze[0])\n",
    "    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "    # Mark the entrance as visited since its not a exit.\n",
    "    start_row, start_col = entrance\n",
    "    maze[start_row][start_col] = \"+\"\n",
    "\n",
    "    # Start BFS from the entrance, and use a queue `queue` to store all \n",
    "    # the cells to be visited.\n",
    "    queue = collections.deque()\n",
    "    queue.append([start_row, start_col, 0])\n",
    "\n",
    "    while queue:\n",
    "        curr_row, curr_col, curr_distance = queue.popleft()\n",
    "\n",
    "        # For the current cell, check its four neighbor cells.\n",
    "        for d in dirs:\n",
    "            next_row = curr_row + d[0]\n",
    "            next_col = curr_col + d[1]\n",
    "\n",
    "            # If there exists an unvisited empty neighbor:\n",
    "            if 0 <= next_row < rows and 0 <= next_col < cols \\\n",
    "                and maze[next_row][next_col] == \".\":\n",
    "\n",
    "                # If this empty cell is an exit, return distance + 1.\n",
    "                if 0 == next_row or next_row == rows - 1 or 0 == next_col or next_col == cols - 1:\n",
    "                    return curr_distance + 1\n",
    "\n",
    "                # Otherwise, add this cell to 'queue' and mark it as visited.\n",
    "                maze[next_row][next_col] = \"+\"\n",
    "                queue.append([next_row, next_col, curr_distance + 1])\n",
    "\n",
    "    # If we finish iterating without finding an exit, return -1.\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1293. Shortest Path in a Grid with Obstacles Elimination\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.\n",
    "\n",
    "Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Key is that we need another piece of information, which is the remaining quota that we can use to eliminate the obstacles.\n",
    "## Leetcode solution Very well-written"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SOLUTION1 BFS, keeping (step, coord, quota) as each state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
    "    m = len(grid)\n",
    "    n = len(grid[0])\n",
    "    target = (m-1, n-1)\n",
    "    # sufficient quota, then shortest distance is the Manhattan distance\n",
    "    if k >= m+n-2:\n",
    "        return m+n-2\n",
    "    state = (0,0, k)\n",
    "    queue = [(0, state)] # step, state\n",
    "    seen =set()\n",
    "    seen.add(state)\n",
    "\n",
    "    while (queue):\n",
    "        step, (row, col, k) = queue.pop(0)\n",
    "        if (row, col) == target:\n",
    "            return step\n",
    "        for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:\n",
    "            # if (new_row, new_col) is within the grid boundaries\n",
    "            if (0 <= new_row < m) and (0 <= new_col < n):\n",
    "                new_eliminations = k - grid[new_row][new_col]\n",
    "                new_state = (new_row, new_col, new_eliminations)\n",
    "                # add the next move in the queue if it qualifies\n",
    "                if new_eliminations >= 0 and new_state not in seen:\n",
    "                    seen.add(new_state)\n",
    "                    queue.append((step + 1, new_state))\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SOLUTION2, A STAR, intuition: the optimal directions to explore should be either right or down, rather than left or up.\n",
    "Therefore, one idea to improve our BFS approach is to prioritize exploring the most promising directions at each step. Through prioritization, we can speed up the algorithm by reducing the time spent exploring less promising paths. f(n)=g(n)+h(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The most important property of our heuristic h(n)h(n) function is that the function should be admissible, i.e. it never overestimates the cost. Otherwise, it could not guarantee that the path we find is the shortest one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def manhattan_dist(row, col):\n",
    "        return target[0]-row + target[1]-col\n",
    "    m = len(grid)\n",
    "    n = len(grid[0])\n",
    "    target = (m-1, n-1)\n",
    "    # sufficient quota, then shortest distance is the Manhattan distance\n",
    "    if k >= m+n-2:\n",
    "        return m+n-2\n",
    "    state = (0,0, k)\n",
    "    queue = [(manhattan_dist(0, 0), 0, state)] # step, state\n",
    "    seen =set()\n",
    "    seen.add(state)\n",
    "\n",
    "    while (queue):\n",
    "        heuristic, step, (row, col, remain_k) = heapq.heappop(queue)\n",
    "        remain_man_dist = heuristic - step\n",
    "        if remain_man_dist <= remain_k:\n",
    "            return heuristic\n",
    "        if (row, col) == target:\n",
    "            return step\n",
    "        for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:\n",
    "            # if (new_row, new_col) is within the grid boundaries\n",
    "            if (0 <= new_row < m) and (0 <= new_col < n):\n",
    "                new_eliminations = remain_k - grid[new_row][new_col]\n",
    "                new_state = (new_row, new_col, new_eliminations)\n",
    "                # add the next move in the queue if it qualifies\n",
    "                if new_eliminations >= 0 and new_state not in seen:\n",
    "                    seen.add(new_state)\n",
    "                    new_heuristic = manhattan_dist(new_row, new_col) + step + 1\n",
    "                    heapq.heappush(queue, (new_heuristic, step + 1, new_state))\n",
    "\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 847. Shortest Path Visiting All Nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.\n",
    "\n",
    "Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s Solution:\n",
    "    def shortestPathLength(self, graph):\n",
    "        # 1 <= graph.length <= 12\n",
    "        # 0 <= graph[i].length < graph.length\n",
    "\n",
    "        nodeCount = len(graph)\n",
    "        \n",
    "        # NOTE\n",
    "        # We are using BFS here because it's better suited for 'shortest path'\n",
    "        # types of problems. DFS solution is also viable though.\n",
    "\n",
    "        # Thoughts:\n",
    "        # 1. start at each node, do BFS to try reaching all other nodes.\n",
    "        # 2. Must keep track of visited nodes, else infinite loop may happen.\n",
    "        # 3. But each node may have to be visited multiple times, as described in the problem\n",
    "        #    statement. So we cannot be too strict in limiting searches\n",
    "        # 4. We must describe the state during a search, we need:\n",
    "        #    - The current node we are on\n",
    "        #    - Nodes we have visited (Notice the order does not matter in this case, that's a key)\n",
    "\n",
    "        # each search is described by (currentNode, visited)\n",
    "        # same search does _not_ have to be repeated, since if re-visited with\n",
    "        # the same state, it would yield the same result.\n",
    "        # NOTE this does not prevent revisiting the same node again,\n",
    "        # it just prevents revisiting it with the same STATE!\n",
    "\n",
    "        # Since the input size is restricted, we can use a number to encode\n",
    "        # which nodes have been visited -- the i-th bit is on iff node i has been visited\n",
    "\n",
    "        # conceptually masks[k] indicates that only node k has been visited\n",
    "        masks = [1 << i for i in range(nodeCount)]\n",
    "        # used to check whether all nodes have been visited (11111...111)\n",
    "        allVisited = (1 << nodeCount) - 1\n",
    "        queue = deque([(i, masks[i]) for i in range(nodeCount)])\n",
    "        steps = 0\n",
    "\n",
    "        # encoded_visited in visited_states[node] iff\n",
    "        # (node, encoded_visited) has been pushed onto the queue\n",
    "        visited_states = [{masks[i]} for i in range(nodeCount)]\n",
    "        # states in visited_states will never be pushed onto queue again\n",
    "\n",
    "        while queue:\n",
    "            # number of nodes to be popped off for current steps size\n",
    "            # this avoids having to store steps along with the state\n",
    "            # which consumes both time and memory\n",
    "            count = len(queue)\n",
    "\n",
    "            while count:\n",
    "                currentNode, visited = queue.popleft()\n",
    "                if visited == allVisited:\n",
    "                    return steps\n",
    "\n",
    "                # start bfs from each neighbor\n",
    "                for nb in graph[currentNode]:\n",
    "                    new_visited = visited | masks[nb]\n",
    "                    # pre-check here to for efficiency, as each steps increment may results\n",
    "                    # in huge # of nodes being added into queue\n",
    "                    if new_visited == allVisited:\n",
    "                        return steps + 1\n",
    "                    if new_visited not in visited_states[nb]:\n",
    "                        visited_states[nb].add(new_visited)\n",
    "                        queue.append((nb, new_visited))\n",
    "\n",
    "                count -= 1\n",
    "            steps += 1\n",
    "        # no path which explores every node\n",
    "        return inf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestPathLength(self, graph: List[List[int]]) -> int:\n",
    "    '''\n",
    "    dp(node, mask) = 1 + min(dp(neighbor, mask), dp(neighbor, mask ^ (1 << node))), for all neighbors in graph[node].this is working backward\n",
    "    The mask ^ (1 << node) operation is flipping the bit at position node using the method talked about before, to indicate that we are visiting this node for the first time.\n",
    "    '''\n",
    "    if len(graph) == 1:\n",
    "            return 0\n",
    "    #(node, mask), where node represents the label of the current node we are at,\n",
    "    # and mask represents a bitmask where all the nodes we have visited have their respective bits set to 1.\n",
    "    n = len(graph)\n",
    "    ending_mask = (1 << n) - 1 #a bitmask that represents all nodes being visited.\n",
    "    #This formula works because we are shifting a single bit to the left n times, which in the case of n = 5 gives us 100000,\n",
    "    #which after subtracting 1 will leave 5 bits set to 1, i.e. 100000 - 000001 = 011111.\n",
    "    queue = [(node, 1 << node) for node in range(n)] #This is (i, 1 << i) for all i from 0 to n - 1.\n",
    "    seen = set(queue)\n",
    "\n",
    "    steps = 0\n",
    "    while queue:\n",
    "        next_queue = []\n",
    "        for i in range(len(queue)):\n",
    "            node, mask = queue[i]\n",
    "            for neighbor in graph[node]:\n",
    "                next_mask = mask | (1 << neighbor) #bottom up bitwise or\n",
    "                if next_mask == ending_mask:\n",
    "                    return 1 + steps\n",
    "\n",
    "                if (neighbor, next_mask) not in seen:\n",
    "                    seen.add((neighbor, next_mask))\n",
    "                    next_queue.append((neighbor, next_mask))\n",
    "\n",
    "        steps += 1\n",
    "        queue = next_queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1584. Min Cost to Connect All Points\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimum Spanning Tree"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].\n",
    "\n",
    "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.\n",
    "\n",
    "Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kruskal Algo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        def dist(p1, p2):\n",
    "            return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])\n",
    "        n = len(points)\n",
    "        all_edges = []\n",
    "        \n",
    "        # Storing all edges of our complete graph.\n",
    "        for curr_node in range(n): \n",
    "            for next_node in range(curr_node + 1, n): \n",
    "                weight = dist(points[curr_node], points[next_node])\n",
    "                all_edges.append((weight, curr_node, next_node))\n",
    "        # Sort all edges in increasing order.\n",
    "        all_edges.sort()\n",
    "        uf = UnionFind(n)\n",
    "        mst_cost = 0\n",
    "        edges_used = 0\n",
    "        \n",
    "        for weight, node1, node2 in all_edges:\n",
    "            if uf.join(node1, node2):\n",
    "                mst_cost += weight\n",
    "                edges_used += 1\n",
    "                if edges_used == n - 1:\n",
    "                    break\n",
    "        return mst_cost\n",
    "    \n",
    "class UnionFind:\n",
    "    def __init__(self, size: int) -> None:\n",
    "        self.group = [0] * size\n",
    "        self.rank = [0] * size\n",
    "        \n",
    "        for i in range(size):\n",
    "            self.group[i] = i\n",
    "      \n",
    "    def find(self, node: int) -> int:\n",
    "        if self.group[node] != node:\n",
    "            self.group[node] = self.find(self.group[node])\n",
    "        return self.group[node]\n",
    "\n",
    "    def join(self, node1: int, node2: int) -> bool:\n",
    "        group1 = self.find(node1)\n",
    "        group2 = self.find(node2)\n",
    "        \n",
    "        # node1 and node2 already belong to same group.\n",
    "        if group1 == group2:\n",
    "            return False\n",
    "\n",
    "        if self.rank[group1] > self.rank[group2]:\n",
    "            self.group[group2] = group1\n",
    "        elif self.rank[group1] < self.rank[group2]:\n",
    "            self.group[group1] = group2\n",
    "        else:\n",
    "            self.group[group1] = group2\n",
    "            self.rank[group2] += 1\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prim's Algo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minCostConnectPoints(self, points: List[List[int]]) -> int:\n",
    "        def dist(p1, p2):\n",
    "            return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])\n",
    "        n = len(points)\n",
    "        \n",
    "        # Min-heap to store minimum weight edge at top.\n",
    "        heap = [(0, 0)]\n",
    "        \n",
    "        # Track nodes which are included in MST.\n",
    "        in_mst = [False] * n\n",
    "        \n",
    "        mst_cost = 0\n",
    "        edges_used = 0\n",
    "        \n",
    "        while edges_used < n:\n",
    "            weight, curr_node = heapq.heappop(heap)\n",
    "            \n",
    "            # If node was already included in MST we will discard this edge.\n",
    "            if in_mst[curr_node]:\n",
    "                continue\n",
    "            \n",
    "            in_mst[curr_node] = True\n",
    "            mst_cost += weight\n",
    "            edges_used += 1\n",
    "            \n",
    "            for next_node in range(n):\n",
    "                # If next node is not in MST, then edge from curr node\n",
    "                # to next node can be pushed in the priority queue.\n",
    "                if not in_mst[next_node]:\n",
    "                    next_weight = dist(points[curr_node], points[next_node])\n",
    "                    heapq.heappush(heap, (next_weight, next_node))\n",
    "                    \n",
    "        return mst_cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1631. Path With Minimum Effort\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.\n",
    "\n",
    "A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.\n",
    "\n",
    "Return the minimum effort required to travel from the top-left cell to the bottom-right cell."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Input: heights = [[1,2,2],[3,8,2],[5,3,5]]\n",
    "Output: 2\n",
    "Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.\n",
    "This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "    row = len(heights)\n",
    "    col = len(heights[0])\n",
    "    self.max_so_far = math.inf\n",
    "\n",
    "    def dfs(i, j, max_diff):\n",
    "        if i == row-1 and j == col-1:\n",
    "            self.max_so_far = min(self.max_so_far, max_diff)\n",
    "            return max_diff\n",
    "        curr_height = heights[i][j]\n",
    "        heights[i][j] = 0\n",
    "        min_effort = math.inf\n",
    "        for di, dj in [[0,1], [1, 0], [0, -1], [-1, 0]]:\n",
    "            adj_i = i + di\n",
    "            adj_j = j + dj\n",
    "            if 0 <= adj_i < row and 0<= adj_j< col and heights[adj_i][adj_j] !=0:\n",
    "                curr_diff = abs(heights[adj_i][adj_j]-curr_height)\n",
    "                max_curr_diff = max(max_diff, curr_diff)\n",
    "                if max_curr_diff < self.max_so_far:\n",
    "                    result = dfs(adj_i, adj_j, max_curr_diff)\n",
    "                    min_effort = min(min_effort, result)\n",
    "        heights[i][j] = curr_height\n",
    "        return min_effort\n",
    "\n",
    "    return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dijkstra's Algo O(mnlog(mn))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "    row = len(heights)\n",
    "    col = len(heights[0])\n",
    "    diff_matrix = [[math.inf]*col for _ in range(row)]\n",
    "    diff_matrix[0][0] =  0\n",
    "    visited = [[False] * col for _ in range(row)]\n",
    "    queue = [(0,0,0)] # difference, x, y\n",
    "    while queue:\n",
    "        diff, x, y = heapq.heappop(queue)\n",
    "        visited[x][y] = True\n",
    "        for dx, dy in [[0,1],[1,0],[0,-1],[-1,0]]:\n",
    "            adj_x = x + dx\n",
    "            adj_y = y + dy\n",
    "            if 0 <= adj_x < row and 0<=adj_y<col and not visited[adj_x][adj_y]:\n",
    "                curr_diff=abs(heights[adj_x][adj_y]-heights[x][y])\n",
    "                max_diff = max(curr_diff, diff_matrix[x][y])\n",
    "                if diff_matrix[adj_x][adj_y] > max_diff:\n",
    "                    diff_matrix[adj_x][adj_y] = max_diff\n",
    "                    heapq.heappush(queue, (max_diff, adj_x, adj_y))\n",
    "    return diff_matrix[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minimumEffortPath(self, heights: List[List[int]]) -> int:\n",
    "        row = len(heights)\n",
    "        col = len(heights[0])\n",
    "\n",
    "        def canReachDestinaton(mid):\n",
    "            visited = [[False]*col for _ in range(row)]\n",
    "            queue = [(0, 0)]  # x, y\n",
    "            while queue:\n",
    "                x, y = queue.pop(0)\n",
    "                if x == row-1 and y == col-1:\n",
    "                    return True\n",
    "                visited[x][y] = True\n",
    "                for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:\n",
    "                    adjacent_x = x + dx\n",
    "                    adjacent_y = y + dy\n",
    "                    if 0 <= adjacent_x < row and 0 <= adjacent_y < col and not visited[adjacent_x][adjacent_y]:\n",
    "                        current_difference = abs(\n",
    "                            heights[adjacent_x][adjacent_y]-heights[x][y])\n",
    "                        if current_difference <= mid:\n",
    "                            visited[adjacent_x][adjacent_y] = True\n",
    "                            queue.append((adjacent_x, adjacent_y))\n",
    "\n",
    "        left = 0\n",
    "        right = 10000000\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if canReachDestinaton(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1202. Smallest String With Swaps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def smallestStringWithSwaps(self, s, pairs):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        from collections import defaultdict\n",
    "\n",
    "        s = list(s)\n",
    "        nodes = [i for i in range(len(s))]\n",
    "        size = [1 for i in range(len(s))]\n",
    "\n",
    "        def find(x):\n",
    "            if x == nodes[x]:\n",
    "                return x\n",
    "            nodes[x] = find(nodes[x])\n",
    "            return nodes[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            rootx = find(x)\n",
    "            rooty = find(y)\n",
    "            if rootx != rooty:\n",
    "                nodes[rooty] = rootx\n",
    "\n",
    "        for e1, e2 in pairs:\n",
    "            union(e1, e2)\n",
    "\n",
    "        rootToComponent = defaultdict(list)\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            root = find(i)\n",
    "            rootToComponent[root].append(i)\n",
    "\n",
    "        for k, indices in rootToComponent.items():\n",
    "            chars = []\n",
    "            for i in indices:\n",
    "                chars.append(s[i])\n",
    "            chars = sorted(chars)\n",
    "\n",
    "            for c, i in zip(chars, indices):\n",
    "                s[i] = c\n",
    "\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type pairs: List[List[int]]\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dic = defaultdict(list)\n",
    "        s = list(s)\n",
    "        visited = [False for _ in range(len(s))]\n",
    "        \n",
    "        for source, dest in pairs:\n",
    "            dic[source].append(dest)\n",
    "            dic[dest].append(source)\n",
    "        \n",
    "        def dfs(s, i, chars, indices):\n",
    "            if visited[i]:\n",
    "                return\n",
    "            chars.append(s[i])\n",
    "            indices.append(i)\n",
    "            visited[i] = True\n",
    "            for neigh in dic[i]:\n",
    "                dfs(s, neigh, chars, indices)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if not visited[i]:\n",
    "                chars = []\n",
    "                indices = []\n",
    "                dfs(s, i, chars, indices)\n",
    "              \n",
    "                chars = sorted(chars)\n",
    "                indices = sorted(indices)\n",
    "                # print(chars)\n",
    "                # print(indices)\n",
    "                for c, i in zip(chars, indices):\n",
    "                    s[i] = c\n",
    "                # print(s)\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1041. Robot Bounded In Circle\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:\n",
    "\n",
    "\"G\": go straight 1 unit;\n",
    "\"L\": turn 90 degrees to the left;\n",
    "\"R\": turn 90 degrees to the right.\n",
    "The robot performs the instructions given in order, and repeats them forever.\n",
    "\n",
    "Return true if and only if there exists a circle in the plane such that the robot never leaves the circle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isRobotBounded(instructions: str) -> bool:\n",
    "        # north = 0, east = 1, south = 2, west = 3\n",
    "        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        # Initial position is in the center\n",
    "        x = y = 0\n",
    "        # facing north\n",
    "        idx = 0\n",
    "        \n",
    "        for i in instructions:\n",
    "            if i == \"L\":\n",
    "                idx = (idx + 3) % 4\n",
    "            elif i == \"R\":\n",
    "                idx = (idx + 1) % 4\n",
    "            else:\n",
    "                x += directions[idx][0]\n",
    "                y += directions[idx][1]\n",
    "        \n",
    "        # after one cycle:\n",
    "        # robot returns into initial position\n",
    "        # or robot doesn't face north\n",
    "        return (x == 0 and y == 0) or idx != 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "instructions = \"GGLLGG\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isRobotBounded(instructions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 200. Number of Islands\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "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.\n",
    "\n",
    "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.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"0\",\"0\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"1\",\"1\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "0\n",
      "0\n",
      "1\n",
      "1\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "print(grid[3][0])\n",
    "print(grid[3][1])\n",
    "print(grid[3][2])\n",
    "print(grid[3][3])\n",
    "print(grid[3][4])\n",
    "\n",
    "print(len(grid[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['1', '1', '0', '0', '0'], ['1', '1', '0', '0', '0'], ['0', '0', '1', '0', '0'], ['0', '0', '0', '1', '1']]\n"
     ]
    }
   ],
   "source": [
    "print(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DFS solves the problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numIslands(grid: List[List[str]]) -> int:\n",
    "    \n",
    "    def dfs(i,j, grid):\n",
    "        print(f'point: {i},{j}')\n",
    "        if i < 0 or j < 0 or i>= len(grid) or j>= len(grid[0]) or grid[i][j]!='1':\n",
    "            return\n",
    "        grid[i][j] = '2'\n",
    "        dfs(i,j+1, grid)\n",
    "        dfs(i,j-1, grid)\n",
    "        dfs(i+1,j, grid)\n",
    "        dfs(i-1,j, grid)\n",
    "    island = 0\n",
    "    if not grid:\n",
    "        return island\n",
    "\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            if grid[i][j] == '1':\n",
    "                dfs(i, j, grid)\n",
    "                island+=1\n",
    "                print(island)\n",
    "    return island"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "numIslands(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1254. Number of Closed Islands\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "Return the number of closed islands.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "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]]# return 2 Islands in gray are closed because they are completely surrounded by water (group of 1s).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] # return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [[1,1,1,1,1,1,1],\n",
    "               [1,0,0,0,0,0,1],\n",
    "               [1,0,1,1,1,0,1],\n",
    "               [1,0,1,0,1,0,1],\n",
    "               [1,0,1,1,1,0,1],\n",
    "               [1,0,0,0,0,0,1],\n",
    "               [1,1,1,1,1,1,1]]# return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [[0,0,1,1,0,1,0,0,1,0],\n",
    "        [1,1,0,1,1,0,1,1,1,0],\n",
    "        [1,0,1,1,1,0,0,1,1,0],\n",
    "        [0,1,1,0,0,0,0,1,0,1],\n",
    "        [0,0,0,0,0,0,1,1,1,0],\n",
    "        [0,1,0,1,0,1,0,1,1,1],\n",
    "        [1,0,1,0,1,1,0,0,0,1],\n",
    "        [1,1,1,1,1,1,0,0,0,0],\n",
    "        [1,1,1,0,0,1,0,1,0,1],\n",
    "        [1,1,1,0,1,1,0,1,1,0]] # return 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = [[0,1,0,1,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,1],[0,1,1,0,0,0,0,1,1,1,0,1,0,1,1,0,0,1,0,1],[1,1,0,1,0,0,1,1,1,0,0,0,1,0,0,1,0,1,0,0],[0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,1,1,1,0],[1,1,0,0,1,0,0,1,1,0,1,1,0,1,1,1,0,0,1,1],[1,1,0,0,0,0,0,1,0,1,1,1,0,1,0,0,0,0,0,1],[1,0,1,1,0,1,0,1,0,0,1,0,1,1,1,1,1,0,1,0],[1,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1],[0,0,0,1,1,1,0,1,1,1,0,1,0,1,1,0,1,0,0,0],[1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,0,1,0,1,1],[1,0,0,1,1,1,1,0,1,0,1,1,1,0,0,0,0,1,1,0],[1,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,0,1,1,1],[0,1,1,0,0,1,1,0,0,1,0,1,1,1,1,1,1,0,0,0],[1,0,0,0,1,1,0,1,1,1,0,0,1,0,1,1,0,1,0,1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def dfs(i,j):\n",
    "            print(f'point: {i},{j}')\n",
    "            if i in (0 , len(grid)-1) or j in ( 0,len(grid[0])-1):\n",
    "                self.isisland = False\n",
    "\n",
    "            for i, j in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n",
    "                if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 0:\n",
    "                    grid[i][j] = 2 \n",
    "                    dfs(i, j)\n",
    "\n",
    "        island = 0\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "    #             print(i,j)\n",
    "                if grid[i][j] == 0:\n",
    "                    self.isisland = True\n",
    "                    dfs(i, j)\n",
    "                    island+=self.isisland\n",
    "                    print(island)\n",
    "        return island"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "Sol = Solution()\n",
    "Sol.closedIsland(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def closedIsland(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            if x in (0, m-1) or y in (0, n-1):\n",
    "                self.isIsland = False \n",
    "            for i, j in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j] == 0:\n",
    "                    grid[i][j] = -1 \n",
    "                    dfs(i, j)\n",
    "                    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    self.isIsland = True\n",
    "                    dfs(i, j)\n",
    "                    res += self.isIsland\n",
    "                    \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 198,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sol2 = Solution()\n",
    "Sol2.closedIsland(grid)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2477. Minimum Fuel Cost to Report to the Capital\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.\n",
    "\n",
    "There is a meeting for the representatives of each city. The meeting is in the capital city.\n",
    "\n",
    "There is a car in each city. You are given an integer seats that indicates the number of seats in each car.\n",
    "\n",
    "A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.\n",
    "\n",
    "Return the minimum number of liters of fuel to reach the capital city."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "BFS Solution: leaf to root traversal non tradition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "    n = len(roads)+1\n",
    "    degree = [0] * n\n",
    "    represent = [1] * n\n",
    "    adj = collections.defaultdict(list)\n",
    "    for src, dest in roads:\n",
    "        adj[src].append(dest)\n",
    "        adj[dest].append(src)\n",
    "        degree[src] +=1\n",
    "        degree[dest] +=1\n",
    "    #bfs\n",
    "    # visited = set()\n",
    "    queue = deque([])\n",
    "    for i in range(len(degree)):\n",
    "        if degree[i] == 1 and i != 0:\n",
    "            queue.append((i))\n",
    "    fuel = 0\n",
    "    while queue:\n",
    "        for _ in range(len(queue)):\n",
    "            curr_node = queue.popleft()\n",
    "            fuel += math.ceil(represent[curr_node] / seats)\n",
    "            for nei in adj[curr_node]:\n",
    "                represent[nei] += represent[curr_node]\n",
    "                degree[nei] -=1\n",
    "                # if nei not in visited:\n",
    "                    # fuel +=1\n",
    "                if degree[nei] ==1 and nei != 0:\n",
    "                    # visited.add(nei)\n",
    "                    queue.append(nei)\n",
    "    return fuel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DFS solution pay attention to the ceiling function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:\n",
    "    fuel = 0 \n",
    "    n = len(roads) + 1\n",
    "    adj = [[] for _ in range(n)]\n",
    "    for road in roads:\n",
    "        adj[road[0]].append(road[1])\n",
    "        adj[road[1]].append(road[0])\n",
    "\n",
    "    def dfs(node, parent, adj, seats):\n",
    "        nonlocal fuel\n",
    "        representatives = 1\n",
    "        for child in adj[node]:\n",
    "            if child != parent:\n",
    "                representatives += dfs(child, node, adj, seats)\n",
    "        if node != 0 :\n",
    "            fuel += math.ceil(representatives/seats)\n",
    "        return representatives\n",
    "    dfs(0, -1, adj, seats)\n",
    "    return fuel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1129. Shortest Path with Alternating Colors\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.\n",
    "\n",
    "You are given two arrays redEdges and blueEdges where:\n",
    "\n",
    "redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and\n",
    "blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.\n",
    "Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "    adj = [[] for _ in range(n)] \n",
    "    for red_s, red_d in redEdges:\n",
    "        adj[red_s].append((red_d, 0))\n",
    "    for blue_s, blue_d in blueEdges:\n",
    "        adj[blue_s].append((blue_d, 1))\n",
    "    visited = set()\n",
    "    visited.add((0, 0))\n",
    "    visited.add((0, 1))\n",
    "\n",
    "    ans = [-1] *n \n",
    "    ans[0] = 0 \n",
    "    # for i in range(n):\n",
    "    queue = deque([(0, 0, 0)])\n",
    "    queue.append((0, 1, 0))\n",
    "    while queue:\n",
    "        curr_node, last_color, step = queue.popleft()\n",
    "        if ans[curr_node] == -1:\n",
    "            ans[curr_node] = step\n",
    "        # if curr_node == i:\n",
    "        #     ans[i] = step\n",
    "        for nei, color in adj[curr_node]:\n",
    "            if last_color != color and (nei, color) not in visited:\n",
    "                # if ans[nei] == -1:\n",
    "                #     ans[nei] = step+1\n",
    "                visited.add((nei, color))\n",
    "                queue.append((nei, color, step+1))\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1514. Path with Maximum Probability\n",
    "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].\n",
    "\n",
    "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.\n",
    "\n",
    "If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.\n",
    "\n",
    "###GPT 4 can do it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "    graph = [[] for _ in range(n)]\n",
    "    for (x, y), prob in zip(edges, succProb):\n",
    "        graph[x].append((y, prob))\n",
    "        graph[y].append((x, prob))\n",
    "\n",
    "    max_prob = [0.0] * n\n",
    "    max_prob[start] = 1.0\n",
    "    priority_queue = [(-1.0, start)]\n",
    "\n",
    "    while priority_queue:\n",
    "        prob, node = heapq.heappop(priority_queue)\n",
    "        prob = -prob\n",
    "        if prob < max_prob[node]: continue\n",
    "        for nxt_node, succProb in graph[node]:\n",
    "            if max_prob[node] * succProb > max_prob[nxt_node]:\n",
    "                max_prob[nxt_node] = max_prob[node] * succProb\n",
    "                heapq.heappush(priority_queue, (-max_prob[nxt_node], nxt_node))\n",
    "\n",
    "    return max_prob[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "    graph = defaultdict(list)\n",
    "    for i, (a, b) in enumerate(edges):\n",
    "        graph[a].append([b, succProb[i]])\n",
    "        graph[b].append([a, succProb[i]])\n",
    "\n",
    "    max_prob = [0.0] * n    \n",
    "    max_prob[start] = 1.0\n",
    "\n",
    "    queue = deque([start])\n",
    "    while queue:\n",
    "        cur_node = queue.popleft()\n",
    "        for nxt_node, path_prob in graph[cur_node]:\n",
    "\n",
    "            # Only update max_prob[nxt_node] if the current path increases\n",
    "            # the probability of reach nxt_node.\n",
    "            if max_prob[cur_node] * path_prob > max_prob[nxt_node]:\n",
    "                max_prob[nxt_node] = max_prob[cur_node] * path_prob\n",
    "                queue.append(nxt_node)\n",
    "\n",
    "    return max_prob[end]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}