<?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 bwithcho on Medium]]></title>
        <description><![CDATA[Stories by bwithcho on Medium]]></description>
        <link>https://medium.com/@bwithchewoo?source=rss-a4ae8056743f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*-dA-ArWOKpYAcOsCkepNGg.jpeg</url>
            <title>Stories by bwithcho on Medium</title>
            <link>https://medium.com/@bwithchewoo?source=rss-a4ae8056743f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 10:05:27 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@bwithchewoo/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 Practice Using Python3 — Day 128]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-128-84bb00b9c67b?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/84bb00b9c67b</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Sat, 31 May 2025 14:18:58 GMT</pubDate>
            <atom:updated>2025-05-31T14:18:58.955Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 128</h3><p><a href="https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/description/">https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/description/</a></p><p>Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.</p><p>You may assume each number in the sequence is unique.</p><p>Consider the following binary search tree:</p><pre>     5<br>    / \<br>   2   6<br>  / \<br> 1   3</pre><p><strong>The Approach:</strong></p><p>The problem wants us to check if an array represents a valid preorder traversal of a binary search tree. A binary search tree is structured where all nodes in the left subtree must be less than the node and all nodes in the right subtree must be greater than the node. Preorder traversal is when we visit the current root, then the left subtree and then the right subtree.</p><p>We should keep track of the minimum that future values must respect as we explore subtrees and use a stack to mimic preorder traversal. As we traverse the preorder array, we should push values to the stack when we are still in the left subtree. Then whenever we encounter a value greater than the top of the stack, it means that we are transitioning from a left subtree to a right subtree. Pop from the stack until we find the appropriate ancestor and update the minimum. If a value is less than the lower bound, this is invalid.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def verifyPreorder(self, preorder: List[int]) -&gt; bool:<br>        stack = []<br>        lower_bound = float(&#39;-inf&#39;)<br>    <br>        for value in preorder:<br>            if value &lt; lower_bound:<br>                return False<br><br>            while stack and value &gt; stack[-1]:<br>                lower_bound = stack.pop()<br><br>            stack.append(value)<br>    <br>        return True</pre><p><a href="https://leetcode.com/problems/paint-house/">https://leetcode.com/problems/paint-house/</a></p><p>There are a row of <em>n</em> houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.</p><p>The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.</p><p><strong>The Approach:</strong></p><p>The problem wants us to imagine we are painting houses one by one with three choices of colors, red, blue or green and the constraint that we can’t paint it the same color as the previous house. We should use dynamic programming and make a decision at each house and pick a color while keeping track of the minimum cost to paint a house a certain color. We compute the minimum cost for each of the 3 color choices based on the costs of painting the previous house with either of the other two colors. By the end we will have three total costs for the last house, one for each color and we just need to pick the minimum of those three.</p><p><strong>Next Steps:</strong></p><p>First lets handle the simplest case, if there are no houses, there is nothing to paint so return 0. Otherwise, lets iterate through each house starting from the second house, not the first because we will be building up the solution using previous results to compute the current cost. We do this by adding the cost of painting the current house a certain color and the minimum of the cost of painting the previous house the other two colors. We will be overwriting the costs array and column 0 represents red, column 1 represents blue, column 2 represents green. Then we just need to take the minimum of the last row of costs as it will contain the minimum total cost for each ending color.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def minCost(self, costs: List[List[int]]) -&gt; int:<br>        if not costs:<br>            return 0<br>    <br>        n = len(costs)<br><br>        for i in range(1, n):<br>            costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])<br>            costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])<br>            costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])<br>    <br>        return min(costs[-1])</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=84bb00b9c67b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 127]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-127-45545feadd91?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/45545feadd91</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Sat, 31 May 2025 00:17:11 GMT</pubDate>
            <atom:updated>2025-05-31T00:17:11.267Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 127</h3><p><a href="https://leetcode.com/problems/meeting-rooms/description/">https://leetcode.com/problems/meeting-rooms/description/</a></p><p>Given an array of meeting time intervals consisting of start and end times [[s1,e1], [s2,e3],…] (si &lt; ei), determine if a person could attend all meetings.</p><p><strong>The Approach:</strong></p><p>The problem wants us to determine if a person could attend all meetings given a list of time intervals consisting of start and end times. First lets sort the list of time intervals based on the start times. We want to do this to make comparison easier for consecutive meetings as we check for overlaps. Then lets initialize a variable to track the end time of the last meeting and set it to negative infinity at first so that it will always be the smallest time to make it easier to reset when we get to the first pair.</p><p>Then lets iterate through the sorted meetings and if the start time of the current meeting is greater than or equal to the compare value, update our variable to the end of the meeting. This is because for each meeting, we only need to check if the meeting starts before the previous one ends. If start is greater than or equal to our variable it means that there is no overlap with any of the previous meetings. Since the list is sorted, all earlier meetings must have ended before this one starts so we only care about the most recent meeting’s end time going forward. If the start time is less than the variable, that means there is a conflict, so return False. If we reach the end of the loop without any conflicts, return True.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def canAttendMeetings(self, intervals: List[List[int]]) -&gt; bool:<br>        sortedlist = sorted(intervals, key=lambda x: x[0])<br>        compare = float(&#39;-inf&#39;)<br>        for start, end in sortedlist:<br>            if start &gt;= compare:<br>                compare = end<br>            else:<br>                return False<br>        return True</pre><p><a href="https://leetcode.com/problems/factor-combinations/">https://leetcode.com/problems/factor-combinations/</a></p><p>Numbers can be regarded as the product of their factors.</p><ul><li>For example, 8 = 2 x 2 x 2 = 2 x 4</li></ul><p>Given an integer n, return <em>all possible combinations of its factors</em>. You may return the answer in <strong>any order</strong>.</p><p><strong>Note</strong> that the factors should be in the range [2, n — 1].</p><p><strong>The Approach:</strong></p><p>The problem wants us to find all unique combinations of numbers between 2 and n-1 that multiply to exactly n. Every number can be built by multiplying together smaller numbers. We want to also avoid duplicates so we should explore factors in non-decreasing order. Start from 2 up to the square root of n as possible starting factors. We only need to consider up to the square root of n as a factor because if n = a x b, and the square root of n multiplied by itself equals n, it means that either a or b must be less than or equal to the square root of n. Once we find a valid factor, add that factor and n divided by that factor as one valid result. Then we want to recursively explore the co-factor and ensure that any other factor we find is greater than previous ones to maintain non-decreasing order.</p><p><strong>Next Steps:</strong></p><p>First lets initialize an empty list that will store the factors that we find. Then lets create a helper function that we will use for recursion to try every possible factor. We need to know the number that we are factoring and the number will get smaller and smaller in each recursive call. We also need to know the smallest factor we can try in the next recursive call to enforce non-decreasing order of factors. We should also pass down the list of factors we have chosen so far in the recursive path to build up a complete factor combination that we can add to our results list.</p><p>We want to try every number as a factor from the starting number up to the square root of the number we are trying to factor. Then check if the number is actually a factor by making sure that there is no remainder when dividing, if there is, then this number can’t be used in a product to reach the number. Then calculate the other part of the factor pair by doing integer division by the current number we are trying.</p><p>Store the complete factor combination in the results list and then recursively try to further factor the cofactor we found by calling the helper function passing the cofactor as the new remaining number, the current number as the new start to maintain non-decreasing order and the path plus the current number as the new factor sequence.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def getFactors(self, n: int) -&gt; List[List[int]]:<br>        results = []<br>        def backtrack(remaining: int, start: int, path: List[int]):<br>            for i in range(start, isqrt(remaining) + 1):<br>                if remaining % i == 0:<br>                    cofactor = remaining // i<br>                    results.append(path + [i, cofactor])<br>                    backtrack(cofactor, i, path + [i])<br><br>        backtrack(n, 2, [])<br>        return results</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=45545feadd91" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 126]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-126-3a1a03d081e3?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/3a1a03d081e3</guid>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Thu, 29 May 2025 17:58:29 GMT</pubDate>
            <atom:updated>2025-05-29T17:58:29.250Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 126</h3><p><a href="https://leetcode.com/problems/count-univalue-subtrees/description/">https://leetcode.com/problems/count-univalue-subtrees/description/</a></p><p>Given a binary tree, count the number of uni-value subtrees.</p><p>A Uni-value subtree means all nodes of the subtree have the same value.</p><p><strong>The Approach:</strong></p><p>The problem wants us to figure out how many subtrees have all nodes with the same value in a binary tree. Lets start from the bottom up, from the leaves up to the root using post-order traversal. We want to start from the bottom because a leaf node can be considered a uni-value subtree by itself because it has only one value. We basically treat every node as the root of a potential uni-value subtree. For non-leaf nodes, a subtree is uni-value if both left and right subtrees are also uni-value or don’t exist and if the values in those subtrees match the current node’s value.</p><p><strong>Next Steps:</strong></p><p>First lets initialize a variable that we will use to keep track of how many uni-value subtrees we find. Then because we want to use recursion for post-order traversal, lets define a helper function to check whether the subtree with a node passed down is uni-value. Since this is recursion, lets define our base case, an empty node is considered a uni-value subtree and leaf nodes that have None children are treated as uni-value, so return True.</p><p>Then call our function on the left and right nodes to check if both sides are uni-value. If either side is not uni-value, return False. If the values of the children don’t match the current node, return False. If all these checks get passed, then it means the subtree is uni-value so increment our counter and return True.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def countUnivalSubtrees(self, root: TreeNode) -&gt; int:<br>        self.count = 0 <br><br>        def is_unival(node):<br>            if node is None:<br>                return True<br><br>            left_uni = is_unival(node.left)<br>            right_uni = is_unival(node.right)<br><br>            if not left_uni or not right_uni:<br>                return False<br><br>            if node.left and node.left.val != node.val:<br>                return False<br><br>            if node.right and node.right.val != node.val:<br>                return False<br><br>            self.count += 1<br>            return True<br><br>        is_unival(root)<br>        return self.count</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3a1a03d081e3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 125]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-125-22e472b6b325?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/22e472b6b325</guid>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Wed, 28 May 2025 16:24:02 GMT</pubDate>
            <atom:updated>2025-05-28T16:24:02.190Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 125</h3><p><a href="https://leetcode.com/problems/strobogrammatic-number-iii/description/">https://leetcode.com/problems/strobogrammatic-number-iii/description/</a></p><p>Given two strings low and high that represent two integers low and high where low ≤ high, return <em>the number of </em><strong><em>strobogrammatic numbers</em></strong><em> in the range</em> [low, high].</p><p>A <strong>strobogrammatic number</strong> is a number that looks the same when rotated 180 degrees (looked at upside down).</p><p><strong>The Approach:</strong></p><p>The problem wants us to find out how many strobogrammatic numbers there are between the range of two numbers. A strobogrammatic number is a number when rotated 180 degrees is a valid number, such a 0, 1, 6, 8, 9. We can check every number between the range but this would be inefficient for large ranges. Instead lets generate valid strobogrammatic numbers using recursion to build longer numbers by adding valid digit pairs to both ends of smaller valid numbers. Then compare them with the range and increment a counter for every valid strobogrammatic number within the range.</p><p><strong>Next Steps:</strong></p><p>First lets create a list of valid strobogrammatic pairs that we can reference later. Then lets create a helper function and we need to pass down the number of digits left to fill in the current recursive step and the total length of the number we are building. Since we are using recursion, lets define our base cases. If n is 0, return an empty string and if n is 1, return 0, 1, 8 because only those numbers have a valid pair with themselves.</p><p>Then lets call our function to recursively generate all valid strobogrammatic numbers of length n — 2 because we want to wrap an existing string with a pair of digits. Initialize an empty list to store all valid results of length n. Then loop through each smaller sub-number returned from the recursive call and for each valid strobogrammatic pair, wrap the current middle with the pair. We also want to check if n equals total length, if it does then we don’t want to use 0 for the pair to avoid leading zeros. Add the new strobogrammatic number to our list and then return result so that higher calls can build up to larger numbers.</p><p>Initialize a variable that will serve as a counter of how many valid strobogrammatic numbers are within the range, starting from 0. We only want to generate strobogrammatic numbers of lengths that could fall within the range so we define n and total length using the lengths of low and high. Now that we generated all numbers of a valid length, we need to check if they are numerically within the range. We do this by checking if the number has the same length as low, it can’t be less than low and if the number has the same length as high, make sure it’s not greater than high. Increment the counter if it fulfills these conditions, otherwise skip.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def strobogrammatic_in_range(low, high):<br>        pairs = [(&#39;0&#39;, &#39;0&#39;), (&#39;1&#39;, &#39;1&#39;), (&#39;6&#39;, &#39;9&#39;), (&#39;8&#39;, &#39;8&#39;), (&#39;9&#39;, &#39;6&#39;)]<br>    <br>        def build(n, total_length):<br>            if n == 0:<br>                return [&quot;&quot;]<br>            if n == 1:<br>                return [&quot;0&quot;, &quot;1&quot;, &quot;8&quot;]<br>    <br>            middles = build(n - 2, total_length)<br>            result = []<br>            for middle in middles:<br>                for a, b in pairs:<br>                    if n == total_length and a == &#39;0&#39;:<br>                        continue<br>                    result.append(a + middle + b)<br>            return result<br>    <br>        count = 0<br>        for length in range(len(low), len(high) + 1):<br>            for num in build(length, length):<br>                if (len(num) == len(low) and num &lt; low) or (len(num) == len(high) and num &gt; high):<br>                    continue<br>                count += 1<br>        return count</pre><p><a href="https://leetcode.com/problems/group-shifted-strings/">https://leetcode.com/problems/group-shifted-strings/</a></p><p>Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -&gt; “bcd”. We can keep &quot;shifting&quot; which forms the sequence:</p><pre>&quot;abc&quot; -&gt; &quot;bcd&quot; -&gt; ... -&gt; &quot;xyz&quot;</pre><p>Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in <strong>any order</strong>.</p><p><strong>The Approach:</strong></p><p>The problem wants us to group strings in an array that belong to the same shifting sequence. Basically when we shift a string, each character shifts by the same amount. Strings in the same shifting sequence will have the same relative difference between characters, even if they start with different letters.</p><p>So lets figure out the difference pattern for each string, which tells us how many positions we move forward in the alphabet between each pair of adjacent characters in the string. To handle wraparounds from z to a, use modulo 26 since there are 26 characters. Use a dictionary and use the difference pattern as the key and the strings as the value to group all the strings that share the same pattern.</p><p><strong>Next Steps:</strong></p><p>First lets initialize an empty dictionary using defaultdict which will initialize empty lists for new keys that we will use to group strings together based on their shifting pattern. Then go through each string and initialize an empty list that will store the difference pattern we calculate. Then go through each string starting from the second character and compare it with the previous character. Look at each adjacent pair of characters and get the ASCII code of the character and find the difference between the two characters. The difference can be negative when the alphabet wraps around so add 26 and do modulo 26 to account for this. Add the difference to the pattern list that will represent the string’s shifting.</p><p>Convert the difference pattern into a tuple to make it hashable because a list is not hashable and cannot be used as a dictionary key. Then append the string with the same difference pattern to our dictionary. By the end of the loops, we will have strings collected into groups based on their difference pattern. So we want to get all the values in the dictionary, which will be lists of grouped strings and convert it into a list.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def groupStrings(self, strings: List[str]) -&gt; List[List[str]]:<br>        groups = defaultdict(list)  <br>    <br>        for s in strings:  <br>            pattern = []<br>    <br>            for i in range(1, len(s)):<br>                diff = (ord(s[i]) - ord(s[i - 1]) + 26) % 26<br>                pattern.append(diff)<br><br>            key = tuple(pattern)<br><br>            groups[key].append(s)<br><br>        return list(groups.values())</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=22e472b6b325" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 124]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-124-c32be95fcba8?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/c32be95fcba8</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Tue, 27 May 2025 21:10:21 GMT</pubDate>
            <atom:updated>2025-05-27T21:10:21.987Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 124</h3><p><a href="https://leetcode.com/problems/strobogrammatic-number/description/">https://leetcode.com/problems/strobogrammatic-number/description/</a></p><p>A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).</p><p>Write a function to determine if a number is strobogrammatic. The number is represented as a string.</p><p><strong>The Approach:</strong></p><p>The problem wants us figure out if a number is strobogrammatic, which is when a number looks the same when rotated 180 degrees. There are only a couple numbers that are strobogrammatic, 0, 1, 6, 8, 9. We can therefore map 0 to 0, 1 to 1, 6 to 9, 8 to 8 and 9 to 6. The problem tells us that the number length will be 50 digits max and will have no leading zeros. We can use two pointers to compare positions from both ends of the number and check if the numbers map to each other. If the number has an odd number of digits, the middle digit must be 0, 1, 8 since it must map to itself.</p><p><strong>Next Steps:</strong></p><p>First lets create a dictionary to define how each valid strobogrammatic number flips. Then initialize two pointers, one at the start of the number and the other at the end of the number string. Until the pointers cross, we want to compare the numbers at each pointer. Check if the left number exists in our mapping, if it does, its mapped value needs to match the right number. If it doesn’t return False immediately.</p><p><strong>The Solution:</strong></p><pre>class Solution(object):<br>  def isStrobogrammatic(self, num):<br>      mapping = {<br>            &#39;0&#39;: &#39;0&#39;,<br>            &#39;1&#39;: &#39;1&#39;,<br>            &#39;6&#39;: &#39;9&#39;,<br>            &#39;8&#39;: &#39;8&#39;,<br>            &#39;9&#39;: &#39;6&#39;<br>      }<br>        <br>      left, right = 0, len(num) - 1<br>      <br>      while left &lt;= right:<br>          left_digit = num[left]<br>          right_digit = num[right]<br><br>          if left_digit not in mapping or mapping[left_digit] != right_digit:<br>              return False<br>          <br>          left += 1<br>          right -= 1<br>      <br>      return True</pre><p><a href="https://leetcode.com/problems/strobogrammatic-number-ii/">https://leetcode.com/problems/strobogrammatic-number-ii/</a></p><p>Given an integer n, return all the <strong>strobogrammatic numbers</strong> that are of length n. You may return the answer in <strong>any order</strong>.</p><p>A <strong>strobogrammatic number</strong> is a number that looks the same when rotated 180 degrees (looked at upside down).</p><p><strong>The Approach:</strong></p><p>The problem basically wants us to generate all strobogrammatic numbers of length n, numbers that look the same when rotated 180 degrees. We know that valid strobogrammatic numbers are 0, 1, 6, 8, 9. So we can build the numbers up recursively. Starting from base case of if n is 0, return an empty string and if n is 1, return 0, 1, 8 because only those digits are valid for odd length numbers. Then start building numbers of length n by adding the results from smaller inner numbers. When building the outermost pair, skip adding 0 to the front to prevent leading zeros.</p><p><strong>Next Steps:</strong></p><p>First lets create pair combinations in a list for the valid digit combinations of rotated numbers. Then lets create a helper function to handle recursion, with the arguments of the length of the string we are currently trying to build and the total length we want to get. These two arguments are important because we will continuously decrease the value of the current length with each recursive call and knowing the total length will help us know when we are building the outermost digits to avoid leading zeros.</p><p>Since this is recursion, lets define our exit cases, when the current length is 0, return an empty string and when the current length is 1, return 0, 1, 8, since only those numbers are strobogrammatic with themselves. Basically we want to use the recursion to grow outwards from a smaller inner core by adding digit pairs outward. Call our recursive function and subtract 2 from the current length, when we first call our recursive function, current length will start at n.</p><p>Initialize an empty list to store our result list. We want to loop through the list of shorter valid strobogrammatic strings that we get from our recursive calls and wrap each string with a valid strobogrammatic digit pair on both sides to make it longer. We also want to add a condition that if the current length is the total length and the pair is 0, don’t use 0 to avoid leading zeros.</p><p>Create the new valid number of the current length by adding the pair to each end and then add it to the result list. Then after trying all pairs on all middles, return the full list of valid strobogrammatic strings of this length. In essence this list becomes the middle part for previous recursive calls until the top level has all valid strobogrammatic numbers of length n.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def findStrobogrammatic(self, n: int) -&gt; list[str]:<br>        pairs = [(&#39;0&#39;, &#39;0&#39;), (&#39;1&#39;, &#39;1&#39;), (&#39;6&#39;, &#39;9&#39;), (&#39;8&#39;, &#39;8&#39;), (&#39;9&#39;, &#39;6&#39;)]<br><br>        def build(current_length: int, total_length: int) -&gt; list[str]:<br>            if current_length == 0:<br>                return [&quot;&quot;]<br>            if current_length == 1:<br>                return [&quot;0&quot;, &quot;1&quot;, &quot;8&quot;]<br><br>            middles = build(current_length - 2, total_length)<br>            result = []<br><br>            for middle in middles:<br>                for a, b in pairs:<br>                    if current_length == total_length and a == &#39;0&#39;:<br>                        continue<br>                    result.append(a + middle + b)<br><br>            return result<br><br>        return build(n, n)</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c32be95fcba8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 123]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-123-aa701d5c438a?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/aa701d5c438a</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Mon, 26 May 2025 15:27:10 GMT</pubDate>
            <atom:updated>2025-05-26T15:27:10.509Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 123</h3><p><a href="https://leetcode.com/problems/shortest-word-distance/description/">https://leetcode.com/problems/shortest-word-distance/description/</a></p><p>Given a list of words and two words <em>word1</em> and <em>word2</em>, return the shortest distance between these two words in the list.</p><p><strong>The Approach:</strong></p><p>The problem wants us to find the shortest distance between two words in a list of words. It tells us that both words exist in the given list and that the two words are not the same. Since we know that, lets just find both words in the list as we traverse and store their positions. If we’ve seen both at least once, calculate the distance between their latest positions and update the minimum distance. This is because we want to account for if both words appear multiple times.</p><p><strong>Next Steps:</strong></p><p>Lets initialize two variables to track the positions of the two words we are trying to find in the list respectively and initialize them both at -1. We give them this value initially as an indicator to us that the word has not been found yet, if it has been found, the value would be at least 0 since indexes range from 0 to positive infinity. Then initialize a variable to store our answer of the shortest minimum distance and set it at first to positive infinity, as any new answer we find will always be smaller.</p><p>Then go through each word in the list while keeping track of the index and word respectively. Then check if the current word is equal to either word that we are looking for, if it is, then store the index into its position variable. When both positions of the words are no longer -1, then set the answer between the previous minimum distance we found and the absolute value of the result of subtracting one position value from the other.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -&gt; int:<br>        w1pos= -1<br>        w2pos = -1<br>        ans = float(&#39;inf&#39;)<br>        for index, word in enumerate(wordsDict):<br>            if word == word1:<br>                w1pos = index<br>            if word == word2:<br>                w2pos = index<br>            if w1pos != -1 and w2pos != -1:<br>                ans = min(ans, abs(w1pos - w2pos))<br>        return ans</pre><p><a href="https://leetcode.com/problems/shortest-word-distance-ii/">https://leetcode.com/problems/shortest-word-distance-ii/</a></p><p>Given a list of words and two words <em>word1</em> and <em>word2</em>, return the shortest distance between these two words in the list.</p><p><em>word1</em> and <em>word2</em> may be the same and they represent two individual words in the list.</p><p><strong>The Approach:</strong></p><p>The problem wants us to find the shortest distance between any two occurrences of two words, with the possibility that the two words are the same. The problem tells us that the words are guaranteed to exist in the list. There are two possibilities then for the two words, the words being the same and the words being different. If they are the same, we need to find the smallest distance between two different occurrences of the same word so not the same index. If they are different, we just need to find how close the two different words appear in the list.</p><p><strong>Next Steps:</strong></p><p>First lets initialize two variables to store the index positions of the two words and set them at -1, which will tell us that we haven’t found any instances of the word yet in the list. Then initialize a variable that will store the minimum distance to positive infinity so that any new distance we find will always be less.</p><p>Loop through each word in the list along with its index and handle two different cases, when the two words are the same or different. If the two words are different, record their positions in their respective variables. Once both words have been seen at least once, figure out the distance between them and update the minimum distance found.</p><p>If the words are the same, then when we find a word that matches the word we are looking for and we have already seen this word before, calculate the distance from the previous occurrence to the current one and update the minimum distance if it is smaller. Then move the previous pointer forward to the current index to handle consecutive appearances of the same word.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -&gt; int:<br>        w1pos = -1<br>        w2pos = -1<br>        ans = float(&#39;inf&#39;)<br>        <br>        for index, word in enumerate(wordsDict):<br>            if word1 != word2:<br>                if word == word1:<br>                    w1pos = index<br>                if word == word2:<br>                    w2pos = index<br>                if w1pos != -1 and w2pos != -1:<br>                    ans = min(ans, (abs(w1pos-w2pos)))<br>            if word1 == word2:<br>                if word == word1:<br>                    if w1pos != -1:<br>                        ans = min(ans, index - w1pos)<br>                    w1pos = index<br>        return ans</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aa701d5c438a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 122]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-122-2b37e75e95fe?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/2b37e75e95fe</guid>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Sun, 25 May 2025 13:31:16 GMT</pubDate>
            <atom:updated>2025-05-25T13:31:16.093Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 122</h3><p><a href="https://leetcode.com/problems/different-ways-to-add-parentheses/description/">https://leetcode.com/problems/different-ways-to-add-parentheses/description/</a></p><p>Given a string expression of numbers and operators, return <em>all possible results from computing all the different possible ways to group numbers and operators</em>. You may return the answer in <strong>any order</strong>.</p><p>The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10⁴.</p><p><strong>The Approach:</strong></p><p>The problem wants us to explore all the different ways to group numbers and operators using parentheses and get the result of each possible grouping. So lets go through the string and every time we see an operator, lets consider it a place to split the expression. Basically the operator is like a pivot where everything to the left is one sub expression and everything to the right is another sub expression.</p><p>Recursively solve all possible results from both the left and right sub expressions. After getting all the possible results from the left and right parts, combine them using the operator we split at. Use memoization to avoid recalculating the same sub expression.</p><p><strong>Next Steps:</strong></p><p>First lets initialize an empty dictionary that will store results of sub expressions so we don’t waste time recalculating the same expressions. Then lets initialize a helper function to handle recursion, it only needs the information of the string it is evaluating. Since this is recursion, lets define our base cases, if the expression exists in our dictionary, return the calculation of that expression because we already solved that sub problem. If the expression is just a digit and has no operator, return the number.</p><p>Define an empty list that we use to store the results of different ways to group numbers and operators. We want the result list inside the helper function and not outside of it because each recursive call will create its own list and return it upwards. The parent call will then combine the returned results to build new results. Each recursive call is self-contained and will return its own results and will naturally build the full set of answers by combining sub results.</p><p>Then loop through the string, if the character is an operator, split the string into two parts, left and right by splitting the string into everything before and after the operator respectively. Recursively compute all results for the left and right parts. Each recursive call will return all possible results for that sub part.</p><p>Then for every left result and right result, apply the operator and then add that result to the list. Afterwards store the result of the expression into our dictionary, so that later in recursion if we hit the same string again, we can just return the stored result instead of recalculating.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def diffWaysToCompute(self, expression: str) -&gt; List[int]:<br>        memo = {}<br><br>        def compute(expr: str) -&gt; List[int]:<br>            if expr in memo:<br>                return memo[expr]<br><br>            if expr.isdigit():<br>                return [int(expr)]<br><br>            results = []<br>            for i, char in enumerate(expr):<br>                if char in &quot;+-*&quot;:<br>                    left = expr[:i]<br>                    right = expr[i+1:]<br><br>                    left_results = compute(left)<br>                    right_results = compute(right)<br><br>                    for l in left_results:<br>                        for r in right_results:<br>                            if char == &#39;+&#39;:<br>                                results.append(l + r)<br>                            elif char == &#39;-&#39;:<br>                                results.append(l - r)<br>                            elif char == &#39;*&#39;:<br>                                results.append(l * r)<br><br>            memo[expr] = results<br>            return results<br><br>        return compute(expression)</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2b37e75e95fe" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 121]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-121-dc55622ac133?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/dc55622ac133</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Sat, 24 May 2025 15:19:04 GMT</pubDate>
            <atom:updated>2025-05-24T15:19:04.852Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 121</h3><p><a href="https://leetcode.com/problems/delete-node-in-a-linked-list/description/">https://leetcode.com/problems/delete-node-in-a-linked-list/description/</a></p><p>There is a singly-linked list head and we want to delete a node node in it.</p><p>You are given the node to be deleted node. You will <strong>not be given access</strong> to the first node of head.</p><p>All the values of the linked list are <strong>unique</strong>, and it is guaranteed that the given node node is not the last node in the linked list.</p><p>Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:</p><ul><li>The value of the given node should not exist in the linked list.</li><li>The number of nodes in the linked list should decrease by one.</li><li>All the values before node should be in the same order.</li><li>All the values after node should be in the same order.</li></ul><p><strong>Custom testing:</strong></p><ul><li>For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.</li><li>We will build the linked list and pass the node to your function.</li><li>The output will be the entire list after calling your function.</li></ul><p><strong>The Approach:</strong></p><p>The problem wants us to delete a node from a linked list, but we don’t have access to the head of the list and since this is a singly linked list, we can’t easily access the previous node from the node we want to remove. We are given the node to delete with the knowledge that it is not the last node, meaning that the node we want to delete has a next node.</p><p>So instead of trying to update the pointer from the previous node since we can’t access it, lets try something else. Copy the value from the next node into the current node to overwrite the current node. Then skip the next node which would be a duplicate by updating the current node’s next pointer to the next next node.</p><p><strong>Next Steps:</strong></p><p>Since we only have access to the node we want to delete, basically we can only get access to all the nodes starting from the node we want to delete. So lets replace the current node’s value with the next node’s value. Then lets move the next pointer to point to the next next node to basically skip the next node. This will ensure that we are mimicking deletion while ensuring the same order.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def deleteNode(self, node):<br>        &quot;&quot;&quot;<br>        :type node: ListNode<br>        :rtype: void Do not return anything, modify node in-place instead.<br>        &quot;&quot;&quot;<br>        node.val = node.next.val<br><br>        node.next = node.next.next</pre><p><a href="https://leetcode.com/problems/sliding-window-maximum/">https://leetcode.com/problems/sliding-window-maximum/</a></p><p>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.</p><p>Return <em>the max sliding window</em>.</p><p><strong>The Approach:</strong></p><p>The problem gives us an array of numbers and a window size k that defines what numbers we are able to see in the array. It wants us to return an array of the maximum numbers for each window as we move from left to right in the main array. We can loop through each window and figure out the max by looking through each window size k, but this would take too long.</p><p>So instead lets us a double-ended queue, deque, to track useful elements. Using deque allows us to add and remove from both ends in constant time while also keeping track of indices of elements in the window and removing indices that are no longer in the window. Make sure that the front of the queue always holds the index of the max element for the current window. Essentially we want to ensure that we store indices of elements in decreasing order of value from front to back.</p><p>When we move the window, we will need to add new elements. But first, we want to remove indices from the back of the queue if their corresponding values are less than the new element because those elements will never be the max again. Add the new element’s index to the queue. Remove the index at the front if it is outside the current window. The element at the front of the queue should be the maximum for the current window.</p><p><strong>Next Steps:</strong></p><p>Lets initialize an empty list that will store the values of the maximum number in each window size k. Then initialize a deque that will store indices, not values to contain elements inside the current sliding window. We can still access the value by looking up the value using the index we stored. Using indexes lets us keep track of each value’s position which is unique, especially if there are duplicate values.</p><p>As we go through the numbers array, we want to remove out-of-window indices. We know the left boundary of the current window by subtracting k + 1 from the current position of the array. If the index at the front of the deque is outside this window, remove it. Also remove elements from the back of the deque if they are smaller than the current value because they will never be the max in this window or any future one. The right boundary of the current window is where we are in the array as we traverse left to right.</p><p>Add the current index to the deque. We can simply add because before this we popped from the back of the deque until it is empty or find a value that is greater than or equal to the new value. This ensures that only larger values stay in the deque from left to right and makes it so that we can simply append the current index since all smaller values have been removed.</p><p>Add the max value to our result list once we filled up the first full window of size k. When the current position, i, is equal to k-1, it means we have seen the first complete window. After that, every new element shifts the window right by one and so we want to collect a result for each next step through the array. We append the the number at the index stored in the first element of deque because the first element is always the largest element’s index in the current window.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def maxSlidingWindow(self, nums: List[int], k: int) -&gt; List[int]:<br>        result = []<br>        dq = deque()  <br><br>        for i in range(len(nums)):<br>            if dq and dq[0] &lt; i - k + 1:<br>                dq.popleft()<br><br>            while dq and nums[dq[-1]] &lt; nums[i]:<br>                dq.pop()<br><br>            dq.append(i)<br><br>            if i &gt;= k - 1:<br>                result.append(nums[dq[0]])<br><br>        return result</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dc55622ac133" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 120]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-120-3f02ca7820c5?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/3f02ca7820c5</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Fri, 23 May 2025 16:29:56 GMT</pubDate>
            <atom:updated>2025-05-23T16:29:56.574Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 120</h3><p><a href="https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/">https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/</a></p><p>Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.</p><p>According to the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor">definition of LCA on Wikipedia</a>: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow <strong>a node to be a descendant of itself</strong>).”</p><p><strong>The Approach:</strong></p><p>The problem wants us to find the lowest common ancestor in a binary search tree. In a binary search tree, all nodes in the left subtree have smaller values than the node and all nodes in the right subtree have larger values than the node. So lets start from the root of the BST and compare the values of the two nodes we are trying to find the LCA for against the root. If both nodes are smaller than the current node, it means the LCA must be in the left subtree. If both are greater than the current node, the LCA must be in the right subtree. If one is smaller and one is greater, or if the current node matches either node, then the current node is the LCA.</p><p><strong>Next Steps:</strong></p><p>So set a variable to track the current node we are at in the tree and initialize it at the root. Then as long as the current node is not None, we will keep traversing the tree. Check the values of the two nodes we are looking for against the current node we are at. If both nodes are less than the current node, then set the current node to the current node’s left child. If both nodes are greater than the current node, set the current node to the current node’s right child. Otherwise, the current node is the split point so return the current node.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def lowestCommonAncestor(self, root: &#39;TreeNode&#39;, p: &#39;TreeNode&#39;, q: &#39;TreeNode&#39;) -&gt; &#39;TreeNode&#39;:<br>        current = root<br><br>        while current:<br>            if p.val &lt; current.val and q.val &lt; current.val:<br>                current = current.left<br><br>            elif p.val &gt; current.val and q.val &gt; current.val:<br>                current = current.right<br><br>            else:<br>                return current</pre><p><a href="https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/">https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/</a></p><p>Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.</p><p>According to the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor">definition of LCA on Wikipedia</a>: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow <strong>a node to be a descendant of itself</strong>).”</p><p><strong>The Approach:</strong></p><p>The problem wants us to find the lowest common ancestor of two nodes in a binary tree. In a binary tree, we can’t rely on node values to guide our search, the nodes can be anywhere in the tree. We have to explore the entire tree to find out where the two nodes are located. So we need to think recursively and check for each node in the tree, does this node contain either node in its left or right subtree. If it does, this node might be the lowest common ancestor.</p><p>Basically we want to recursively travel the tree, if we hit a leaf, return None because the node was not found in this path. If we find either node, return that node to signal that we found one of them. If both the left and right recursive calls return non-null then one node was found in one subtree and the another was found in the other subtree, meaning the current node is the LCA. If only one side returns non-null, it means both nodes are in that subtree. If both return null, then that subtree doesn’t have either node.</p><p><strong>Next Steps:</strong></p><p>Since we are going to be using recursion, lets define our exit case. If the current node is None, p or q, return the current node as it means we either hit the end of a tree or found one of the nodes we are looking for. Then recursively call the function on the left and right child respectively. If both left and right are non-null, it means that one node was found in one subtree and the second in the other, meaning that this node is the LCA. If only one is non-null, propagate that upward because it means that both nodes are in the same branch. Basically the first node to “see” both targets from different branches will return itself as the LCA.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def lowestCommonAncestor(self, root: &#39;TreeNode&#39;, p: &#39;TreeNode&#39;, q: &#39;TreeNode&#39;) -&gt; &#39;TreeNode&#39;:<br>        if root is None or root == p or root == q:<br>            return root<br><br>        left = self.lowestCommonAncestor(root.left, p, q)<br>        right = self.lowestCommonAncestor(root.right, p, q)<br><br>        if left and right:<br>            return root<br><br>        return left if left else right</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3f02ca7820c5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[LeetCode Practice Using Python3 — Day 119]]></title>
            <link>https://medium.com/@bwithchewoo/leetcode-practice-using-python3-day-119-0def1b178559?source=rss-a4ae8056743f------2</link>
            <guid isPermaLink="false">https://medium.com/p/0def1b178559</guid>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[bwithcho]]></dc:creator>
            <pubDate>Thu, 22 May 2025 16:09:12 GMT</pubDate>
            <atom:updated>2025-05-22T16:09:12.545Z</atom:updated>
            <content:encoded><![CDATA[<h3>LeetCode Practice Using Python3 — Day 119</h3><p><a href="https://leetcode.com/problems/implement-queue-using-stacks/description/">https://leetcode.com/problems/implement-queue-using-stacks/description/</a></p><p>Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).</p><p>Implement the MyQueue class:</p><ul><li>void push(int x) Pushes element x to the back of the queue.</li><li>int pop() Removes the element from the front of the queue and returns it.</li><li>int peek() Returns the element at the front of the queue.</li><li>boolean empty() Returns true if the queue is empty, false otherwise.</li></ul><p><strong>Notes:</strong></p><ul><li>You must use <strong>only</strong> standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.</li><li>Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.</li></ul><p><strong>The Approach:</strong></p><p>The problem wants us to implement a queue using two stacks to simulate front-to-back access using top-of-stack operations only. A queue removes elements from the front while a stack removes elements from the back. Therefore, we need to reverse the order of elements once during their transfer from one stack to another. Use one stack to handle all push operations and another to handle all pop/peek operations.</p><p>When we want to push an element, just push onto the input stack. When we want to pop or peek, do it from the output stack. If the output stack is empty, transfer all the elements from the input stack into the output stack to reverse the order and then pop/peek.</p><p><strong>Next Steps:</strong></p><p>So when a queue is initialized, lets initialize two stacks, one for push operations and another for pop/peek operations, basically one for input and another for output. This is so that we can add to a stack from the back, but when we want to pop/peek, we have a stack that is in reversed order so we can get the element from the back similar to stack operations but in queue order.</p><p>For the push operation, append the new element to the input stack which puts the new element at the back. For the empty function, return empty only if both stacks are empty. We check both stacks because some elements might still be in the input stack if we haven’t popped yet or some elements might be in the output stack waiting to be popped. Basically the queue is empty only if both the input and output stacks are empty because the queue could still have elements that are waiting to be processed in the input stack or ready for removal in the output stack.</p><p>For the pop and peek operation, we want to ensure first that there are elements in our output stack. Remember that we want the oldest element, which is at the bottom of the input stack. So we need to create a helper function to handle reversing the order of the input stack into the output stack only if the output stack is empty. If there are still elements in the output stack, just pop the last element or return the last element for peeking in the output stack because its reversed order that corresponds to the front of the queue.</p><p><strong>The Solution:</strong></p><pre>class MyQueue:<br><br>    def __init__(self):<br>        self.stack_in = []   <br>        self.stack_out = []  <br><br>    def push(self, x: int) -&gt; None:<br>        self.stack_in.append(x)<br><br>    def pop(self) -&gt; int:<br>        self.move_in_to_out()<br>        return self.stack_out.pop()<br><br>    def peek(self) -&gt; int:<br>        self.move_in_to_out()<br>        return self.stack_out[-1]<br><br>    def empty(self) -&gt; bool:<br>        return not self.stack_in and not self.stack_out<br><br>    def move_in_to_out(self):<br>        if not self.stack_out:<br>            while self.stack_in:<br>                self.stack_out.append(self.stack_in.pop())</pre><p><a href="https://leetcode.com/problems/number-of-digit-one/description/">https://leetcode.com/problems/number-of-digit-one/description/</a></p><p>Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.</p><p><strong>The Approach:</strong></p><p>The problem wants us to count how many times the digit 1 appears in all numbers from 0 to n. Checking every number from 0 to n and counting 1s manually would take too long. Instead lets use place-value analysis by going digit by digit in the given number. So for each digits place like ones, tens, hundreds, thousands, they contribute some number of 1s.</p><p>For the ones place, every 10 numbers has a 1 in the ones place once. So based on the tens place, which tells us how many full 10s there are, we can multiply by 1. Every full block of 100 contributes 10 1s in the tens place. In essence, we can count how many times 1 appears in that position by looking at the digit to the left of the current position, the current digit position and the lower digit to the right. By looking to the left, we can tell how many full cycles happened. By looking at the current digit, if its 0, there is no extra 1 beyond the cycles, if its 1, add the remainder + 1, if its greater than 1, add a full block of that digit place. By looking to the right, we can determine how much of the current block has passed.</p><p><strong>Next Steps:</strong></p><p>Lets initialize a variable to keep track of the number of 1s and another to keep track of which digit place we are looking at. Then loop through each digit place and count how many times the digit 1 appears at each digit place. For each place, split n into three parts, digits to the left of the current digit, the current digit and digits to the right of the current digit.</p><p>The digits to the left of the current digit are at the current place * 10 and using integer division will isolate the number to the left. The digit at the current place can be isolated using integer division by the current place to put the current digit in the ones place and using modulo 10 extracts that digit. To get the digits to the right of the current digit, use modulo by the current place to extract everything after the current digit place.</p><p>The digit to the left tells us how many full cycles of this digit we have seen. The current digit tells us the contribution of the digit at this place. The digits to the right tell us how far into the current cycle we have gone. Altogether we can calculate how many 1s appear at a digit place based on completed cycles, current digit contribution and partial progress into the current block.</p><p>If the current digit is 0, all the 1s come from the higher digits. If the current digit is 1, add all 1s from full cycles and the current partial from lower digits. If the current digit is greater than 1, we can treat it as another full cycle. Move to the next digit place by multiplying the current place by 10.</p><p><strong>The Solution:</strong></p><pre>class Solution:<br>    def countDigitOne(self, n: int) -&gt; int:<br>        count = 0<br>        place = 1  <br><br>        while place &lt;= n:<br>            high = n // (place * 10)<br>            curr = (n // place) % 10<br>            low = n % place<br><br>            if curr == 0:<br>                count += high * place<br>            elif curr == 1:<br>                count += high * place + (low + 1)<br>            else:<br>                count += (high + 1) * place<br><br>            place *= 10  <br><br>        return count</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0def1b178559" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>