<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Wangyy on Medium]]></title>
        <description><![CDATA[Stories by Wangyy on Medium]]></description>
        <link>https://medium.com/@wangyy395?source=rss-ca7cde3eb133------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*81VrCIKFrwdpo1AzzrUtzA.jpeg</url>
            <title>Stories by Wangyy on Medium</title>
            <link>https://medium.com/@wangyy395?source=rss-ca7cde3eb133------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 20:20:33 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@wangyy395/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Leetcode 38: Count and Say]]></title>
            <link>https://wangyy395.medium.com/leetcode-38-count-and-say-78730a482aef?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/78730a482aef</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Sat, 20 Mar 2021 21:58:13 GMT</pubDate>
            <atom:updated>2021-03-20T21:58:13.067Z</atom:updated>
            <content:encoded><![CDATA[<p>Let’s solve a medium problem together on Leetcode.com: <a href="https://leetcode.com/problems/count-and-say/">Count and Say</a></p><h4>Description</h4><blockquote><em>The </em><strong><em>count-and-say</em></strong><em> sequence is a sequence of digit strings defined by the recursive formula:</em></blockquote><blockquote><em>countAndSay(1) = &quot;1&quot;</em></blockquote><blockquote><em>countAndSay(n) is the way you would &quot;say&quot; the digit string from </em><em>countAndSay(n-1), which is then converted into a different digit string.</em></blockquote><blockquote><em>To determine how you “say” a digit string, split it into the </em><strong><em>minimal</em></strong><em> number of groups so that each group is a contiguous section all of the </em><strong><em>same character.</em></strong><em> Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.</em></blockquote><blockquote><em>For example, the saying and conversion for digit string </em><em>&quot;3322251&quot;:</em></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/581/0*nhacUEcZA7eBe7RY.jpg" /></figure><blockquote><em>Given a positive integer </em><em>n, return the </em><em>nth term of the </em><strong><em>count-and-say</em></strong><em> sequence.</em></blockquote><p>Example:</p><pre><strong>Input:</strong> n = 4<br><strong>Output:</strong> &quot;1211&quot;<br><strong>Explanation:</strong><br>countAndSay(1) = &quot;1&quot;<br>countAndSay(2) = say &quot;1&quot; = one 1 = &quot;11&quot;<br>countAndSay(3) = say &quot;11&quot; = two 1&#39;s = &quot;21&quot;<br>countAndSay(4) = say &quot;21&quot; = one 2 + one 1 = &quot;12&quot; + &quot;11&quot; = &quot;1211&quot;</pre><h4>Solution</h4><p>For a given string, in order to “Count and Say” it, there are two variables to consider:</p><ul><li>count of the current character</li><li>what’s the current character?</li></ul><p>Assume the string we’re visiting is “1211”, let’s have two variables count and previous to record the result while iterating the string.</p><ul><li><strong>Step 1: initialization</strong></li></ul><p>Before visiting the string, let’s say count = 0 and previous = ‘.’ to represent the initial state and a variable result to denote the output.</p><ul><li><strong>Step 2: visit index 0, character = ‘1’</strong></li></ul><p>Now, the current character we’re visiting is ‘1’. prevous = ‘.’ is denoting the current character is the beginning of the string, we simply increment the count by 1 and set the previous = ‘1’ for the next visiting character.</p><ul><li><strong>Step 3: visit index 1, character = ‘2’</strong></li></ul><p>The current character we’re visiting is ‘2’. prevous = ‘1’ is denoting the current character is a new character we need to “<strong>count and say</strong>”. Now, we need to do two things: 1). record the previous result: append count and previous to the result. After appending, result = ‘11’; 2). renew count = 1, and prevous = ‘2’ for the next visiting character.</p><ul><li><strong>Step 4: visit index 2, character = ‘1’</strong></li></ul><p>The current character we’re visiting is ‘1’. prevous = ‘2’ is denoting the current character is a new character we need to “<strong>count and say</strong>”. Now, we need to do two things: 1). record the previous result: append count and previous to the result. After appending, result = ‘1112’; 2). renew count = 1, and prevous = ‘1’ for the next visiting character.</p><ul><li><strong>Step 5: visit index 3, character = ‘1’</strong></li></ul><p>The current character we’re visiting is ‘1’ is the same with prevous = ‘1’ . We increment the count = 2 variable and leave the previous.</p><ul><li><strong>Step 6: done iteration</strong></li></ul><p>After iterating the string, we still need to append the last visiting&#39;s result to the output: result = ‘111221’ . Depending on the iteration times, we’ll decide whether return the result or input it as a string for the next iteration.</p><h4>Code</h4><pre>def countAndSay(n: int) -&gt; str:<br>    res = &#39;1&#39;</pre><pre>    for _ in range(1, n):<br>        prev, count = &#39;.&#39;, 0<br>        curr_str = &quot;&quot;<br>        for char in res:<br>            if char == prev or prev == &#39;.&#39;:<br>                count += 1<br>            else:<br>                curr_str += str(count) + prev<br>                count = 1<br>            prev = char</pre><pre>        curr_str += str(count) + prev<br>        res = curr_str</pre><pre>    return res</pre><h4>Reference</h4><p><a href="https://leetcode.com/problems/count-and-say/">Count and Say - LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=78730a482aef" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to flatten a binary tree to a linked list: recursion approach]]></title>
            <link>https://wangyy395.medium.com/how-to-flatten-a-binary-tree-to-a-linked-list-recursion-approach-565c4353bd91?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/565c4353bd91</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Sun, 14 Mar 2021 20:39:32 GMT</pubDate>
            <atom:updated>2021-03-14T20:39:32.502Z</atom:updated>
            <content:encoded><![CDATA[<p>Data structures such as binary trees, linked lists are frequently asked in a technical interview. Sometimes, interviewees are asked to transform one data structure to another. For example, convert a list to a linked list, or covert an ordered list to a binary tree, etc. Today, I’ll talk about a medium problem in leetcode.com:<a href="https://leetcode.com/problems/flatten-binary-tree-to-linked-list/"> flatten a binary tree to linked list</a>.</p><h4>Description</h4><blockquote><em>Given the </em><em>root of a binary tree, flatten the tree into a &quot;linked list&quot;:</em></blockquote><blockquote><em>The “linked list” should use the same </em><em>TreeNode class where the </em><em>right child pointer points to the next node in the list and the </em><em>left child pointer is always </em><em>null.</em></blockquote><blockquote><em>The “linked list” should be in the same order as a </em><a href="https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR"><strong><em>pre-order traversal</em></strong></a><em> of the binary tree.</em></blockquote><p><strong>Example:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/890/1*KKIbC1mJPkbUVS69JlNH4g.png" /></figure><pre><strong>Input:</strong> root = [1,2,5,3,4,null,6]<br><strong>Output:</strong> [1,null,2,null,3,null,4,null,5,null,6]</pre><h4>Solution</h4><p>This problem asks to convert a binary tree to a linked list in the ‘pre-order’ traversal. <strong>Pre-order</strong> is a method to traverse a binary tree in this -&gt; left -&gt; right order. In order to convert a binary tree to a linear data structure, let’s break this problem down into several sub-problems:</p><ul><li>Flatten the <strong>left</strong> subtree in the pre-order traversal, marked as flattened_left_subtree;</li><li>Flatten the <strong>right</strong> subtree in the pre-order traversal, marked as flattened_right_subtree;</li><li>Link the root, flattened_left_subtree , flattened_right_subtree together in the pre-order traversal.</li></ul><p>Let’s draw a graph to see how it happens:</p><ul><li>Assume we are given a binary tree looks like:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*agoN11AvE9T4teVO_tnmmQ.png" /></figure><ul><li>Flatten the left and right subtree:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tFvM1lnWrQAX__kyPeGDsA.png" /></figure><ul><li>combine the tree in the end:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qECM1AZDv3PrP_NpNcaIlw.png" /></figure><h4>Code</h4><p>The function we’re going to implement called: def flatten(self, root: TreeNode) -&gt; None . Let’s implement the previous three parts together:</p><ul><li><strong>Step 1:</strong> flatten the <strong>left</strong> subtree: since the function flatten itself is flattening a given tree to a linked list, we can simply pass in the root of the left subtree as an argument, flatten(root.left) will return the result as we want</li><li><strong>Step 2:</strong> flatten the <strong>right</strong> subtree: similar to the previous step, flatten(root.right) will return the flattened right subtree.</li><li><strong>Step 3:</strong> link the three individual parts together: 1). set the root.left to None 2). find the <strong>tail</strong> of flattened_left_subtree , and let tail.right points to the <strong>head</strong> of flattened_right_subtree 3).let root.right points to the <strong>head</strong> of flattened_left_subtree .</li></ul><pre>class TreeNode:<br>    def __init__(self, val=0, left=None, right=None):<br>        self.val = val<br>        self.left = left<br>        self.right = right</pre><pre>    def flatten(self, root: TreeNode) -&gt; None:<br>        &quot;&quot;&quot;<br>        Do not return anything, modify root in-place instead.<br>        &quot;&quot;&quot;<br>        if not root:<br>            return None <br>        self.flatten(root.left)<br>        self.flatten(root.right)<br>        <br>        if root.left:<br>            right = root.right <br>            root.right = root.left <br>            root.left = None <br>            last = root<br>            while last.right:<br>                last = last.right <br>            last.right = right</pre><p>Thanks for reading!</p><h4><strong>Reference</strong></h4><p><a href="https://leetcode.com/problems/flatten-binary-tree-to-linked-list/">Flatten Binary Tree to Linked List - LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=565c4353bd91" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Merge Sort a linked list]]></title>
            <link>https://wangyy395.medium.com/merge-sort-a-linked-list-701a5e9d257b?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/701a5e9d257b</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Thu, 04 Mar 2021 20:56:03 GMT</pubDate>
            <atom:updated>2021-03-04T20:56:03.002Z</atom:updated>
            <content:encoded><![CDATA[<p>Sorting algorithms are frequently asked during a technical interview. Several common sorting algorithms such as quicksort, selection sort, merge sort are usually applied to sorting a list. However, sorting a linked list is not straightforward: it’s not easy to access an element by index in constant running time. Most of the sorting algorithms ask for extra space and the running time is relatively large. Today, I’ll talk about how to apply the merge sort algorithm to a linked list, the running time is O(n*log(n)), and it happens in-place.</p><h4>What is Merge Sort?</h4><p>Merge sort is a divide and conquer algorithm that sorts the input list recursively. There are two steps to finish the process:</p><ul><li>Divide the input list into <em>n</em> sub-list, each sub-list has the same size.</li><li>Merge the sub-lists into one big list, and each element in the list is ordered.</li></ul><p>Here’s a picture illustrating the process:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XZ_iJDU_5Spc_zl6FQVMiQ.jpeg" /><figcaption>merge sort process</figcaption></figure><p>As we can see from the picture, there are two key steps to sort a list: 1). divide a list evenly; 2).merge the sub-list in the end. I’ll talk about how to achieve these functions in a linked list.</p><h4>How to divide a linked list into two parts?</h4><p>The most intuitive way is to count the total_size of the linked list, then divide the linked list into two parts, each part has the size of total_size / 2. However, we found it takes O(n) time to run because we must iterate the whole linked list in the beginning. The more efficient way is applying two-pointers approaching. Assume we have two pointers: a fast pointer and a slow pointer. In each step, the fast pointer steps across two nodes, the slow pointer only steps across one node. When the fast node approaches the end of the list, the slow pointer is actually standing at the middle point of the linked list. Let’s prove it together:</p><pre>Assume given list has n nodes, both fast pointer and slow pointer stand at the first node of the list. <br>fast pointer: rate is 2 node/step, take n/2 steps to visit all nodes;<br>slow pointer: rate is 1 node/step, take n steps to visit all nodes. </pre><pre>At the n/2 steps: fast pointer stands at the last node of the list, slow pointer now at n/2 steps * 1 node/step = n/2 node. Is exactly the middle node of the size n linked list.</pre><h4>How to merge two linked lists in ascending order?</h4><p>Assume we have two sorted linked lists, we want to merge them as a big sorted list. We can have two pointers to indicate the node we’re currently comparing, and append the smaller node into the new node. Let’s see how it works:</p><pre>l1: 1 -&gt; 3 -&gt; 5<br>l2: 2 -&gt; 4 -&gt; 6</pre><pre>We start from the first node from the list, i&#39;ll mark the current compareing nodes <strong>bold</strong>. </pre><pre>l1: <strong>1</strong> -&gt; 3 -&gt; 5<br>l2: <strong>2</strong> -&gt; 4 -&gt; 6<br>reslt: 1 -&gt; <br>Comparision: 1 &lt; 2, append 1 to the result, move the pointer to its next </pre><pre>l1: 1 -&gt; <strong>3</strong> -&gt; 5<br>l2: <strong>2</strong> -&gt; 4 -&gt; 6<br>reslt: 1 -&gt; 2 -&gt; <br>Comparision: 2 &lt; 3, append 2 to the result, move the pointer to its next</pre><pre>l1: 1 -&gt; <strong>3</strong> -&gt; 5 <br>l2: 2 -&gt; <strong>4</strong> -&gt; 6<br>reslt: 1 -&gt; 2 -&gt; 3<br>Comparision: 3 &lt; 4, append 3 to the result, move the pointer to its next</pre><pre>l1: 1 -&gt; 3 -&gt; <strong>5</strong> <br>l2: 2 -&gt; <strong>4</strong> -&gt; 6<br>reslt: 1 -&gt; 2 -&gt; 3 -&gt; 4<br>Comparision: 4 &lt; 5, append 4 to the result, move the pointer to its next</pre><pre>l1: 1 -&gt; 3 -&gt; <strong>5</strong> <br>l2: 2 -&gt; 4 -&gt; <strong>6</strong><br>reslt: 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5<br>Comparision: 5 &lt; 6, append 5 to the result, since l1’s pointer meets the end, we simply append all the following nodes after l2’s pointer to the result: 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 6</pre><h4>Merge sort a linked list</h4><p>Now it’s time to build the whole solution with previous key functions. Remember it’s a divide and conquer algorithm, recursion may happen in many places!</p><pre>class ListNode:<br>    def __init__(self, val=0, next=None):<br>        self.val = val<br>        self.next = next</pre><pre>    #main function <br><strong>    def sortList(self, head: ListNode) -&gt; ListNode:</strong><br>        if not head or not head.next:<br>            return head <br>        <br>        second = self.break_half(head)<br>        sorted_first = self.sortList(head)<br>        sorted_second = self.sortList(second)<br>        <br>        return self.merge(sorted_first, sorted_second)<br>    <br>    #will divide the list into two parts evenly, and return the head     of the second half   <br><strong>    def break_half(self, head):</strong><br>        if not head or not head.next:<br>            return head</pre><pre>        slow, fast = head, head.next <br>        while fast and fast.next:<br>            fast = fast.next.next <br>            slow = slow.next <br>        <br>        mid = slow.next<br>        slow.next = None <br>        <br>        return mid</pre><pre>    #merge two list into a big ordered list<br><strong>    def merge(self, l1, l2):</strong><br>        if not l1 and not l2:<br>            return None <br>        <br>        if not l1:<br>            return l2 <br>        <br>        if not l2:<br>            return l1 <br>        <br>        new_head = None <br>        <br>        if l1.val &lt; l2.val:<br>            new_head = l1 <br>            new_head.next = self.merge(l1.next, l2)<br>        else:<br>            new_head = l2<br>            new_head.next = self.merge(l1, l2.next)<br>        <br>        return new_head</pre><h4>Analyze:</h4><ul><li>Time Complexity: O(nlogn), where n is the number of nodes in the linked list.</li><li>Space Complexity: O(nlogn), where n is the number of nodes in the linked list. Since the problem is recursive, we need additional space to store the recursive call stack. The maximum depth of the recursion tree is O(nlogn) .</li></ul><h4><strong>Reference</strong></h4><ul><li><a href="https://en.wikipedia.org/wiki/Merge_sort">Merge sort - Wikipedia</a></li><li><a href="https://leetcode.com/problems/sort-list/">Sort List - LeetCode</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=701a5e9d257b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implement a doubly linked list with Python]]></title>
            <link>https://wangyy395.medium.com/implement-a-doubly-linked-list-with-python-f484f56c8a1a?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/f484f56c8a1a</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Sat, 27 Feb 2021 21:46:11 GMT</pubDate>
            <atom:updated>2021-02-27T21:46:11.727Z</atom:updated>
            <content:encoded><![CDATA[<h4><strong>Introduction</strong></h4><p>A singly linked list is a set of linked nodes. Different from a singly linked list, each node in a doubly linked list has an extra pointer points to its previous node. Today, I’ll talk about the implementation of a doubly linked list in python.</p><h4>Implementation in Python</h4><ul><li>Node class</li></ul><p>A doubly linked list is composed of a set of nodes. A node has two pointers and a value. One pointer points to its previous node, another pointer points to its next node.</p><pre>class Node:</pre><pre>    def __init__(self, val):<br>        self.val = val<br>        self.next = None<br>        self.prev = None<br></pre><ul><li>Doubly linked list class</li></ul><p>Besides the nodes, we also need two variables to specify the start and end of a linked list. We usually have two nodes to represent the head and tail of the doubly linked list.</p><pre>class DoublyLinkedList:<br>    def __init__(self):<br>        self.head = Node(float(&#39;inf&#39;)<br>        self.tail = Node(float(&#39;inf&#39;)<br>        self.head.next = self.tail<br>        self.tail.prev = self.head</pre><ul><li>Implement methods</li></ul><p>The basic functions of a doubly linked list are: insert, remove. Both functions are arranging a node. We can apply them to the Node class.</p><pre>class Node:</pre><pre>    def __init__(self, val):<br>        self.val = val<br>        self.next = None<br>        self.prev = None</pre><pre>    def insert_after(self, node):<br>        next_node = self.next<br>        self.next = node<br>        node.prev = self<br>        node.next = next_node <br>        next_node.prev = node</pre><pre>    def remove(self):<br>        self.next.prev = self.prev<br>        self.prev.next = self.next<br>        self.next, self.prev = None, None</pre><p>Combine two classes together:</p><pre>class Node:</pre><pre>    def __init__(self, val):<br>        self.val = val<br>        self.next = None<br>        self.prev = None</pre><pre>    def insert_after(self, node):<br>        next_node = self.next<br>        self.next = node<br>        node.prev = self<br>        node.next = next_node <br>        next_node.prev = node</pre><pre>    def remove(self):<br>        self.next.prev = self.prev<br>        self.prev.next = self.next<br>        self.next, self.prev = None, None<br></pre><pre>class DoublyLinkedList:</pre><pre>    def __init__(self):<br>        self.head = Node(float(&#39;inf&#39;)<br>        self.tail = Node(float(&#39;inf&#39;)<br>        self.head.next = self.tail<br>        self.tail.prev = self.head<br>        //to map the val with the node<br>        self.mapping = {}  </pre><h4>Analyze</h4><p>A doubly linked list performs well in inserting and deleting a node. Both functions only take O(1) running time. For the space complexity, it takes O(n), n is the length of the list since we create an extra dictionary to record the node position of the list.</p><p>Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f484f56c8a1a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Max area of the island: dfs and bfs approach]]></title>
            <link>https://wangyy395.medium.com/max-area-of-the-island-dfs-and-bfs-approach-33a25c1da894?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/33a25c1da894</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Fri, 19 Feb 2021 22:29:03 GMT</pubDate>
            <atom:updated>2021-02-19T22:29:03.574Z</atom:updated>
            <content:encoded><![CDATA[<p>For the given island that’s represented in a matrix of 0&#39;s and 1&#39;s, we usually use a depth-first search or a breadth-first search algorithm to solve. Today, I’ll introduce how to solve and compare such a problem using both approaches.</p><h4>Problem</h4><blockquote>Given a non-empty 2D array grid of 0&#39;s and 1&#39;s, an <strong>island</strong> is a group of 1&#39;s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.</blockquote><blockquote>Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)</blockquote><p><strong>Example:</strong></p><pre>[[0,0,1,0,0,0,0,1,0,0,0,0,0],<br> [0,0,0,0,0,0,0,1,1,1,0,0,0],<br> [0,1,1,0,1,0,0,0,0,0,0,0,0],<br> [0,1,0,0,1,1,0,0,<strong>1</strong>,0,<strong>1</strong>,0,0],<br> [0,1,0,0,1,1,0,0,<strong>1</strong>,<strong>1</strong>,<strong>1</strong>,0,0],<br> [0,0,0,0,0,0,0,0,0,0,<strong>1</strong>,0,0],<br> [0,0,0,0,0,0,0,1,1,1,0,0,0],<br> [0,0,0,0,0,0,0,1,1,0,0,0,0]]</pre><p>Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.</p><p>Try to solve it yourself: <a href="https://leetcode.com/problems/max-area-of-island/">https://leetcode.com/problems/max-area-of-island/</a></p><h4>DFS</h4><p>While iterating the cell, we want to calculate the current island area that it could form. To do this, we can utilize the depth-first-search algorithm here. We’ll create a helper function, the input is the current position, the output is the area of adjacent islands. Here’s the process of executing:</p><ul><li>While iterating the grid, we pass the position of each cell to the helper function to get the island area;</li><li>Inside the helper function, we need to consider several edge cases: 1) if the given position is out of range, we simple return 0; 2) if the given cell is water, we return 0 due to no island exist in the current cell</li><li>To avoid circular search, we’ll use a set to record the visited islands</li></ul><p><strong>Code:</strong></p><pre>class Solution:<br>    def maxAreaOfIsland(self, grid: List[List[int]]) -&gt; int:<br>        seen = set()<br>        def area(r, c):<br>            if not (0 &lt;= r &lt; len(grid) and 0 &lt;= c &lt; len(grid[0])<br>                    and (r, c) not in seen and grid[r][c]):<br>                return 0<br>            seen.add((r,c))<br>            return (1 + area(r+1, c) + area(r-1, c) +<br>                    area(r, c-1) + area(r, c+1))<br>        <br>        return max(area(r,c) for r in range(len(grid)) for c in range(len(grid[0])))</pre><p><strong>Analysis:</strong></p><ul><li>Time Complexity: O(m*n), m is the number of rows and n is the number of the column in the given grid. There’re m*n cells in the given grid. Since we visited all cells, so the running time is O(m*n).</li><li>Space complexity: O(m*n) , we introduce a set to record the visited cell. And memory is created during the recursion calls. The total space used is O(m*n) .</li></ul><h4>BFS</h4><p>Unlike the dfs approach using a stack in recursion calls, the bfs approach usually utilizes a queue in the iteration. Here are the steps in bfs implementation:</p><ul><li>While iterating the grid, we check if the current cell is an island;</li><li>If the cell is an island, we use a queue to record its adjacent island cells. If its adjacent cells are islands, we append the cell to the queue waiting for the next round’s checking.</li><li>To avoid circular search, we’ll use a set to record the visited islands</li></ul><p><strong>Code:</strong></p><pre>class Solution:<br>    def maxAreaOfIsland(self, grid: List[List[int]]) -&gt; int:<br>        rows, cols = len(grid), len(grid[0])<br>        seen = set()<br>        row_dir = [0,0,1,-1]<br>        col_dir = [1,-1,0,0]<br>        res = 0 <br>        <br>        for i in range(rows):<br>            for j in range(cols):<br>                if (i, j) not in seen and grid[i][j] == 1:<br>                    queue = [[i, j]]<br>                    area = 0</pre><pre>while queue:  <br>                        curr = queue.pop(0)<br>                        seen.add((curr[0], curr[1]))<br>                        area += 1<br>                        for k in range(4):<br>                            nr = curr[0] + row_dir[k]<br>                            nc = curr[1] + col_dir[k]</pre><pre>if nr &gt;= 0 and nr &lt; rows and nc &gt;= 0 and nc &lt; cols and grid[nr][nc] == 1 and (nr, nc) not in seen:<br>                                queue.append([nr, nc])<br>                                seen.add((nr, nc))</pre><pre>res = max(res, area)<br>        <br>        return res</pre><p><strong>Analysis:</strong></p><ul><li>Time Complexity: O(m*n), m is the number of rows and n is the number of the column in the given grid. There’re m*n cells in the given grid. Since we visited all cells, so the running time is O(m*n).</li><li>Space complexity: O(m*n) , we introduce a set to record the visited cell. And a queue is created in calculating the area. The total space used is O(m*n) .</li></ul><p>Which solution do you prefer?</p><h4>Reference</h4><p><a href="https://leetcode.com/problems/max-area-of-island/">Max Area of Island - LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=33a25c1da894" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solve the sliding window maximum problem]]></title>
            <link>https://wangyy395.medium.com/solve-the-sliding-window-maximum-problem-f04fccb64963?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/f04fccb64963</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Fri, 12 Feb 2021 20:29:44 GMT</pubDate>
            <atom:updated>2021-02-12T20:29:44.424Z</atom:updated>
            <content:encoded><![CDATA[<p>The sliding window algorithm is often used to find the target number in a string/list. Today, I’ll introduce how to solve this leetcode problem using the sliding window algorithm and optimize its running time.</p><h4>Problem description</h4><blockquote>You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return <em>the max sliding window</em>.</blockquote><p><strong>Example 1:</strong></p><pre><strong>Input:</strong> nums = [1,3,-1,-3,5,3,6,7], k = 3<br><strong>Output:</strong> [3,3,5,5,6,7]<br><strong>Explanation:</strong> <br>Window position                Max<br>---------------               -----<br>[1  3  -1] -3  5  3  6  7       <strong>3</strong><br> 1 [3  -1  -3] 5  3  6  7       <strong>3</strong><br> 1  3 [-1  -3  5] 3  6  7      <strong> 5</strong><br> 1  3  -1 [-3  5  3] 6  7       <strong>5</strong><br> 1  3  -1  -3 [5  3  6] 7       <strong>6</strong><br> 1  3  -1  -3  5 [3  6  7]      <strong>7</strong></pre><p>You can solve it online here: <a href="https://leetcode.com/problems/sliding-window-maximum/">leetcode 239</a>.</p><h4>Solve it using the sliding window algorithm</h4><p>The intuitive solution is to find the maximum number in each sliding window. As the previous example shows, each sliding window could be marked by two pointers: left and right boundary. Steps to solve this problem are:</p><ul><li>Create an initial sliding window from index 0. And the right pointer is the k number away from the left pointer. Calculate the current maximum number inside the window and append it to the result list.</li><li>We move the sliding window from index 1. Each iteration will move the left and right pointer to its left to create a new sliding window.</li><li>For each newly created sliding window, find the maximum number inside and record it in the result list.</li></ul><p><strong>Code:</strong></p><pre>class Solution:<br>    def maxSlidingWindow(self, nums: List[int], k: int) -&gt; List[int]:<br>        window = []<br>        result = []<br>        right = k<br>        <br>        for i in range(k):<br>            window.append(nums[i])<br>            <br>        while right &lt; len(nums):<br>            result.append(max(window))<br>            window.pop(0)<br>            window.append(nums[right])<br>            right += 1  <br>        result.append(max(window))<br>        return result</pre><p><strong>Analysis</strong></p><ul><li>Time complexity: O(k*n). There are total n-k+1 sliding windows for n size list. And each sliding window will take k time to find the maximum number inside it.</li><li>Space complexity: O(k). We create a sliding window list with size k to record the current window.</li></ul><h4>Optimize it with a deque</h4><p>O(k*n) is too time-consuming. Can we solve it in linear time? The answer is yes, by introducing a deque.</p><p>Deque is a data structure that’s similar to a list. The difference is that it takes constant time to remove/append an element to the front/end of the deque. For this problem, we can introduce a deque to help to find the maximum number in each sliding window. The deque is storing the numbers that could be the maximum number in each sliding window.</p><p>Let’s how to improve it with an example: nums = [1,3,-1,-3,5,3,6,7], k = 3 .</p><pre><strong>Step1: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 0, nums[i] = 1, deque = []<br>When deque is empty, nums[i] is a candidate, append i to the deque. Now deque = [0]</pre><pre><strong>Step2: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 1, nums[i] = 3, deque = [0]<br>The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [1]</pre><pre><strong>Step3: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 2, nums[i] = -1, deque = [1]<br>The current number is less than the last element in the deque. Meaning the current number is candidate for the next sliding window. We append the current index to the deque. Now deque = [1, 2]. And we&#39;ve done seeing the frist sliding window, we push the first element to the result. result = [3]</pre><pre><strong>Step4: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 3, nums[i] = -3, deque = [1,2]<br>The current number is less than the last element in the deque. Meaning the current number is candidate for the next sliding window. We append the current index to the deque. Now deque = [1,2,3]. For second sliding window, the maximum number is nums[deque[0]]. We append it to the result. result = [3,3]</pre><pre><strong>Step5: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 4, nums[i] = 5, deque = [1,2,3]<br>The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [4]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5]</pre><pre><strong>Step6: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 5, nums[i] = 3, deque = [4]<br>The current number is less than the last element in the deque. Meaning the current number is candidate for the next sliding window. We append the current index to the deque. Now deque = [4,5]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5,5]</pre><pre><strong>Step7: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 6, nums[i] = 6, deque = [4,5]<br>The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [6]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5,5,6]</pre><pre><strong>Step8: </strong><br>nums = [1,3,-1,-3,5,3,6,7], i = 7, nums[i] = 7, deque = [6]<br>The current number nums[i] is greater than the last element in the deque, the current number is a new candidate, we pop the last element from the deque until the deque is empty or the last element in the deque is greater than the current number. Now deque = [7]. Append nums[deque[0]] as the maximum number in current sliding window, result = [3,3,5,5,6,7]</pre><p><strong>Code:</strong></p><pre>class Solution:<br>    def maxSlidingWindow(self, nums: List[int], k: int) -&gt; List[int]:<br>        result = []<br>        arr = []<br>        <br>        for index, num in enumerate(nums):<br>            while arr and nums[arr[-1]] &gt; num:<br>                arr.pop()<br>                <br>            arr.append(index)<br>            if arr[0] == index - k:<br>                arr.pop(0)<br>                <br>            if index &gt;= k-1:<br>                result.append(nums[arr[0]])<br>                <br>        return result</pre><p><strong>Analysis</strong></p><ul><li>Time complexity: O(n). We iterate the given list once to find the result.</li><li>Space complexity: O(k). In the worst-case scenario, the size of the deque is k.</li></ul><h4>Reference</h4><p><a href="https://leetcode.com/problems/sliding-window-maximum/">Sliding Window Maximum - LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f04fccb64963" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implement a Trie in Python]]></title>
            <link>https://wangyy395.medium.com/implement-a-trie-in-python-e8dd5c5fde3a?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/e8dd5c5fde3a</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Fri, 05 Feb 2021 22:25:26 GMT</pubDate>
            <atom:updated>2021-02-05T22:25:26.779Z</atom:updated>
            <content:encoded><![CDATA[<p>We know tree well, a binary search tree performs well in searching. Today, I’ll introduce another tree-like data structure, which is widely used for retrieval of a key in a dataset of strings: trie.</p><h4>Introduction</h4><p>A trie also called prefix-tree, is a type of <a href="https://en.wikipedia.org/wiki/Search_tree">search tree</a>, a <a href="https://en.wikipedia.org/wiki/Tree_(data_structure)">tree</a> <a href="https://en.wikipedia.org/wiki/Data_structure">data structure</a> used for locating specific keys from within a set. These keys are always strings and characters. A trie is structured by trie nodes. Each trie node has two components: a set of children that leads to the next trie node, and a boolean value defines if it is the end for the word.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/683/0*fyC68Zd3w8pUDphM.png" /><figcaption>credit to <a href="https://java2blog.com/trie-data-structure-in-java/">Java2Blog</a></figcaption></figure><p>A trie has many applications such as:</p><ul><li><strong>Autocomplete</strong>: when googling something, it will automatically predict the rest of a word a user is typing. Basically, it’s searching the prefix in a trie and provides the following words as options.</li><li><strong>Spell checker</strong>: it checks if the user’s typing by searching the word in a trie(dictionary).</li><li><strong>Solving Boggle games</strong>: starts with a random character in the given matrix, check whether it is a prefix in a trie(dictionary).</li></ul><h4>Basic functions of a trie</h4><p>The basic functions of a trie include: insert, search a word, and search a prefix:</p><ul><li><strong>Insert a word into a trie</strong></li></ul><p>Insert every letter of the word into a trie. The process is 1). start from the root to check if the current letter node exists; 2) if the letter node exists, move one level down to the next letter; 3) if the letter does not exist, create a new node; 4) repeat the previous steps until we met the end of the word, and mark the last node’s boolean True.</p><ul><li><strong>Search if a word exists in a trie</strong></li></ul><p>We start from the root with the first letter, examine if the letter exists in its children set. There are two cases: 1). if a letter can’t be found in a trie, simple return False; 2). if all letters in a word can be found in a trie and they all linked, check the last letter’s boolean value, if it’s not the end of the word, return False, otherwise return True.</p><ul><li><strong>Check if a prefix exists in a trie</strong></li></ul><p>Similar to the searching function. In this case, we don’t need to check the last letter node’s boolean value.</p><h4>Implementation</h4><p>There’re two ways of implementation. The trie structures are the same, the only difference is the representation of the trie node’s children.</p><ul><li><strong>Trie node’s children is an array</strong></li></ul><p>For every trie node in a tree, its children is a form of an array with size 26. Index 0 is representing ‘a’, and index 25 is representing ‘z’. When inserting a new letter, we’ll first calculate its index, then create a new trie node at children[index].</p><p>Code:</p><pre>class TrieNode:<br>    def __init__(self):<br>        self.children = [None] * 26<br>        self.isLeaf = False</pre><pre>class Trie:</pre><pre>    def __init__(self):<br>        &quot;&quot;&quot;<br>        Initialize your data structure here.<br>        &quot;&quot;&quot;<br>        self.root = TrieNode()</pre><pre>    def insert(self, word: str) -&gt; None:<br>        &quot;&quot;&quot;<br>        Inserts a word into the trie.<br>        &quot;&quot;&quot;<br>        current = self.root <br>        for letter in word:<br>            index = ord(letter) - ord(&#39;a&#39;)<br>            if not current.children[index]:<br>                current.children[index] = TrieNode()<br>            current = current.children[index]<br>        current.isLeaf = True</pre><pre>    def search(self, word: str) -&gt; bool:<br>        &quot;&quot;&quot;<br>        Returns if the word is in the trie.<br>        &quot;&quot;&quot;<br>        current = self.root <br>        for letter in word:<br>            index = ord(letter) - ord(&#39;a&#39;)<br>            if not current.children[index]:<br>                return False <br>            current = current.children[index]<br>        return current.isLeaf and current</pre><pre>    def startsWith(self, prefix: str) -&gt; bool:<br>        &quot;&quot;&quot;<br>        Returns if there is any word in the trie that starts with the given prefix.<br>        &quot;&quot;&quot;<br>        current = self.root <br>        for letter in prefix:<br>            index = ord(letter) - ord(&#39;a&#39;)<br>            if not current.children[index]:<br>                return False<br>            current = current.children[index]<br>        return True</pre><ul><li>Trie node’s children is a dictionary</li></ul><p>Each trie node’s children set is represented by a dictionary. When inserting a new word into a trie, the letter is the key of the node’s children dictionary, the value is the next letter’s node.</p><p>Compare with array approach, it saves some spaces due to the size of trie node children is not fixed to 26.</p><p>Code:</p><pre>class TrieNode:<br>    def __init__(self):<br>        self.children = collections.defaultdict(TrieNode)<br>        self.is_end = False</pre><pre>class Trie:</pre><pre>    def __init__(self):<br>        &quot;&quot;&quot;<br>        Initialize your data structure here.<br>        &quot;&quot;&quot;<br>        self.root = TrieNode()</pre><pre>    def insert(self, word: str) -&gt; None:<br>        &quot;&quot;&quot;<br>        Inserts a word into the trie.<br>        &quot;&quot;&quot;<br>        current = self.root<br>        for letter in word:<br>            current = current.children[letter]<br>        current.is_end = True</pre><pre>    def search(self, word: str) -&gt; bool:<br>        &quot;&quot;&quot;<br>        Returns if the word is in the trie.<br>        &quot;&quot;&quot;<br>        current = self.root<br>        for letter in word:<br>            current = current.children.get(letter)<br>            if current is None:<br>                return False<br>        return current.is_end</pre><pre>    def startsWith(self, prefix: str) -&gt; bool:<br>        &quot;&quot;&quot;<br>        Returns if there is any word in the trie that starts with the given prefix.<br>        &quot;&quot;&quot;<br>        current = self.root <br>        <br>        for letter in prefix:<br>            current = current.children.get(letter)<br>            if not current:<br>                return False<br>        <br>        return True</pre><h4>Reference</h4><ul><li><a href="https://en.wikipedia.org/wiki/Trie#Applications">Trie</a></li><li><a href="https://leetcode.com/problems/implement-trie-prefix-tree/">Implement Trie (Prefix Tree) - LeetCode</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e8dd5c5fde3a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Crack the house robber problem]]></title>
            <link>https://wangyy395.medium.com/crack-the-house-robber-problem-5400d3cec053?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/5400d3cec053</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Sat, 30 Jan 2021 23:39:24 GMT</pubDate>
            <atom:updated>2021-01-30T23:39:24.155Z</atom:updated>
            <content:encoded><![CDATA[<p>My previous post introduced the <strong>Knapsack</strong> problem. It states how to solve using the dynamic programming algorithm. Besides <strong>Knapsack</strong>, there’s one series of problems that you might encounter in a coding interview: the house robber problems. Today, let’s talk about it.</p><h4><strong>Problem description</strong></h4><blockquote><em>You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and </em><strong><em>it will automatically contact the police if two adjacent houses were broken into on the same night</em></strong><em>.</em></blockquote><blockquote><em>Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight </em><strong><em>without alerting the police</em></strong><em>.</em></blockquote><p><strong>Examples:</strong></p><pre><strong>Case 1:</strong> <br><strong>Input:</strong> nums = [1,2,3,1]<br><strong>Output:</strong> 4<br><strong>Explanation:</strong> Rob house 1 (money = 1) and then rob house 3 (money = 3).<br>             Total amount you can rob = 1 + 3 = 4.</pre><pre><strong>Case 2: </strong><br><strong>Input:</strong> nums = [2,7,9,3,1]<br><strong>Output:</strong> 12<br><strong>Explanation:</strong> Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).<br>             Total amount you can rob = 2 + 9 + 1 = 12.</pre><p>From the description and examples, we know the robber has to find out the maximum profit for the given houses without stealing two adjacent houses. How to solve it?</p><h4>Solution</h4><p>It seems complicated at the first glance. In fact, if we break it into subproblems, there are only two scenarios to consider: at the current house, will the robber rob it? There are two cases to consider:</p><ul><li>At house i, if the robber robs it, meaning that the robber didn’t rob the previous house i-1, the maximum profit could be profit at the house i-2 plus current house valuei</li><li>At house i, if the robber doesn’t rob it, meaning that the previous house i-1 could be robbed, the maximum profit might happen at the house i-1</li></ul><p>As the result, at house i, the maximum profit is determined by its previous houses: profit[i] = max(profit[i-2]+house[i], profit[i-1]) . To compare these two values, the best way is to create an array to store the profit.</p><p>Let’s take one example to walk through the process:</p><pre><strong>Input:</strong> nums = [2,7,9,3,1]</pre><pre><strong>Step 1: </strong><br>Let&#39;s create an array to store the maximum proit the robber robbed. Let&#39;s set initial profits all to 0: profit = [0,0,0,0,0,0]. Note that we increate the profit size by 1, it means when i = 0, the profit is zero due to the <strong>None</strong> house value. </pre><pre><strong>Step 2:<br></strong>Initial state is that when i = 0, profit[0] = 0. When i = 1, profit[1] = nums[0] = 2 because it&#39;s the maximum profit if we only go over one house. Now profit<strong> </strong>=<strong> </strong>[0,2,0,0,0,0]</pre><pre><strong>Step 3:<br></strong>Start with index = 2, let&#39;s find the maximum profit while iterating the houses.</pre><pre>When i = 2, current house value is 7, consider two cases here:<br>    <strong>* rob it: profit[2] = profit[2-2] + 7 = 7</strong><br>    * not rob it: profit[2] = profit[2-1] = 2 <br>Obviously, 7 is bigger, profit<strong> </strong>=<strong> </strong>[0,2,7,0,0,0]</pre><pre><strong>Step 4:<br></strong>Move to index = 3, current house value is 9, consider two cases here:<br>    <strong>* rob it: profit[3] = profit[3-2] + 9 = 11</strong><br>    * not rob it: profit[3] = profit[3-1] = 7<br>Obviously, 11 is bigger, profit<strong> </strong>=<strong> </strong>[0,2,7,11,0,0]</pre><pre><strong>Step 5:<br></strong>Move to index = 4, current house value is 3, consider two cases here:<br>    * rob it: profit[4] = profit[4-2] + 3= 10<br>    <strong>* not rob it: profit[4] = profit[4-1] = 11</strong><br>Obviously, 11 is bigger, profit<strong> </strong>=<strong> </strong>[0,2,7,11,11,0]</pre><pre><strong>Step 5:<br></strong>Move to the last house index = 5, current house value is 1, consider two cases here:<br>    <strong>* rob it: profit[5] = profit[5-2] + 1 = 12</strong><br>    * not rob it: profit[5] = profit[5-1] = 11<br>Obviously, 12 is bigger, profit<strong> </strong>=<strong> </strong>[0,2,7,11,11,12]</pre><pre><strong>Step 6:<br></strong>Now, we&#39;ve seen all given houses: profit<strong> </strong>=<strong> </strong>[0,2,7,11,11,12]. The maximum profit is 12. </pre><p><strong>Code:</strong></p><pre>    <strong>def rob(nums):</strong><br>        if not nums or len(nums) == 0:<br>            return 0<br>        <br>        res = nums[0]<br>        profit = [0] * (len(nums) + 1)<br>        profit[1] = nums[0]<br>        <br>        <br>        for i in range(2, len(profit)):<br>            profit[i] = max(nums[i-1] + profit[i-2], profit[i-1])<br>            res = max(res, profit[i])<br>  <br>        return res</pre><p><strong>Analysis:</strong></p><p>Let n be the number of the given houses:</p><ul><li>Time complexity: O(n) since we iterate the nums once, and saved the result at an array.</li><li>Space complexity: O(n) since we create an extra array with size n+1 to help to find the maximum profit.</li></ul><h4>House Robber II</h4><p>There’s a more challenging version of the house robber problem:</p><p><strong>Description:</strong></p><blockquote><em>You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are </em><strong><em>arranged in a circle.</em></strong><em> That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and </em><strong><em>it will automatically contact the police if two adjacent houses were broken into on the same night</em></strong><em>.</em></blockquote><blockquote><em>Given a list of non-negative integers </em><em>nums representing the amount of money of each house, return the maximum amount of money you can rob tonight </em><strong><em>without alerting the police</em></strong><em>.</em></blockquote><p><strong>Examples:</strong></p><pre><strong>Case 1:<br>Input:</strong> nums = [2,3,2]<br><strong>Output:</strong> 3<br><strong>Explanation:</strong> You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.</pre><pre><strong>Case 2:<br>Input:</strong> nums = [1,2,3,1]<br><strong>Output:</strong> 4<br><strong>Explanation:</strong> Rob house 1 (money = 1) and then rob house 3 (money = 3).<br>Total amount you can rob = 1 + 3 = 4.</pre><p><strong>Solution</strong></p><p>When the houses are circular, it’s different from the previous problem because the first house and last house can’t be robbed at the same time. How to solve it?</p><p>In fact, we can divide it into two subproblems:</p><ul><li>Don’t rob the <strong>first</strong> house, what’s the maximum profit robbed?</li><li>Don’t rob the <strong>last</strong> house, what’s the maximum profit robbed?</li></ul><p>Each subproblem could be solved using the previous algorithm. The only part that needs to change is that for the <strong>don’t rob front case: profit[1] = 0</strong>. To record the maximum profit of two different cases, we’ll create two different arrays: notRobFront, and notRobTail . After iterating the houses, we’ll compare two arrays to find the maximum profit.</p><p><strong>Code:</strong></p><pre>    <strong>def rob(nums):</strong><br>        size = len(nums)</pre><pre>        notRobFront = [0] * (size + 1)<br>        notRobTail = [0] * (size + 1)</pre><pre>        notRobFront[1] = 0<br>        notRobTail[1] = nums[0]</pre><pre>        for i in range(2, size):<br>            notRobFront[i] = max(notRobFront[i-1], notRobFront[i-2]+nums[i-1])<br>            notRobTail[i] = max(notRobTail[i-1], notRobTail[i-2]+nums[i-1])</pre><pre>        notRobFront[-1] = max(notRobFront[size-1], notRobFront[size-2] + nums[-1])</pre><pre>        return max(notRobFront[-1], notRobTail[-2])</pre><p><strong>Analysis:</strong></p><p>Let n be the number of the given houses:</p><ul><li>Time complexity: O(n) since we iterate the nums once, and saved the result at an array.</li><li>Space complexity: O(2n) ≈ O(n) since we create two extra arrays with size n+1 to help to find the maximum profit.</li></ul><p>Thanks for reading!</p><h4>Reference</h4><ul><li><a href="https://leetcode.com/problems/house-robber/">House Robber - LeetCode</a></li><li><a href="https://leetcode.com/problems/house-robber-ii/">House Robber II - LeetCode</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5400d3cec053" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Intro to dynamic programming knapsack problems]]></title>
            <link>https://wangyy395.medium.com/intro-to-dynamic-programming-knapsack-problems-dc5d71f664f3?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/dc5d71f664f3</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Sun, 24 Jan 2021 22:57:52 GMT</pubDate>
            <atom:updated>2021-01-24T22:57:52.004Z</atom:updated>
            <content:encoded><![CDATA[<p>Dynamic programming problems are frequently asked in a tech interview. For me, dynamic programming problems are challenging to understand and to solve. Recently, I see a <a href="https://leetcode.com/problems/target-sum/discuss/455024/DP-IS-EASY!-5-Steps-to-Think-Through-DP-Questions.">post</a> demonstrating that dynamic programming problems can be categorized. One of the categories is the <strong>Knapsack</strong> problem. Today, I&#39;ll introduce what’s knapsack problem and its related topics.</p><h4>Definition</h4><p>The <a href="https://en.wikipedia.org/wiki/Knapsack_problem"><strong>knapsack problem</strong></a> is a problem in <a href="https://en.wikipedia.org/wiki/Combinatorial_optimization">combinatorial optimization</a>: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7qVrrJOuli5A3xwU.png" /><figcaption>This file is licensed under the <a href="https://en.wikipedia.org/wiki/en:Creative_Commons">Creative Commons</a> <a href="https://creativecommons.org/licenses/by-sa/2.5/deed.en">Attribution-Share Alike 2.5 Generic</a> license.</figcaption></figure><p>That’s said if we have items with the following weights and values, what’s the maximum value we can steal with the total weight that doesn’t exceed the maximum weight.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/1*LIr8KaZVYZ_W1whWSbvTjg.png" /></figure><h4>The Brute-Force solution</h4><p>When evaluating the maximum values to get, we need to consider all subsets of the given array. For each subset, we also need to make sure the total weight doesn’t exceed the max weight. The intuitive process would be: start from item 1, two consequences are <strong>a)</strong>take it; <strong>b)</strong>not take it. Followed by item 2, consequences a and b both have another two consequences: <strong>c)</strong>take item 2; <strong>d)</strong>not take item 2. …Until we met the last item in the array. The following graph visualizes this process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ciH9LP6bKFQvTQPbieAIyA.jpeg" /></figure><p>As we can see from the graph, there are 2^n combinations we need to consider, n is the number of items. Among these combinations, we find out that the maximum value we can get is $15. The running time for the brute-force solution is O(2^n). Time complexity is O(1).</p><p>Code:</p><pre>class Solution:</pre><pre>    def knapsack(self, values, weights, maxWeightConstraint):</pre><pre>        self.res = 0</pre><pre>        def backtrack(values, weights, maxWeightConstraint, currWeight, currVal):</pre><pre>            if currWeight &gt; maxWeightConstraint:</pre><pre>                return</pre><pre>            else:</pre><pre>                self.res = max(self.res, currVal)</pre><pre>            for i in range(len(weights)):</pre><pre>                backtrack(values[i+1:], weights[i+1:], maxWeightConstraint, currWeight+weights[i], currVal+values[i])</pre><pre>        backtrack(values, weights, maxWeightConstraint, 0, 0)</pre><pre>        return self.res</pre><h4>Dynamic programming solution</h4><p>Dynamic programming algorithm performs well in reducing the running time by adding extra space to memorize the results of different combinations. How to solve the knapsack problem using this algorithm? Let’s take several steps to think about the process:</p><p><strong>Step 1: break down the problem into multiple subproblems</strong></p><p>To determine the maximum values we can get from the given items and weights, let’s start with a smaller scale. At the weight j,j in range[0,max weight]and item i , what’s the maximum value we can get at the current state?</p><p><strong>Step 2: determine the initial state</strong></p><p>The best data structure to store the maximum value we get for item[i]weight[j] is a 2D matrix. The row number is the (total item count + 1), and the column number is (max weight + 1). The reason we increment the size by 1 is to determine the initial state: when the item is None and the weight is 0, the value we get is 0.</p><p><strong>Step 3: solve the subproblem</strong></p><p>If we’re only given one item and its weight doesn’t exceed the maximum weight, obviously the result is its value. If we gradually increase the size of given items, how to determine the items to pick? For each item, there’re two scenarios: <strong>pick it or not pick it</strong>. The subproblem becomes: if we pick the current item, item[i]weight[j] = item[i-1]weight[j-wi]+vi , if we don’t pick the current item, item[i]weight[j] = item[i-1]weight[j] . We need to find the maximum value among these two, as the result, item[i]weight[j] = max(item[i-1]weight[j-wi]+vi, item[i-1]weight[j]) .</p><p>Code:</p><pre>def knapsack(values, weights, maxWeightConstraint):<br>    row, col = len(values)+1, maxWeightConstraint+1<br>    dp = [[0 for _ in range(col)] for _ in range(row)]</pre><pre>    for i in range(1, row):<br>        for j in range(1, col):<br>            if j &gt;= weights[i-1]:<br>                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])</pre><pre>    return dp[row-1][col-1]</pre><p>Compare with the brute force solution, the dynamic programming approach greatly reduces the running time to O(n*m), where n is the size of items, m is the max weight. However, since it introduces a matrix with size(n*m), the space complexity increases to O(m*n).</p><h4>Related topics</h4><p>Many dynamic programming problems can be solved by implementing the knapsack’s algorithm. Here’s the list of similar problems:</p><ul><li><a href="https://leetcode.com/problems/coin-change/">Coin change</a></li><li><a href="https://leetcode.com/problems/coin-change-2/">Coin change 2</a></li><li><a href="https://leetcode.com/problems/partition-equal-subset-sum/">Partition equal subset sum</a></li><li><a href="https://leetcode.com/problems/target-sum/">Target sum</a></li><li><a href="https://leetcode.com/problems/split-array-with-same-average/">Split array with same average</a></li></ul><p>Thanks for reading!</p><h4>Reference</h4><p><a href="https://en.wikipedia.org/wiki/Knapsack_problem">Knapsack problem - Wikipedia</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dc5d71f664f3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Deal with subset, permutation, combination problems using backtracking algorithm]]></title>
            <link>https://wangyy395.medium.com/deal-with-subset-permutation-combination-problems-using-backtracking-algorithm-d50dc8f60f92?source=rss-ca7cde3eb133------2</link>
            <guid isPermaLink="false">https://medium.com/p/d50dc8f60f92</guid>
            <dc:creator><![CDATA[Wangyy]]></dc:creator>
            <pubDate>Sun, 17 Jan 2021 21:50:01 GMT</pubDate>
            <atom:updated>2021-01-17T21:50:01.518Z</atom:updated>
            <content:encoded><![CDATA[<p>It’s often asked during a technical interview: write a function to get the subsets/combinations/permutations for a given set. These problems seem difficult to solve in the first place, but have similarities when applying the backtracking algorithm. In this post, I’ll illustrate how to solve these problems using the backtracking algorithm.</p><h4>Definitions</h4><p>Assume we are given a set A, and it contains several elements. For example, A = [1, 2, 3].</p><ul><li><strong>Subset:</strong><a href="https://en.wikipedia.org/wiki/Subset"><strong> </strong>In definition, a set B is a subset of set A if all elements of B are also elements of A</a>. Note that the <strong>empty set</strong> is a subset of any set. Set A has <strong>8 subsets</strong>: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]].</li><li><strong>Combination</strong>: is a selection of the original set. The combination is the same with subset. Except that we usually select combinations for a specific purpose. For example, if we wanna get combinations of set A that add up to the number 4, the only combination we find is [1, 3].</li><li><strong>Permutation: </strong>In <a href="https://en.wikipedia.org/wiki/Mathematics">mathematics</a>, a <a href="https://en.wikipedia.org/wiki/Permutation"><strong>permutation</strong></a> of a <a href="https://en.wikipedia.org/wiki/Set_(mathematics)">set</a> is, loosely speaking, an arrangement of its members into a <a href="https://en.wikipedia.org/wiki/Sequence">sequence</a> or <a href="https://en.wikipedia.org/wiki/Linear_order">linear order</a>, or if the set is already ordered, a rearrangement of its elements. The biggest difference between subset and permutation is that: subset is a selection of the original set, where permutation is the arrangement of the original set. Set A has <strong>6 permutations</strong>: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]</li></ul><h4>Backtracking Algorithm</h4><p>Assume we are at the starting point of a maze, we’re going to find all possible paths to exit it. For each move, we need to decide the direction of whether to go down or go right. If we reach a dead-end, we need to go back to choose another direction that probably works. This process of continuing moving and backing is a classical example of <strong>backtracking</strong>.</p><blockquote><strong>Backtracking</strong> is a general <a href="https://en.wikipedia.org/wiki/Algorithm">algorithm</a> for finding all (or some) solutions to some <a href="https://en.wikipedia.org/wiki/Computational_problem">computational problems</a>, notably <a href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem">constraint satisfaction problems</a>, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.</blockquote><p>The backtracking algorithm performs well in finding all valid solutions. Next, I’ll explain how to implement it in subset/combination/permutation problems.</p><h4>Subset Problems</h4><p><a href="https://leetcode.com/problems/subsets/"><strong>Problem</strong></a>: Given an integer array nums, return <em>all possible subsets (the power set). </em>The solution set must not contain duplicate subsets.</p><p><strong>Explain</strong>: As we all know, the empty set is a subset of any set. We can start with the empty set, then gradually add an element to it, until we run out all elements. One thing to notice is: every time we add an element, we need to make sure that it doesn&#39;t appear before. To avoid it, we need to append the element from nums[i+1:] .</p><p><strong>Process:</strong></p><p>Let’s take set = [1,2,3] as an example, to see how we find all subsets</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TIjIx12DUbEVeJ6TU2evbQ.jpeg" /></figure><ul><li><strong>Step 1</strong>: find all subsets start with element nums[0], we add nums[0] to the empty set [] to create a new subset [1]. Start from set [1], we still can add elements from the remaining set [2, 3] to create some new subsets. First, add element 2 to the current subset to create a new subset [1, 2], then we can add the remaining element 3 to this subset to create a new subset [1, 2, 3]. Secondly, we go back to the previous subset [1], add element 3 to create another subset [1, 3].</li><li><strong>Step 2</strong>: find all subsets start with element nums[1], we add nums[1] to the empty set [] to create a new subset [2]. Since there’s still one element 3 in remain, we can only create a new element with it [2, 3]</li><li><strong>Step 3</strong>: find all subsets start with element nums[2], we add nums[1] to the empty set [] to create a new subset [3]. There’s no element left in the original set. We’ve found all possible subsets.</li></ul><p><strong>Code:</strong></p><pre>class Solution:<br>    def subsets(self, nums: List[int]) -&gt; List[List[int]]:<br>        res = []<br>        self.backtrack(nums, [], res)<br>        return res<br>    <br>    def backtrack(self, nums, path, res):<br>        res.append(path)<br>        for i in range(len(nums)):<br>            self.backtrack(nums[i+1:], path+[nums[i]], res)</pre><h4>Permutation Problems</h4><p><a href="https://leetcode.com/problems/permutations/"><strong>Problem</strong></a><strong>:</strong> Given an array nums of distinct integers, return <em>all the possible permutations</em>. You can return the answer in <strong>any order</strong>.</p><p><strong>Explain</strong>:</p><p>Permutations are arrangements of the original set. The key point is to find all possible arrangements and make sure there’s no duplicate. We can iterate the set then find all permutations starting with the current element.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ow1k88kEknNWfKhuoS9WyQ.jpeg" /></figure><p><strong>Process</strong>:</p><p><strong>Step 1</strong>: find all permutations starting with element nums[0]. Now the left elements are [2, 3], we pick elements from it and form the permutation with the left one until the set runs out.</p><p><strong>Step 2</strong>: find all permutations starting with element nums[1]. Now the left elements are [1, 3], we pick elements from it and form the permutation with the left one until the set runs out.</p><p><strong>Step 3</strong>: find all permutations starting with element nums[2]. Now the left elements are [1, 2], we pick elements from it and form the permutation with the left one until the set runs out.</p><p><strong>Code</strong>:</p><pre>class Solution:<br>    def permute(self, nums: List[int]) -&gt; List[List[int]]:<br>        res = []<br>        self.backtrack(nums, [], res)<br>        return res <br>    <br>    def backtrack(self, nums, path, res):<br>        if not nums:<br>            res.append(path)<br>            return <br>        <br>        for i in range(len(nums)):<br>            self.backtrack(nums[:i]+nums[i+1:], path+[nums[i]], res)</pre><h4>Combination Problems</h4><p><a href="https://leetcode.com/problems/combination-sum/"><strong>Problem</strong></a><strong>:</strong> Given an array of <strong>distinct</strong> integers candidates and a target integer target, return <em>a list of all </em><strong><em>unique combinations</em></strong><em> of </em>candidates<em> where the chosen numbers sum to </em>target<em>.</em> You may return the combinations in <strong>any order</strong>. The <strong>same</strong> number may be chosen from candidates an <strong>unlimited number of times</strong>. Two combinations are unique if the frequency of at least one of the chosen numbers is different.</p><p><strong>Explain</strong>:</p><p>Similar to the previous problem, we can start at the first element in the set, and gradually find combinations that sum to the target. There are two conditions we need to consider during the process: 1). if the current sum equals the target, we’ve found one combination, stop finding 2). if the current sum is greater than the target, we stop finding it.</p><p><strong>Process</strong>:</p><p>Let’s take candidates = [2,3,6,7], target = 7 as an example.</p><ul><li><strong>Case 1</strong>: find all combinations start with [2]. Combine with each element from [2, 3, 6, 7], only [2, 2] and [2, 3] can have possible solutions due to the other two’s sum being greater than the target. For [2, 2], it has four more combinations [2, 2, 2], [2, 2, 3], [2, 2, 6], [2, 2, 7], and the sum of [2, 2, 3] equals to the target, we’ve found one combination. [2, 2, 2] is possible to create a combination because it’s less than the target. The possible combinations are : [2, 2, 2, 2], [2, 2, 2, 3],[2, 2, 2, 6],[2, 2, 2, 7], and there’s no valid combination due to the sums are all greater than the target.</li><li><strong>Case 2</strong>: find all combinations start with [3]. Combine with each element from [6, 7]: [3, 6] and [3, 7], there are no valid combinations.</li><li><strong>Case 3</strong>: find all combinations start with [7]. Itself is one valid combination. And there’s no more possible combination.</li><li><strong>Case 4</strong>: find all combinations start with [8]. No combinations found in this case.</li></ul><p>Result is: [[2, 2, 3], [7]]</p><p><strong>Code</strong>:</p><pre>class Solution:</pre><pre>    def combinationSum(self, candidates: List[int], target: int) -&gt; List[List[int]]:<br>        res = []<br>        candidates.sort()<br>        self.backtrack(candidates, [], res, target)<br>        return res<br>    def backtrack(self, candidates, path, res, target):<br>        if target &lt; 0:<br>            return <br>        if target == 0:<br>            res.append(path)<br>            return <br>        for i in range(len(candidates)):<br>            self.backtrack(candidates[i:], path+[candidates[i]], res, target - candidates[i])</pre><h4>Reference</h4><ul><li><a href="https://en.wikipedia.org/wiki/Backtracking">Backtracking - Wikipedia</a></li><li><a href="https://en.wikipedia.org/wiki/Subset">Subset</a></li></ul><p><a href="https://en.wikipedia.org/wiki/Permutation">https://en.wikipedia.org/wiki/Permutation</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d50dc8f60f92" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>