graph problems

flood_fill.js

var floodFill = (image, sr, sc, newColor, firstColor) => {
   const dfs = (image, sr, sc, newColor, firstColor) =>{
    if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[sr].length || image[sr][sc] !== firstColor || image[sr][sc] === newColor)   {
        return image; // return image as-is
    }
    
    image[sr][sc] = newColor;
    
    dfs(image, sr + 1, sc, newColor, firstColor);
    dfs(image, sr - 1, sc, newColor, firstColor);
    dfs(image, sr, sc + 1, newColor, firstColor);
    dfs(image, sr, sc - 1, newColor, firstColor);
    }
    
    dfs(image, sr, sc, newColor, image[sr][sc]);
 
    
    return image;
    
}; 

// this works because of hoisting
// previously in same function there is no "hoisting" because that's not how hoisting works. Need to be in gloabl scope?

var floodFill2 = (image, sr, sc, newColor, firstColor) => {
  
    dfs2(image, sr, sc, newColor, image[sr][sc]);

    return image;
    
}; 

 const dfs2 = (image, sr, sc, newColor, firstColor) =>{
    if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[sr].length || image[sr][sc] !== firstColor || image[sr][sc] === newColor)   {
        return image; // return image as-is
    }
    
    image[sr][sc] = newColor;
    
    dfs(image, sr + 1, sc, newColor, firstColor);
    dfs(image, sr - 1, sc, newColor, firstColor);
    dfs(image, sr, sc + 1, newColor, firstColor);
    dfs(image, sr, sc - 1, newColor, firstColor);
    }
    

march_8_code_kl.py

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        # this is about counting in-degrees and out-degrees 
        # town judge should have 0 out-degree and N-1 in-degree
        # [1, 2]
        # 1 -> 2 
        out_degree, in_degree = {i:0 for i in range(1, N+1)}, {i:0 for i in range(1, N+1)}
        
        for edge in trust:
            out_degree[edge[0]] = out_degree.get(edge[0], 0)+1
            in_degree[edge[1]] = in_degree.get(edge[1], 0)+1
        
        for i in range(1, N+1):
            if out_degree[i] == 0 and in_degree[i] == N-1:
                return i 
        return -1 
    
'''
Success
Details 
Runtime: 800 ms, faster than 59.89% of Python3 online submissions for Find the Town Judge.
Memory Usage: 17.3 MB, less than 10.00% of Python3 online submissions for Find the Town Judge.
Next challenges:
Find the Celebrity
'''

# build a graph representing the relationship between each course
# Calculate in-degree for each node
# Start from node with 0 in-degree (no-prerequisites) and update in-degree during
# graph traversal. Track each visited course and return true if we are able to visit each course, else false
# go over an example of success, an example of failure
from collections import deque 
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        postReqs = {i:set() for i in range(numCourses)}
        inDegree = {i:0 for i in range(numCourses)}
        for c1, c2 in prerequisites:
            postReqs[c2].add(c1)
            inDegree[c1] += 1 
        queue = deque([c for c, v in inDegree.items() if v == 0])
        visited = set()
        while queue:
            curCourse = queue.popleft()
            visited.add(curCourse)
            for nextCourse in postReqs[curCourse]:
                inDegree[nextCourse] -= 1 
                if inDegree[nextCourse] == 0:
                    queue.append(nextCourse)
        return len(visited) == numCourses
    
        
'''
Success
Details 
Runtime: 104 ms, faster than 53.26% of Python3 online submissions for Course Schedule.
Memory Usage: 13.9 MB, less than 97.96% of Python3 online submissions for Course Schedule.
Next challenges:
Graph Valid Tree
Minimum Height Trees
Course Schedule III
'''

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        islands = 0 
        # run dfs on graph, count how many "runs"
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    islands += 1 
        return islands
        
    
    def dfs(self, grid, r, c):
        directions = [(1, 0), (0, 1), (0, -1), (-1, 0)]
        grid[r][c] = "x"
        for d in directions:
            nr, nc = d[0]+r, d[1]+c
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == '1':
                grid[nr][nc] = "x"
                self.dfs(grid, nr, nc)
        
                 
'''
Success
Details 
Runtime: 136 ms, faster than 88.33% of Python3 online submissions for Number of Islands.
Memory Usage: 13.8 MB, less than 70.09% of Python3 online submissions for Number of Islands.
Next challenges:
Walls and Gates
Number of Islands II
Number of Connected Components in an Undirected Graph
Number of Distinct Islands
'''


"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
from collections import deque 
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # use bfs, find deepest level
        if not root:
            return 0
        queue = deque([root])
        level = 0 
        while queue:
            qlength = len(queue)
            for i in range(qlength):
                curNode =queue.popleft()
                for child in curNode.children:
                    queue.append(child)
            level += 1 
        return level 
             

