DEV Community: Shoryu

Number of Islands - Union Find Solution

Shoryu — Sat, 22 Feb 2020 01:56:38 +0000

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Question

Number of Islands

We have to count the number of islands in Given a 2d grid map of '1's (land) and '0's (water).

An island is defined as below.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Approach

To check a 2d grid map, DFS or BFS is useful in many cases.

This question can be solved by DFS and Union Find Algorithm.
I'm gonna write about Union Find solution in this article.

In this algorithm, we can group the nodes and find the group number of some node(we can find the parent of some node).

To solve this question, if we find the '1'(land), we're gonna union the adjacent lands horizontally or vertically as much as possible.

Repeat the above process over and over again, and then finally the number of group is the answer for this question.

Solution

class Solution:

    def numIslands(self, grid: List[List[str]]) -> int:    
        if not grid:
            return 0
        grid_y = len(grid)
        grid_x = len(grid[0])

        uf = UnionFind(grid)

        for i in range(grid_y):
            for j in range(grid_x):
                if grid[i][j] == '1':
                    for k, l in ([1,0], [-1,0], [0,1], [0,-1]):
                        ny, nx = i+k, j+l
                        if 0<= ny < grid_y and 0 <= nx < grid_x and grid[ny][nx] == '1':
                            uf.union(i*grid_x+j, ny*grid_x+nx)
        return uf.count                     


class UnionFind:
    def __init__(self, grid):

        y = len(grid)
        x = len(grid[0])
        self.parents = [0] * (y*x)
        self.count = 0

        for i in range(y):
            for j in range(x):
                if grid[i][j] == '1':
                    self.parents[i*x+j] = -1
                    self.count += 1
    def find(self, x):

        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):

        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.count -= 1

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Valid Parentheses

Shoryu — Sat, 15 Feb 2020 01:52:22 +0000

This is a part of my series where I memo learning from LeetCode. If you have better solutions or ideas, please leave a comment!

Problems

Valid Parentheses

We have to check the given string is valid parentheses.
The given string is invalid when there is a lacking of right or left parenthesis or the order of parentheses is wrong.

For example,

"([])" -> OK
"()[]{}" -> OK
"[](()" -> NG
"([)]" -> NG
"]" -> NG

Approach

Stack and map are useful for this question.

We are gonna look the given string in order from the front.

When the char is the left side parenthesis, add it to stack, and when the char is the right side parenthesis, pop stack top value and check whether is valid or not by using map.
So we have to set the map as below,

parentheses_map = [")":"(", "}":"{", "]":"["]

Finally, if stack is empty, the string is valid.

Solution

class Solution:
    def isValid(self, s: str) -> bool:

        stack = []

        parentheses_map = {")":"(", "}":"{", "]":"["}

        for i in s:
            if i in parentheses_map:
                stack_top = stack.pop() if stack else ' '
                if parentheses_map[i] != stack_top:
                    return False
            else:
                stack.append(i)
        return not stack

Note: In the above Solution code, when the stack is empty, we have to assign a dummy value because if write as below,

if stack:
    stack_top = stack.pop()

the case s = "]" are gonna be True and this is a wrong answer.

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Serialize and Deserialize Binary Tree

Shoryu — Sat, 01 Feb 2020 10:42:51 +0000

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Problems

Serialize and Deserialize Binary Tree

We have to serialize a given binary tree to string, and then deserialize the string to the former binary tree.
So let's start with thinking about how to traverse the tree.

Approach

(https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/995/)

For starters let's think about the above example.
In the above example, the output string is [1, 2, 3, null, null ,4, 5].

To traverse tree, BFS or DFS is useful and We have to think which one is better.

DFS is more adapted because it will be easier to deserialize than BFS because the order of node encoded on BFS is based on the linkage of nodes. If you know the other reason to use DFS or you think BFS is more adapted and know the reason why it is, please leave your comment about your opinion!

Solution

class Codec:

    def serialize(self, root):
        """ Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def encode(root, string):
            """ a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += 'None,'
            else:
                string += str(root.val) + ','
                string = encode(root.left, string)
                string = encode(root.right, string)
            return string

        return encode(root, '')
# Deserialization 
class Codec:

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def decode(l):
            """ a recursive helper function for deserialization."""
            if l[0] == 'None':
                l.pop(0)
                return None

            root = TreeNode(l[0])
            l.pop(0)
            root.left = decode(l)
            root.right = decode(l)
            return root

        data_list = data.split(',')
        root = decode(data_list)
        return root

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Construct Binary Tree from Inorder and Postorder Traversal

Shoryu — Sun, 26 Jan 2020 02:29:05 +0000

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Problems

Construct Binary Tree from Inorder and Postorder Traversal

We want to return the binary tree by given inorder and postorder Traversal.

Approach

Postorder is left->right->root and inorder is left->root->right, so the root of tree is the rightmost of postorder traversal and we can get to know the subtree of it by checking inorder traversal.

For example:
inorder = 9,3,15,20,7 (left->root->right)
postorder = 9,15,7,20,3 (left->right->root)