'''
Success
Details 
Runtime: 28 ms, faster than 99.96% of Python3 online submissions for Maximum Depth of N-ary Tree.
Memory Usage: 14.8 MB, less than 100.00% of Python3 online submissions for Maximum Depth of N-ary Tree.
Next challenges:
Open the Lock
Smallest String Starting From Leaf
Sum of Nodes with Even-Valued Grandparent
'''

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque 
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([root])
        while queue:
            qlength = len(queue)
            leaf_sum = 0
            for i in range(qlength):
                curNode = queue.popleft()
                if not curNode.left and not curNode.right:
                    leaf_sum += curNode.val
                if curNode.left:
                    queue.append(curNode.left)
                if curNode.right:
                    queue.append(curNode.right)
        return leaf_sum
                
      
'''
Success
Details 
Runtime: 96 ms, faster than 70.75% of Python3 online submissions for Deepest Leaves Sum.
Memory Usage: 16.4 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.
Next challenges:
Path Sum III
Increasing Order Search Tree
Sum of Root To Leaf Binary Numbers
'''

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        self.leaf_sum = 0 
        self.max_depth = 1
        self.dfs(root, 1)
        return self.leaf_sum 
    
    def dfs(self, node, cur_depth):
        if not node:
            return 
        if not node.left and not node.right:
            if cur_depth == self.max_depth:
                self.leaf_sum += node.val
            elif self.max_depth < cur_depth:
                self.max_depth = cur_depth
                self.leaf_sum = node.val  
        self.dfs(node.left, cur_depth+1)
        self.dfs(node.right, cur_depth+1)
        
        
'''
Success
Details 
Runtime: 100 ms, faster than 56.94% of Python3 online submissions for Deepest Leaves Sum.
Memory Usage: 16 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.
Next challenges:
Subtree of Another Tree
Minimum Distance Between BST Nodes
Lowest Common Ancestor of Deepest Leaves
''' 


class Solution:
    def numEnclaves(self, A: List[List[int]]) -> int:
       
        for i in range(len(A)):
            for j in range(len(A[0])):
                if i == 0 or i == len(A)-1 or j == 0 or j == len(A[0])-1:
                    if A[i][j] == 1:
                        self.dfs(A, i, j)
        count = 0 
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == 1:
                    count += 1 
        return count 
    
    def dfs(self, grid, r, c):
        grid[r][c] = 0 
        for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nr, nc = d[0]+r, d[1]+c
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 1:
                grid[nr][nc] = 0 
                self.dfs(grid, nr, nc)

'''
Success
Details 
Runtime: 624 ms, faster than 43.89% of Python3 online submissions for Number of Enclaves.
Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Number of Enclaves.
Next challenges:
Number of Connected Components in an Undirected Graph
Regions Cut By Slashes
Number of Operations to Make Network Connected
'''

# slight optimization
class Solution:
    def numEnclaves(self, A: List[List[int]]) -> int:
        zeroes = 0
        self.edge_ones = 0 
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == 0:
                    zeroes += 1  
                if i ==0 or j == 0 or i == len(A)-1 or j == len(A[0])-1:
                    if A[i][j] == 1:
                        self.dfs(A, i, j)
        return len(A)*len(A[0])- zeroes - self.edge_ones 
    
    def dfs(self, grid, r, c):
        grid[r][c] = 'x'
        self.edge_ones += 1 
        for d in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nr, nc = d[0]+r, d[1]+c
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 1:
                grid[nr][nc] = 'x' 
                self.dfs(grid, nr, nc)
        
'''
Success
Details 
Runtime: 624 ms, faster than 43.89% of Python3 online submissions for Number of Enclaves.
Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Number of Enclaves.
Next challenges:
Target Sum
Number of Distinct Islands II
Minimize Malware Spread
'''
        

problem_list.txt

3/8/20 
1) https://leetcode.com/problems/find-the-town-judge 
2) https://leetcode.com/problems/course-schedule 
3) https://leetcode.com/problems/number-of-islands 
4) https://leetcode.com/problems/flood-fill
5) https://leetcode.com/problems/maximum-depth-of-n-ary-tree 
6) https://leetcode.com/problems/word-search 

Feedback for Jing (Course Schedule) 
Describe the algorithm (topological sort without talking about implementation details/how code will run
i.e. high level: This problem requires us to build a graph of the courses and determine if it is a DAG (no cycles, connected)
then say I will use top sort to accomplish this. If asked about top sort details, talk about starting from 
course with in-degree 0, etc.

3/9/20
7) https://leetcode.com/problems/deepest-leaves-sum/ 
8) https://leetcode.com/problems/number-of-enclaves/ 
9) https://leetcode.com/problems/loud-and-rich

3/10/20 
10) https://leetcode.com/problems/01-matrix 
11) https://leetcode.com/problems/pacific-atlantic-water-flow