The root is 3 because it is the rightmost in postorder traversal and the left subtree is 9 and the right subtree is 15, 20, 7 because in inorder Traversal, 9 is left of 3(=root) and 15, 20, 7 is right of 3. The next root is 20, and the right subtree is 15 and the left subtree is 7.

So we are able to solve this question by repeating this process.

Solution

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def helper(left_end, right_end):
            if left_end > right_end:
                return None

            value = postorder.pop()
            root = TreeNode(value)

            index = index_map[value]

            root.right = helper(index + 1, right_end)
            root.left = helper(left_end, index - 1)
            return root

        index_map = {val:idx for idx, val in enumerate(inorder)} 
        return helper(0, len(inorder) - 1)

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Path Sum

Shoryu — Sun, 19 Jan 2020 01:51:17 +0000

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

Problems

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf >path such that adding up all the values along the path equals the given >sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
11  13  4
 /  \        \
7    2        1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is >22.

We want to know the sum of the value of the route from root to leaf.

In the above example, root is 5 and leaves are 13, 7, 2 and 1, so we have to check the route 5->8->13, 5->4->11->7, 5->4->11->2 and 5->8->4->1.

Approach

We are gonna check the four route by BFS(breadth first search).

In the above example, the BFS order is [5, 4, 8, 11, 13, 4, 7, 2, 1].

We are able to get the sum of the value of the route by adding the value of node to the value of its children. That's say, when the root's value is 5 and the children's values are 4 and 8, we make the children's values are 9 and 13 by adding the root's value and repeat it until the child is a leaf.

Solution

from collections import deque
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if root is None:
            return False

        queue = deque([root,])

        while queue:
            node = queue.popleft()
            if node.left is not None:
                node.left.val += node.val
                queue.append(node.left)
            if node.right is not None:
                node.right.val += node.val
                queue.append(node.right)
            if node.right is None and node.left is None and node.val == sum:
                return True
        return False

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Morris In-order Tree Traversal

Shoryu — Sun, 12 Jan 2020 07:55:20 +0000

This is part of my series where I memo learning from LeetCode. If you have better solutions or ideas, please leave a comment!

The pattern of Tree Traversal

Here are three patterns for Tree Traversal.

Each patten has only one order.

Pre-order Traversal
- root -> left -> right
In-order Traversal
- left -> root -> right
Post-order Traversal
- right -> left -> root

Problem

Today's problem is about In-order Traversal.

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.
Example:

Input: [1,null,2,3]

Output: [1,3,2]

We have to put the values of Input in In-order, which is left -> root -> right.

Approach

To solve the problem with Morris In-order Tree Traversal, we have to follow the rules below.

if current has no left child,
- Add current's value to output.
- current = current.right.
if current has left child,
- make the current the right child of the rightmost node in current's left subtree.
- current = current.left

note: Don't forget the original current left to be null to avoid infinite loops in rule.2

Here is the example of the traversal.

Solution: Morris In-order Tree Traversal

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        output = []
        current = root

        while current is not None:
            if current.left is None:
                output.append(current.val)
                current = current.right
            else:
                predecessor = current.left
                while predecessor.right:
                    predecessor = predecessor.right 
                predecessor.right = current
                tmp = current
                current = current.left
                tmp.left = None
        return output

Thank you for reading this article!
I always welcome your feedback, question, and idea.

Morris Pre-order Tree Traversal

Shoryu — Sat, 11 Jan 2020 09:18:45 +0000

This is part of my series where I memo learning from Leetcode. If you have better solutions or ideas, please leave a comment!

The pattern of Tree Traversal

Here are three patterns for Tree Traversal.

Each patten has only one order.

Pre-order Traversal
- root -> left -> right
In-order Traversal
- left -> root -> right
Post-order Traversal
- right -> left -> root

Problem

Today's problem is about Pre-order Traversal.

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]

Output: [1,2,3]

We have to put the values of Input in Pre-order, which is root -> left -> right.

Approach

To solve the problem with Morris Traversal, we have to follow the four steps below.

go one step left if possible and then go right till the end.
add Node to output and establish the link predecessor.right = node.
When we visit the same predecessor the second time, it already points to the current node, thus we remove the link created at step2 and move to right node with node = node.right.
return step1

note: If the step1 is impossible, add node to output and move right to next node.

Here are the points you should remember.

Add output when node has no left node or predecessors.right is null.
when predecessor has no right node, make the link from predecessor to node.
after making the link from predecessor to node, move the node to left.
after delete the link from predecessor to node, move the node to right.

Here is the example of the traversal.

Solution: Morris Pre-order Tree Traversal

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :type: List[int]
        """
        node = root
        output = []
        while node:
            if node.left is None:
                output.append(node.val)
                node = node.right
            else:                
                predecessor = node.left
                while predecessor.right and predecessor.right is not node:
                    predecessor = predecessor.right
                if predecessor.right is None:
                    output.append(node.val)
                    predecessor.right = node
                    node = node.left
                else:
                    predecessor.right = None
                    node = node.right
        return output

Thank you for reading this article!
I always welcome your feedback, question, and idea.