<?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 Nathan Thomas on Medium]]></title>
        <description><![CDATA[Stories by Nathan Thomas on Medium]]></description>
        <link>https://medium.com/@nwthomas?source=rss-9a175cd0696f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*BBQlg8IH6i5HZQa0ZQLvgQ.jpeg</url>
            <title>Stories by Nathan Thomas on Medium</title>
            <link>https://medium.com/@nwthomas?source=rss-9a175cd0696f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 05:36:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@nwthomas/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[Detect Cycle in a Linked List (LeetCode #141)]]></title>
            <link>https://nwthomas.medium.com/detect-cycle-in-a-linked-list-leetcode-141-dd4d5444b6df?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/dd4d5444b6df</guid>
            <category><![CDATA[linked-list-cycle]]></category>
            <category><![CDATA[nathan-thomas]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Thu, 08 Dec 2022 19:25:54 GMT</pubDate>
            <atom:updated>2022-12-08T19:31:35.946Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SkpTNmtTTAGOJ2OqXhpdgQ.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@mischievous_penguins">Casey Horner</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/unique-paths-leetcode-62-b1f4c6fcc154"><em>Unique Paths</em></a><em> and </em><a href="https://medium.com/@nwthomas/reverse-a-linked-list-leetcode-206-62441622e652"><em>Reverse a Linked List</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/linked-list-cycle/">Detect a Cycle in a Linked List</a> problem, you’re in the right spot.</p><p>This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given the head to a singly linked list</li><li>We should detect if there is a cycle in it</li><li>The number of nodes in the list is in the range [0, 10^4]</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Initial Problem Setup 🏗</h3><p>This problem requires an understanding of how singly-linked list data structures work. If you want an in-depth explanation of that, check out my article on how to <a href="https://medium.com/@nwthomas/reverse-a-linked-list-leetcode-206-62441622e652">Reverse a Linked List</a>.</p><p>First off, we need to define a Node class (which LeetCode will actually give us) for the singly-linked list as well as handle the case where we aren’t passed a linked list at all (e.g. the value is None). This is possible according to the rules we reviewed above:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/566f9ed9e677c4227dd3685ee6b4aafc/href">https://medium.com/media/566f9ed9e677c4227dd3685ee6b4aafc/href</a></iframe><p>Next, we need to initialize two “runners” which will compete against each other to traverse this linked list (I promise I’ll explain more in just a second):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/27fd5f4214c5b66ea572ea5b85fd8d71/href">https://medium.com/media/27fd5f4214c5b66ea572ea5b85fd8d71/href</a></iframe><p>Next, we need to set up our while loop. I’m going to write some code here and then explain it to you, so read it and then we’ll walk through it together:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2a32122cc1d84831bb11ab00025f4814/href">https://medium.com/media/2a32122cc1d84831bb11ab00025f4814/href</a></iframe><p>The basic idea that we’re going for here is that we want the first runner to advance one node every iteration of our loop. At the same time, the second runner will advance at the pace of <em>two</em> nodes for every iteration. If the second ever passes the first, we know for a fact that it’s circled back on itself and we’ve detected a cycle.</p><p>We have set up our while loop to run as long as second.next is truthy (e.g. not None). The same goes for second.next.next. This will allow us to check two nodes ahead for the second runner every iteration of our loop.</p><p>Finally, I plopped an if statement down just inside the while loop that will check if second.next and second.next.next are equal to the first runner’s current node. If that’s the case, we return True since we’ve found the cycle we were talking about above.</p><p>If this if statement isn’t run, we need to update our pointers to move the two runners forward:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2719e141f229e35449d0573be57fa0ec/href">https://medium.com/media/2719e141f229e35449d0573be57fa0ec/href</a></iframe><p>We can safely update second to second.next.next here since our while loop logic already did the work of making sure they’re truthy (e.g. actual nodes).</p><p>Boom. There we go.</p><p>If we never hit the if statement clause and we run through the entire linked list, the while loop will end. In that scenario, we merely have a return statement at the end of the function that will return False.</p><p>This entire function will run in a time complexity of O(n) (since we’re iterating through the list approximately once) and a space complexity of O(1) (since we use a constant amount of variables in the problem no matter how long the linked list is).</p><h3>Conclusion</h3><p>Great job. How did it go? Did you feel like this one deserved the “easy” title on LeetCode?</p><p>Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-dev/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://www.nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dd4d5444b6df" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Reverse a Linked List (LeetCode #206)]]></title>
            <link>https://nwthomas.medium.com/reverse-a-linked-list-leetcode-206-62441622e652?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/62441622e652</guid>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Tue, 06 Dec 2022 19:40:52 GMT</pubDate>
            <atom:updated>2022-12-06T20:22:16.515Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BAam2_ReEYxOdk9M27WAnw.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@kar111">Karine Avetisyan</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/unique-paths-leetcode-62-b1f4c6fcc154"><em>Unique Paths</em></a><em> and </em><a href="https://medium.com/@nwthomas/meeting-rooms-leetcode-920-7e9d06f38a23"><em>Meeting Rooms</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/reverse-linked-list/">Reverse Linked List</a> problem, you’re in the right spot.</p><p>This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given the head of a singly-linked list (although the list might be empty)</li><li>We should reverse the list</li><li>We should return the reversed list</li></ol><p>If you haven’t worked with linked lists before as a data structure (or haven’t reversed one before), don’t worry. That’s why we’re here right now.</p><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>What is a Linked List? ⛓</h3><p>To start off with, let’s quickly review what a linked list data structure is (and specifically a singly-linked list). That basic understanding will let us understand how we can reverse it.</p><p>A linked list is really just a series of nodes that point to each other like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0sL5vcw1pj5nYpsfy7iUXA.png" /></figure><p>Each one of these nodes will have a value associated with it along with a pointer to the next node. If we were to write a class for this, it would look like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/388acba0ca70e4256b042f37067e252b/href">https://medium.com/media/388acba0ca70e4256b042f37067e252b/href</a></iframe><p>We could create a series of these nodes by instantiating one with a value, creating a second one with a value, and then assigning the first node’s next value to be the second node. We could repeat this as much as we want to create a “linked list” of nodes.</p><p>Makes sense? 🧠</p><p>I can hear what you’re thinking. You’re going, “Nate, why would you ever want to store value like this instead of in something like a <em>list</em> data structure??”</p><p>I like where your head is at. You <em>should</em> be asking those kinds of questions and trying to understand the <em>why</em> behind anything you learn.</p><p>Try stopping for a minute and thinking about how lists work. You can easily add to the end of one (via the push method) in O(1) time. If you add to the start, you might think that it’s O(1) time as well; it’s actually O(n) time since the list has to re-index every value in the list when you add to the start of it.</p><p>Additionally, you have to search through the <em>entire </em>list in order to find a specific value to replace (unless you already know the index). If you add or remove a value in the middle of the list, you’ll have to go through the entire re-indexing process again (potentially in O(n) time).</p><p>With linked lists, you can add (to either the start or the end) and remove values at <em>any</em> point in the list in O(1) time because you’re just updating pointers to nodes. It will never re-index because each node is a self-contained unit that merely has a pointer <em>reference</em> to the next node.</p><p>It’s worth noting here that the data structure we just discussed above is a <em>singly</em>-linked list. The difference is that a <em>doubly</em>-linked list would also have a pointer back to the <em>previous</em> node, not just one pointing to the next one like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NJVr0JpiclhAP7n7OezPTw.png" /></figure><p>We’d write the code for that like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5fb3e423c1966272605ec32ad91e663c/href">https://medium.com/media/5fb3e423c1966272605ec32ad91e663c/href</a></iframe><p>This would allow us to traverse forwards <em>and</em> backwards and be much more useful in the real world. However, we’ll only be using singly-linked lists today because that’s a requirement of the problem we’re looking at.</p><p>If this all doesn’t make sense yet, we can jump into actually completing the problem and it will hopefully become really clear in a second!</p><h3>Reversing Our Linked List 🔄</h3><p>Now that we’ve reviewed how linked lists work, we can get into actually reversing one!</p><p>First, let’s go ahead and set up our initial variables:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5334c3779c07180484a783da751a0b5c/href">https://medium.com/media/5334c3779c07180484a783da751a0b5c/href</a></iframe><p>First off, we have to check if head does not exist. This is because the problem states that the singly-linked list we’re given might be empty.</p><p>Next, we have to track the prev_node, current_node, and next_node.</p><p>We’ll iteratively use these with a while loop (which we’ll set up soon) in order to reverse out list. Notice that we start prev_node with a value of None. This is because the last node in our singly linked list points to None. If we’re going to reverse the list, our head node will need to point to None (since it’s going to be the end of this list once we’re done).</p><p>Here’s what we need to add next:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/293b1f840cf95e6dc61ae22cbffc7403/href">https://medium.com/media/293b1f840cf95e6dc61ae22cbffc7403/href</a></iframe><p>First, our loop won’t work unless we do a quick assignment:</p><pre>current_node.next = prev_node</pre><p>This initializes our current_node.next value (which is the head value root node here) with None as its value. We’ve already preserved current_node.next’s old value in the variable next_node.</p><p>Nice.</p><p>Next, we setup our while loop to run as long as next_node is truthy (not None). This means our loop will keep running until the last node in the current version of the list has a next value of None.</p><p>Now that this is setup, all that’s left for us to do is write some quick reversal logic inside our while loop:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ac483164f9885317b67c66d7666162ec/href">https://medium.com/media/ac483164f9885317b67c66d7666162ec/href</a></iframe><p>Boom.</p><p>Notice that, for each iteration of our loop, we’re bumping the current_node value back to prev_node, bumping the next_node value to be assigned to current_node, setting next_node to be the current_node.next&#39;s value, and finally doing the same pointer switch of the current_node&#39;s next pointer so that it points at the prev_node.</p><p>Once we’re done, we’ll be at the last node (which is now pointing in reverse back down our reversed singly-linked list). This has become our new root node. We can simply return this at the end of the function.</p><p>This entire problem will run in O(n) time complexity (since we’re iterating through the list once) and O(1) space complexity (since we’re only using a constant number of variables to reverse the singly linked list no matter how long it is).</p><h3>Conclusion</h3><p>Great job. How did it go? Did you feel like this one deserved the “easy” title on LeetCode?</p><p>Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-dev/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://www.nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=62441622e652" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Meeting Rooms (LeetCode #920)]]></title>
            <link>https://nwthomas.medium.com/meeting-rooms-leetcode-920-7e9d06f38a23?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/7e9d06f38a23</guid>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Mon, 05 Dec 2022 19:14:14 GMT</pubDate>
            <atom:updated>2022-12-05T19:14:14.848Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VD32si7vq-VyMvRnb1CAHA.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@socialcut">Social Cut</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/unique-paths-leetcode-62-b1f4c6fcc154"><em>Unique Paths</em></a><em> and </em><a href="https://medium.com/@nwthomas/insert-interval-leetcode-57-d3f7aadcca1"><em>Insert Interval</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/meeting-rooms/">Meeting Rooms</a> problem (it’s a LeetCode premium article, so here’s a <a href="https://www.lintcode.com/problem/920/">LintCode link</a> to get around that), you’re in the right spot.</p><p>This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started! 🙌🏻</p><h3>Understanding the Problem 🕵🏻‍️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given a list of intervals (such as [0, 15]) where the first number is the start time and the last number is the end time</li><li>This list of intervals will be sorted by ascending order of the start times</li><li>We need to check if our person can attend all meetings by seeing if any intervals overlap</li><li>If they overlap, we should return False — if not, we should return True</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>General Approach 🎖</h3><p>While this problem might seem rough at first glance, it turns out that this problem is <em>extremely</em> straightforward.</p><p>It turns out the only thing we really need to do is check each successive interval to see if its start time comes before the previous interval’s end time. That’s it. That’s the solution!</p><p>First, we need to write a for loop like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c8a6a6ba1ae4f6f532d51238abce8a6a/href">https://medium.com/media/c8a6a6ba1ae4f6f532d51238abce8a6a/href</a></iframe><p>We’re going to use the enumerate function in Python because it gives us access to <em>both</em> the index i as well as the value itself (which I’ve named interval).</p><p>Next, we need to check each interval and compare it against the last one. Here’s what that looks like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a545a403caa965b85585ea366043827/href">https://medium.com/media/5a545a403caa965b85585ea366043827/href</a></iframe><p>Whoa. Wait a minute. What’s going on here?</p><p>First, we’re pulling out the start value from the current interval value (which would be something like [10, 34]). We don’t need the end value, so I used the _ underscore character which most coding languages (including Python) understand to mean you <em>don’t</em> want to use it but need to include it in order for the destructuring of values off interval to work.</p><p>Next, I wrote an if statement to check if index i is greater than 0. We only want to compare intervals if we have a previous one to compare against, right? This means we only want our if statement to run if the index is at least 1.</p><p>Finally, I added syntax to the if statement to check that the current interval&#39;s start value was less than the previous interval&#39;s end value. If this is the case, we can return False. This means that we have found overlapping meeting room times.</p><p>If this entire for loop runs over the intervals list without ever returning False, we can know that none of our intervals list has overlapping values. In this case, we can just return True at the end of the function.</p><p>That’s it! That’s all it takes! Here it is again if you want to read it:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a545a403caa965b85585ea366043827/href">https://medium.com/media/5a545a403caa965b85585ea366043827/href</a></iframe><p>This entire solution will run in O(n) time complexity (because we’re iterating through the entire list once) and O(1) space complexity (since we’re using a constant number of variables/memory to solve the problem no matter the length of the intervals list that’s passed in).</p><h3>Conclusion</h3><p>Great job. How did it go? Did you feel like this one deserved the “easy” title on LeetCode?</p><p>Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-dev/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://www.nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7e9d06f38a23" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Insert Interval (LeetCode #57)]]></title>
            <link>https://nwthomas.medium.com/insert-interval-leetcode-57-d3f7aadcca1?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/d3f7aadcca1</guid>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Tue, 01 Nov 2022 18:14:19 GMT</pubDate>
            <atom:updated>2022-11-01T18:14:19.344Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*a6kXvdebcoEbQc4ukltfRQ.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@lastnameeaster">La-Rel Easter</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/unique-paths-leetcode-62-b1f4c6fcc154"><em>Unique Paths</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/insert-interval/">Insert Interval</a> problem, you’re in the right spot.</p><p>This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started! 🙌🏻</p><h3>Understanding the Problem 🕵🏻‍️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given a list of non-overlapping intervals called intervals</li><li>These intervals will have the shape of [start, end] with each of these values being an integer of 0 &lt;= start &lt;= end &lt;= 105</li><li>The intervals list will be length of 0 &lt;= intervals.length &lt;= 104</li><li>We’ll also be given a new interval that we should insert into the intervals list, merging it with others if needed</li><li>We should merge existing intervals as well if they overlap</li><li>The existing intervals list will be sorted by start in ascending order</li><li>We should return this merged intervals list when we’re done</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Initial Problem Setup 🏗</h3><p>This problem extends the popular <a href="https://leetcode.com/problems/merge-intervals/">Merge Intervals</a> problem with a new variation— in addition to merging intervals in a list that we’re given, we also need to insert a single additional new interval into the list as well.</p><p>This sounds complicated, and I’ll be real with you that it melted my brain a little bit the first time I did this one.</p><p>The first thing we need to do is set up our initial values. Additionally, the intervals list can be empty. If this is the case, we can just return the new_interval (which will always be defined). Here’s what this initial code looks like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/33de41129b5388e075f7353e64c556d8/href">https://medium.com/media/33de41129b5388e075f7353e64c556d8/href</a></iframe><p>There’s our early return.</p><p>Next, we have an initialized output list that will end up holding our merge intervals. We can also destructure out the two values of new_interval once here and have them available for the rest of the problem when we do comparisons.</p><p>Finally, we have a boolean flag inserted to track if we’ve used the new_interval already.</p><p>Nice. I think we’re ready to get into some of the harder stuff.</p><p>Let’s do it. 🔥</p><h3>Decision Trees and Intervals 🌲</h3><p>First, we’re going to iterate over all of our intervals list:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ae36a0a2534d54325aad2f0ed22cabf2/href">https://medium.com/media/ae36a0a2534d54325aad2f0ed22cabf2/href</a></iframe><p>For each current_interval here, we’re going to destructure off its current_start and current_end which the rules of the problem say will always be defined.</p><p>Next, we need to build a decision tree off the following rules:</p><ol><li>We need to handle if we haven’t put any intervals into our output yet and the end of the new interval is less than the start of the current one</li><li>We need to handle if we have put intervals already into output and the last interval there overlaps with the current one</li><li>If neither of those cases are true, we want to just append the current variable to our output list</li></ol><p>Here’s what this will look like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7d7020c75af0ce4030c5b26967dfd8cf/href">https://medium.com/media/7d7020c75af0ce4030c5b26967dfd8cf/href</a></iframe><p>We’re not done though. We need one more if statement that will always run after this decision tree.</p><p>You see, we’ve handle the cases where the new interval is first and not merged, when an existing interval is present and we merge, and when we just need to push the current_interval to the output list.</p><p>However, we separately always need to check if we still need to insert the interval and, if the output list has length, compare the last output interval’s ending to the new_start value of the new_interval.</p><p>Let’s add that:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/20e25be8450ddea6b3fce373c5fe2ae0/href">https://medium.com/media/20e25be8450ddea6b3fce373c5fe2ae0/href</a></iframe><p>Ugh. I know that was a lot to take in.</p><p>Essentially, all this last if statement is doing is merging the new_interval with an existing interval if they overlap. That’s it. It’s just a lot of code.</p><p>Before returning our output, we should add the new_interval to the end of output if we never ended up inserting/merging it in the for loop.</p><p>Finally, we just return the output list.</p><p>This whole thing will run in O(n) time complexity and O(n) space complexity (due to the new output list).</p><h3>Conclusion</h3><p>Good job. You made it. What did you think? Was it easier or harder to understand than you expected?</p><p>Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-dev/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://www.nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d3f7aadcca1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Unique Paths (LeetCode #62)]]></title>
            <link>https://nwthomas.medium.com/unique-paths-leetcode-62-b1f4c6fcc154?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/b1f4c6fcc154</guid>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding-challenge]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Sat, 29 Oct 2022 21:00:24 GMT</pubDate>
            <atom:updated>2022-11-01T16:44:25.252Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z0OiiuzqtnOIVeTxjEeT8Q.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@phillipglickman">Philip Glickman</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/merge-k-sorted-lists-leetcode-23-9537d3257dca"><em>Merge K Sorted Lists</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/unique-paths/">Unique Paths</a> problem, you’re in the right spot.</p><p>This is a question in the <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 LeetCode code challenge list</a>, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We have a robot on an m x n grid</li><li>The robot is initially located on the top-left corner of our grid and it needs to move to the bottom-right corner</li><li>The robot can move either right or down at any point in time</li><li>We must return the total number of unique paths that the robot can take to reach the bottom-right corner</li><li>m and n for the grid size will each be within 1 &lt;= n, m &lt;= 100</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Initial Problem Setup 🏗</h3><p>This is yet another dynamic programming problem. I know these can be a little shifty to work with, so we’ll take it slow and I’ll explain each step.</p><p>The real key to this problem is to realize that, since the robot can either move right or down each time, we basically need to count each move right or down as a <em>unique </em>combination.</p><p>For instance, here’s the example image used in the LeetCode challenge:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*UO4JvdwGUH_D1T-h5Zhspg.png" /></figure><p>If we were to move right from where the robot is at the start, that is one unique path so far. Simultaneously, moving down from the start is a second unique path so far. from each of those spots, moving right or down is an additional two unique paths so far.</p><p>See where I’m going with this?</p><p>What if we were to iterate over the entire grid cell by cell and, for every one, add the top cell and the previous cell to count the unique ways so far that we’ve reached the <em>current </em>cell?</p><p>If we did that, we’d eventually find ourselves at the finish with a total that reflects the number of unique ways we’ve moved right or down to reach that point.</p><p>Let’s set up the initial foundation of the problem, and it will make more sense as we continue.</p><p>First, let’s set up our cache:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/10f2103d38512dafcfcaceb641e39d8e/href">https://medium.com/media/10f2103d38512dafcfcaceb641e39d8e/href</a></iframe><p>Notice that we’re initializing the starting space with a value of 1 (key-ed in our dictionary by (0, 0)). This is because dynamic programming problems often require some base seed value that will be used as a foundation to progressively build upon. When we first move right or down, those cells will reference this (0, 0) position. All other cells will continue to build up from there.</p><p>Next, we need to set up our nested loops to traverse our m x n matrix:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3182e22fb65c005178e23d0d0812dfff/href">https://medium.com/media/3182e22fb65c005178e23d0d0812dfff/href</a></iframe><p>Nice. We’re ready to write the core logic of our problem.</p><p>Let’s get into it! 🤘🏻</p><h3>Iterate, Cache, Iterate 🔁</h3><p>First, we need to initialize a variable to track the current_total_ways. We’ll add to this as we move through our logic:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5fd4cc78c6739e03788a44b1d97bf384/href">https://medium.com/media/5fd4cc78c6739e03788a44b1d97bf384/href</a></iframe><p>Next, we’ll have a series of if statements:</p><ol><li>Check if the cell above exists (since we’re moving down from it) and add it to current_total_ways if it does</li><li>Check if the cell to the left exists (since we’re moving right from it) and add it to current_total_ways if it does</li><li>Check whether or not the current cell exists in the cache (guarding against overwriting the base (0, 0) case) and create it with a value of 0 if not</li></ol><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d144298cb537ba86cf5581ce434247bf/href">https://medium.com/media/d144298cb537ba86cf5581ce434247bf/href</a></iframe><p>Nice. The next thing we need to do is add the outcome of current_total_ways to the cache as long as it’s greater than the current cached value of the (x, y) position (if it exists):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/342e938afbee7912f398abd0870c4356/href">https://medium.com/media/342e938afbee7912f398abd0870c4356/href</a></iframe><p>This will allow other cells to access this value later as we iterate.</p><p>The max comparison is really just to avoid overwriting the seed value at (0, 0) when we start our loops. This allows us to avoid a bit of extra logic.</p><p>Finally, we need to return the bottom-right cell in the matrix. This will have our final answer to the problem!</p><p>Believe it or not, this is the complete solution. That wasn’t too bad, right?</p><p>This entire solution will run in O(m * n) space and time complexity as we’re using a matrix in memory and running a nested loop over the original matrix.</p><h3>Conclusion</h3><p>Good job. You made it. What did you think? Was it easier or harder to understand than you expected?</p><p>Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-dev/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://www.nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b1f4c6fcc154" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Merge K Sorted Lists (LeetCode #23)]]></title>
            <link>https://nwthomas.medium.com/merge-k-sorted-lists-leetcode-23-9537d3257dca?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/9537d3257dca</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[coding-challenge]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[heap]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Fri, 28 Oct 2022 18:00:06 GMT</pubDate>
            <atom:updated>2022-10-28T18:00:06.339Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1010/1*H6jxykghJEWOOfmef-fLpA.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@tomas_nz">Tomas Sobek</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/course-schedule-leetcode-209-c935644e1e20"><em>Course Schedule</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/merge-k-sorted-lists/">Merge K Sorted Lists</a> problem, you’re in the right spot.</p><p>This is a question in the <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 LeetCode code challenge list</a>, a group of questions put together by a tech lead at Facebook that’s been touted as a <em>great </em>way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍♂️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given a variable-length list of singly-linked lists called lists</li><li>The length of lists will be 0 &lt;= len(lists) &lt;= 10^4</li><li>Each list will have been sorted in ascending order</li><li>We should merge the linked lists into one sorted linked list and return it</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Understanding Heaps 📚</h3><p>It turns out that this entire problem hinges on knowing what Heaps are and how to use them (or at least, <em>my</em> solution uses them extensively). If you don’t know what the Heap data structure is, you can <a href="https://www.geeksforgeeks.org/heap-data-structure/">learn about them right here</a>.</p><p>The TLDR is that they allow you to use an ordinary list (e.g. [1, 2, 3, 4, 5] or some other set of values) to insert, order, and retrieve values in O(log n) time (that’s the time complexity for inserts and retrievals).</p><p>The reason a Heap can achieve this level of speed is because they utilize a <a href="https://www.geeksforgeeks.org/binary-search/">Binary Search</a> pattern to store data in the list. For instance, let’s say I add the number 5 to the list. Here’s what we’ll start with:</p><pre>heap = [5]</pre><p>Not too much going on here yet, right?</p><p>Next, we’ll add 6 to the list. Under the hood, this is what the data structure looks like:</p><pre>heap = [5, None, 6]</pre><p>Wait. What? Why does it look like that?</p><p>Start looking at this list as a <a href="https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/">Tree data structure</a>. The number 5 is the root at the 0 index, its lefthand child is empty (or None) at the index 1, and its righthand child node has the value of 6 at index 2. Makes sense, right?</p><p>Is there a pattern for this?</p><p>There is. It turns out we can find out the indices for any given “node” in our list by multiplying the current index by 2 and then adding 1 for the lefthand child and 2 for the righthand child.</p><p>For the heap in the example above, this means that:</p><pre>heap = [5, None, 6]<br>        ^  ^     ^<br>Index:  0  1     2</pre><pre>Children of root node at index 0:<br>- Left child is 0 (root index) * 2 + 1 (left child) = 1<br>- Right child is 0 (root index) * 2 + 2 (right child) = 1</pre><p>This rule holds true for any new values we add. For instance, let’s add 10 to the heap:</p><pre>heap = [5, None, 6, None, None, None, 10]</pre><p>Try doing the mental calculation here as to why we placed 10 in this spot.</p><p>I’ll wait.</p><p>That’s right. We move down the righthand side of our pseudo-tree structure until we get to 6. Once there, we know we’d want to make a child node under it on the righthand size.</p><p>If we were storing this in an actual <a href="https://www.geeksforgeeks.org/binary-search-tree-data-structure/">Binary Search Tree</a>, this is how it would look:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*92BTu5IHYhBN2C-ZB6SQhA.png" /></figure><p>This is how we got the calculations on where to place the value 10 in our heap:</p><pre>2 (index of value 6) * 2 + 2 (new child is on righthand size)</pre><pre>= 6 (new index of child)</pre><p>Any index positions in between will be filled with None.</p><p>If we wanted to remove something from our heap, we should pop off the root (value 5 in the example above). At this point, our heap would look like this:</p><pre>heap = [None, None, 6, None, None, None, 10]</pre><p>From here, the heap logic will bubble up the next minimum values one at a time (in log(n) time) until our heap look like this:</p><pre>heap = [6, None, 10]</pre><p>Makes sense, right? We’ve kept our binary search structure but just bubbled up values until the next minimum value (currently 6) is the root value.</p><p>We can now search up and down our heap the same way we’d search any other binary tree.</p><p>Heaps are very powerful and would make a great article all on their own, but this is probably enough understanding for us to get started with solving the problem!</p><h3>Initial Problem Setup 🏗</h3><p>While it’s possible to <a href="https://github.com/nwthomas/data-structures-and-algorithms/blob/master/data_structures/heap/max_binary_heap/maxBinaryHeap.js">write a Heap implementation from scratch</a> (note that this link is one I did in JavaScript), that’s honestly for another day. Python as a language has a <a href="https://docs.python.org/3/library/heapq.html">Heap implementation called heapq</a> that we can use just by importing it.</p><p>Let’s go ahead and import the functions we need for this, and then I’ll explain what they do:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2efae998180fd66955e71a0f5ddb5a34/href">https://medium.com/media/2efae998180fd66955e71a0f5ddb5a34/href</a></iframe><p>There’s quite a bit already going on here, so let’s take it one step at a time:</p><ol><li>First, we’re importing heappop and heappush from the heap implementation in Python called heapq. heappush adds a new value to the heap and sorts it relative to the other values in log n time and heappop removes a value and sorts remaining values in log n time.</li><li>Next, we have a definition of a ListNode class that LeetCode provides to us. This is so we know what the incoming lists look like and also to use to create final nodes in the merged list we will return.</li><li>Finally, we have the start of our merge_k_lists function. We have lists coming in (which is a list of singly-linked lists) and the initial definition of our heap.</li></ol><p>Nice 🤌🏻</p><p>Let’s go ahead and start adding our values from each list.</p><h3>Adding Lists to the Heap 📚</h3><p>Believe it or not, this part is going to be fairly straightforward. All we need to do is iterate through every list, traverse every list, and heappush each value into our heap-ified list. Our heap will sort everything for us.</p><p>Here’s what that will look like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/36a93304064089ea42f1215cf8b4595b/href">https://medium.com/media/36a93304064089ea42f1215cf8b4595b/href</a></iframe><p>We’re essentially starting at each root node for each list (which we assign to current in the code above), use heappush to put that node’s value into the heap, set current to be current.next, and keep continuing that until our current value is None. We then progress on to the other lists and repeat this process until we’re done.</p><p>That’s it! Due to the awesome sorting properties of the heap data structure, we have the minimum value at the top of the heap when we’re done.</p><p>This allows us to start in on the final part of the problem — creating our new, merged list. 🔥</p><h3>Creating Our Sorted Linked List 🖇</h3><p>The very next thing we need to do is to check if heap is empty. This might happen if we’re given an empty lists argument (e.g. we don’t have any lists to merge).</p><p>We can check with a simple if statement:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a0013714806bded81ecbcafb77f39fde/href">https://medium.com/media/a0013714806bded81ecbcafb77f39fde/href</a></iframe><p>Right on.</p><p>Now, we just need to basically do the reverse of our first loop; we can create a new root node and then progressively heappop values off our heap to add them to a new singly-linked list until we have no more values left.</p><p>Here’s what that will look like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/73eedb47fe32fe8a76a5607610582a29/href">https://medium.com/media/73eedb47fe32fe8a76a5607610582a29/href</a></iframe><p>First, we instantiate a new ListNode and pass the result of heappop(heap) into it as the first value (which is the current minimum value in our heap, removed in O(log n) time). This is assigned to a new new_root value that will ultimately be our returned root node.</p><p>Next, we create a new current variable which we assign the value of new_root to.</p><p>Next, we create a while loop that will run for as long as our heap has length (e.g. has values in it).</p><p>Finally, we create a new node inside our loop for every value we heappop off, assign that to the current.next&#39;s value, and then update current to be this new node.</p><p>Once the heap is empty and our loop is complete, we’re done!</p><p>BOOM. ✅</p><p>How does it feel to have solved the problem?</p><p>This solution will run in a total time complexity of O(n log n) where n is the total length of all lists in the lists parameter. This is because we iterate over every value (the first n pass) and then insert/remove them (in log n time due to us using a heap).</p><p>The space complexity is O(n) where n is the total length of all lists in the lists parameter.</p><h3>Conclusion</h3><p>Nice work. We got through our first hard LeetCode problem together. That wasn’t so bad, was it?</p><p>Keep an eye out for the rest of these <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 coding challenges</a> articles. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-dev/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9537d3257dca" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Course Schedule (LeetCode #209)]]></title>
            <link>https://nwthomas.medium.com/course-schedule-leetcode-209-c935644e1e20?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/c935644e1e20</guid>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[coding-challenge]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Tue, 30 Aug 2022 22:03:19 GMT</pubDate>
            <atom:updated>2022-08-30T22:03:19.688Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*K0LMciWUgV0dqEHC9WTgkw.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@neonbrand">Kenny Eliason</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/implement-trie-leetcode-208-e99c00b7acca"><em>Implement Trie</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/course-schedule/">Course Schedule</a> problem, you’re in the right spot.</p><p>This is a question in the <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 LeetCode code challenge list</a>, a group of questions put together by a tech lead at Facebook that’s been touted as a <em>great </em>way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍♂️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given a numCourses integer that represents the total courses available to take</li><li>We’ll be given a list of prerequisites of [a, b] where b is the course that needs to be taken before a</li><li>We should return True if all courses can be taken given the prerequisites or return False if they can’t</li><li>numCourses will be 1 &lt;= numCourses &lt;= 2000</li><li>The length of prerequisites will be 0 &lt;= len(prerequisites) &lt;= 5000</li><li>Each value within prerequisites will be a list of length 2 with two integers in it representing two courses</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Initial Setup 🏗</h3><p>This is the second graph problem I’ve covered in my articles (the first being <a href="https://medium.com/@nwthomas/clone-graph-leetcode-133-144ebcecd985">Clone Graph</a>), but it’s the first one where we <em>really </em>get into some interesting traversal work.</p><p>We’re going to be doing a depth-first search traversal of our graph while caching outcomes along the way. This will enable us to only traverse each node’s prerequisites once and then reuse the results thereafter.</p><p>The first bit of setup we need to do is to map our courses to all prerequisites.</p><p>We can do that by first defining an int to list setup in a dictionary for every course from 0 up to (but not including) numCourses. This is because our courses in our prerequisites list are zero-indexed.</p><p>This is what that looks like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/05170a54ac29b9f0abac972b94c1abd0/href">https://medium.com/media/05170a54ac29b9f0abac972b94c1abd0/href</a></iframe><p>This will produce a dictionary that looks something like this:</p><pre>{ 0: [], 1: [], 2: [], ... on up to num_courses - 1 }</pre><p>From here, we need to initialize an empty cache dictionary and also populate our courses_to_prereqs dictionary with data:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/374d87c574e9661b4bd29406b298c9dd/href">https://medium.com/media/374d87c574e9661b4bd29406b298c9dd/href</a></iframe><p>The for loop iterates through prerequisites and, for every pair of a [course, prereq], pushes the prereq to the list for that course in courses_to_prerequisites.</p><p>For instances, a list of prerequisites like this:</p><pre>prerequisites = [[0, 1], [2, 1]]</pre><p>will not have a courses_to_prerequisites dictionary that looks like:</p><pre>courses_to_prerequisites = {<br>  0: [1],<br>  1: [],<br>  2: [1],<br>}</pre><p>From here, the next step is to set up our depth-first search traversal function!</p><p>Let’s get to it! 🔥</p><h3>Setting Up Our Function 🌀</h3><p>The first thing we need to do is to initialize a new function. We’ll call ours dfs_traversal:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/96c59625e79dfa36ad19e811c11edaf7/href">https://medium.com/media/96c59625e79dfa36ad19e811c11edaf7/href</a></iframe><p>The first thing we need to write inside our function are two quick exit cases.</p><ol><li>We need to exit if the course is already stored in cache (and return its value)</li><li>We need to exist if the length of the current course&#39;s course_to_prerequisites list is length 0 (and return True since the current course has no prerequisites and therefore is automatically possible to take)</li></ol><p>This is what these exit cases look like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/90888913c385ae7e5b01f4f3fd40d15b/href">https://medium.com/media/90888913c385ae7e5b01f4f3fd40d15b/href</a></iframe><p>Next, we’re going to pre-populate our course value in cache to be False in case we exist early in the loop we’re about to write (you’ll see why in a second):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/234b440a2b335b997ae16ee9b24049d5/href">https://medium.com/media/234b440a2b335b997ae16ee9b24049d5/href</a></iframe><p>This will also keep us safe if we get ourselves into a recursive situation (e.g. 0 has a prerequisite of 1 and 1 has a prerequisite of 0).</p><p>After this, we can write a new for loop that will, for every prerequisite for the course (using data we’ve built in courses_to_prereqs), call dfs_traversal:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/daf39dc6ed8fffdeebda130ace85fa78/href">https://medium.com/media/daf39dc6ed8fffdeebda130ace85fa78/href</a></iframe><p>Each time, we’ll call dfs_traversal which adds to the call stack and traverses down deeper into the graph of prerequisites.</p><p>When this call does return, we’ll instantly return False if that’s the value we received (as there’s no point in continually calling more of the other prerequisites — we know this course’s prerequisite can’t be taken).</p><p>Otherwise, we continue with our loop.</p><p>When it’s done, this means that we traversed all the prerequisites and none of them returned False.</p><p>We can now set the cache value for the course to True. After that, we can just return True:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/10db4528d268a21b5d9f285bdc29144f/href">https://medium.com/media/10db4528d268a21b5d9f285bdc29144f/href</a></iframe><p>All that’s left for us to do is to write a loop that, for every course in courses_to_prerequisites, calls dfs_traversal.</p><p>If we get a False returned value at any point, we know the entire course structure is wrong.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/286ea337b60aaa209717e1559bb73425/href">https://medium.com/media/286ea337b60aaa209717e1559bb73425/href</a></iframe><p>At the very end, we can honestly just return True. We’ve fulfilled all the requirements for the course schedule and nothing has returned False. We’re done!</p><p>This algorithm will run in O(V + E) time where V is the number of vertices (courses) and E is the number of edges (connections to prerequisites). We only need to visit each course once before it’s cached.</p><p>The space complexity is also O(V + E).</p><h3>Conclusion</h3><p>Great job. Graph problems can be tough, but you made it. 🙌🏻</p><p>Keep an eye out for the rest of these <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 coding challenges</a> articles. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-profile/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c935644e1e20" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implement Trie (LeetCode #208)]]></title>
            <link>https://nwthomas.medium.com/implement-trie-leetcode-208-e99c00b7acca?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/e99c00b7acca</guid>
            <category><![CDATA[coding-challenge]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Mon, 29 Aug 2022 18:56:25 GMT</pubDate>
            <atom:updated>2022-08-29T19:27:27.592Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xqg8wDOSuZykkC_cypMl_g.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@maritafox">Maria Kavelashvili</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/jump-game-leetcode-55-8db45b80f949"><em>Jump Game</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/implement-trie-prefix-tree/">Implement Trie</a> problem, you’re in the right spot.</p><p>This is a question in the <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 LeetCode code challenge list</a>, a group of questions put together by a tech lead at Facebook that’s been touted as a <em>great </em>way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍♂️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’re supposed to implement a Trie (which is pronounced as “try”) or “prefix tree” (if you want to read up on what it is, read the introduction for <a href="https://en.wikipedia.org/wiki/Trie">this Wikipedia link</a>)</li><li>We should build the following functionality for it:</li></ol><ul><li>Trie() instantiates the trie object</li><li>insert(word: str) inserts the word into the Trie</li><li>search(word: str) returns True if the word exists or False otherwise</li><li>startsWith(prefix: str) returns True if there is a previously-inserted word in the Trie which the prefix prefix or False otherwise</li></ul><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Initial Problem Setup 🏗</h3><p>If you’ve seen a Tree data structure before, you’re just a hop/skip/jump away from learning what a Trie is (and if you haven’t, read the introduction on <a href="https://en.wikipedia.org/wiki/Tree_(data_structure)">this Wikipedia page</a>).</p><p>It turns out that a Trie is very, very similar to a Tree. The key difference is that a Trie can have <em>many</em> children for each node whereas the Tree can only have two (a left and a right).</p><p>In a Trie, each node may contain many children that each represent another character in a chain that you are building. In the Trie below that I’ve written for you, you can see that there are multiple words contained in it if you start from Root and then progressively move down the nodes one-by-one:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O6t655D8rRM1LmzJu-g35w.png" /></figure><p>In the Trie above, we can search through the nodes progressively to check if a word is contained in it.</p><p>For instance, searching the Trie above for “TREE” would return a true boolean:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nE2bahDA7vyvPaynPvnSrQ.png" /></figure><p>Because of this, Tries are a powerful way to solve problems that involve words and word prefixes.</p><p>For our problem, the first things we need to do for our initial setup are to:</p><ol><li>Define a Node class for each of the nodes (like in the diagram above)</li><li>Build the actual Trie&#39;s constructor to handle instantiating a new Trie</li></ol><p>To start off with, we’ll define the Node class so that it has a constructor with a value, children dictionary, and word_totals value (more on that later):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8c3f1590075755dde7497bdf2ab9cde7/href">https://medium.com/media/8c3f1590075755dde7497bdf2ab9cde7/href</a></iframe><p>Next, we’ll create a class called Trie that has a constructor. In that constructor, we’ll merely instantiate a root node that has a value of None:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ff8c36221440491516f6887959c64d09/href">https://medium.com/media/ff8c36221440491516f6887959c64d09/href</a></iframe><p>This is typical for a Trie; we never have a value from the root node, and the children of the root node are the first letter in any words that might exist in the Trie.</p><p>From here, we’re ready to fill out our three methods!</p><p>Let’s do it. 💪🏻</p><h3>Building the Insert Method</h3><p>The insert method will look very familiar to you if you’ve ever had to build out methods to parse through a Binary Search Tree (BST). The big difference here is that we don’t have left or right values. We’re looking in a children dictionary each time we arrive at a new node.</p><p>First, let’s create a variable called current and initialize it with self.root from the Trie:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/298641adf2f47afa0ca8cd7e34bdbccb/href">https://medium.com/media/298641adf2f47afa0ca8cd7e34bdbccb/href</a></iframe><p>We’ve also set up a variable called word_index that allows us to independently track what the current index of the word is that we’re looking for.</p><p>Next, we’ll build out a while loop that runs for as long as word_index is less than the length of word. Inside this, we’ll check for every node we visit if the word[word_index] current exists in that node’s children and then create it as a new node if it doesn’t:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/15b86fc355042d7d57edeb78a3e9eff6/href">https://medium.com/media/15b86fc355042d7d57edeb78a3e9eff6/href</a></iframe><p>This means that we’ll get to reuse a node if it exists or create it otherwise.</p><p>Nice 🎉</p><p>Next, we should update current to be this either pre-existing or newly-created node:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bfb1d78ba388fc01e7260172b6837290/href">https://medium.com/media/bfb1d78ba388fc01e7260172b6837290/href</a></iframe><p>Notice that we’re also incrementing word_index here as well.</p><p>Finally, the last thing we did up there at the end of our code was to increment the word_totals for the last node; this is to recognize that we’ve added one word to the Trie that ends in this node.</p><p>This will be useful for us very soon.</p><p>Our insert method runs in O(n) time (where n is the number of characters in word) and has O(1) space complexity (due to only needing a current and word_index pair of variables).</p><h3>Building the Search Method</h3><p>If you read through every step of the insert method above, the search one is going to look largely the same to you.</p><p>First, we do our variable setup and construct the start of our while loop:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1963672e9b16558fac1e89ff729f0651/href">https://medium.com/media/1963672e9b16558fac1e89ff729f0651/href</a></iframe><p>Notice that we’re merely returning False if we hit a case where a word[word_index] character value does not exist in the current.children dictionary.</p><p>Next, we should do the same updates to current on every loop as well as incrementing word_index:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8523ddbecafcaa3b7de41b6189bd493c/href">https://medium.com/media/8523ddbecafcaa3b7de41b6189bd493c/href</a></iframe><p>The only big thing here that differs from what we saw in the insert method is the return statement at the end.</p><p>We’re checking if the word_totals (which we incremented at the end of the insert statement if a word had finished being inserted on that node) is greater than 0 (which means there is a word present there).</p><p>Our search method runs in O(n) time (where n is the number of characters in word) and has O(1) space complexity (due to only needing a current and word_index pair of variables).</p><p>Cool!</p><p>That’s two methods down. Ready for the last one? 🚀</p><h3>Building the SearchWith Method</h3><p>This one is where the real money lies with this coding challenge. We’re going to have to pull out the old <a href="https://en.wikipedia.org/wiki/Depth-first_search">Depth First Search</a> to make it happen.</p><p>We’ll start off our startsWith method in the <em>exact</em> same way as the search method. In fact, I’ll just plop the code down since it’s 100% the same:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ccc32b2cd8277cfbecda34cce2673bd5/href">https://medium.com/media/ccc32b2cd8277cfbecda34cce2673bd5/href</a></iframe><p>Look familiar? 🤔</p><p>However, this is where the similarities cease. We can only use this part of our Trie traversal up until the end of the prefix. The whole point is that we should find if <em>any</em> words exist that start with this prefix.</p><p>This means that we have to roll up our sleeves and start searching through the remaining nodes from where the prefix left off.</p><p>First, let’s go ahead and create a stack variable and initialize it with a list that (for now) just contains whatever node current currently is:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6194effaa7b461ee761d924793a2a4c4/href">https://medium.com/media/6194effaa7b461ee761d924793a2a4c4/href</a></iframe><p>We’ll be adding values to the front of the stack here and popping them off the front, meaning that we’ll be digging down into our Trie in a depth-first search pattern (technically in a somewhat “<a href="https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/">post-order</a>” depth-first search manner).</p><p>We’ll next add another while loop that will run for as long as stack has a length that’s greater than 0. For each iteration, we’ll pop off the top of the stack and assign it to our previous current variable:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/be66ca029473061f9add4f1b53b38b90/href">https://medium.com/media/be66ca029473061f9add4f1b53b38b90/href</a></iframe><p>If the current node popped off the stack has a word_totals of greater than 0, we know we’ve found a word. In this case, we can just return True.</p><p>If not, we should go ahead and add all the children in current.children to the top of the stack:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/52b169f4e3d041a8d6ebb608e493fab6/href">https://medium.com/media/52b169f4e3d041a8d6ebb608e493fab6/href</a></iframe><p>If we ever exit out of our while loop without finding any word_totals on any of our nodes, we can merely have a base statement that returns False.</p><p>Boom. There we go! 🙌🏻</p><p>This method will run in a worst-case time complexity of O(V) where V is the number of nodes in the Trie. The space complexity is potentially O(V) as well due to the stack that we’re using.</p><h3>Conclusion</h3><p>Nice work. This one teaches you a fundamental data structure, so hopefully going through this has cemented it in your brain!</p><p>Keep an eye out for the rest of these <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 coding challenges</a> articles. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-profile/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e99c00b7acca" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Jump Game (LeetCode #55)]]></title>
            <link>https://nwthomas.medium.com/jump-game-leetcode-55-8db45b80f949?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/8db45b80f949</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Tue, 23 Aug 2022 17:37:50 GMT</pubDate>
            <atom:updated>2022-08-23T17:37:50.916Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*t9ZpUiI00FkeVv_y4qSoDQ.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@josephgruenthal">Joseph Frank</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/longest-increasing-subsequence-leetcode-300-f888b3657c03"><em>Longest Increasing Subsequence</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/jump-game/">Jump Game</a> problem, you’re in the right spot.</p><p>This is a question in the <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 LeetCode code challenge list</a>, a group of questions put together by a tech lead at Facebook that’s been touted as a <em>great </em>way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍♂️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given a list of nums</li><li>We’re initially positioned at the first index 0</li><li>Each value in nums represents the maximum jumps possible from that position</li><li>We should return True if we reach the end of nums via jumping or else False otherwise</li><li>nums will have a length of 1 &lt;= len(nums) &lt;= 10^4</li><li>Values within nums will be 0 &lt;= nums[i] &lt;= 105</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Initial Problem Setup 🏗</h3><p>This is yet another dynamic programming problem, but I promise this one is <em>so straightforward</em> that, once we get the solution done, you’re going to remember this one forever.</p><p>It turns out that the best way to approach this problem is to use a “greedy” approach for jumping.</p><p>Each value in nums represents the maximum amount of jumps from that position. If we keep track of our jumps remaining, subtract 1 each iteration of our loop across nums, and update the jumps we have remaining when the new nums[i] value is larger, we can jump our way across nums while letting this logic handle whether we’ve hit 0 jumps left or not!</p><p>If we do hit 0, we can merely return False.</p><p>If we make it to the end of the list and exit our loop, we can return True!</p><p>Here’s the initial setup for this function:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/bfb673113ca97d98fec59daa00efe320/href">https://medium.com/media/bfb673113ca97d98fec59daa00efe320/href</a></iframe><p>We’ve set up a variable called jumps_remaining that will be initialized with the first value in our nums list (which is guaranteed to have a length of at least 1). This is because we don’t want to start with 0.</p><p>Now, let’s get into setting up our loop! 🔥</p><h3>Setting Up Our Loop 🔁</h3><p>The next thing we need to do is use a for loop and iterate over our nums list.</p><p>I’m going to use the enumerate function to get access to <em>both</em> the index and the value of each position in nums:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1a80e677782060ee994fa6aa2e4bf462/href">https://medium.com/media/1a80e677782060ee994fa6aa2e4bf462/href</a></iframe><p>Notice that we immediately update our jumps_remaining with either its current value or the value of the current num, whichever is greater.</p><p>The next thing we need to do is to check if our value is 0 even <em>after</em> this update:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/23c46137a948a1851a2b6932ab1cf6e0/href">https://medium.com/media/23c46137a948a1851a2b6932ab1cf6e0/href</a></iframe><p>We only want to do this if we’re not on the final index of nums. If we have 0 jumps remaining but we’re at the end, that’s a <em>good </em>thing, right?</p><p>This is our False case where we return if we can’t keep jumping anymore.</p><p>The final thing in our loop we need to do is to subtract 1 from jumps_remaining every iteration. This is us actually performing a jump to the next iteration of the loop!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ca87418ce50b96149be60ec71ba1e372/href">https://medium.com/media/ca87418ce50b96149be60ec71ba1e372/href</a></iframe><p>Finally, we need some code at the end of our function in case we make it to the end of our nums list successfully (e.g. our loop stops running and we never had to return False):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f5438889de690233855d9ce0e3c4b48d/href">https://medium.com/media/f5438889de690233855d9ce0e3c4b48d/href</a></iframe><p>Nice. We can just return True!</p><p>This whole thing only iterates through our nums list once, and so it runs in O(n) time complexity. We’re also only using a single variable in memory, so it has a O(1) space complexity.</p><h3>Conclusion</h3><p>Nice work. Dynamic programming problems can send you for a bit until they click, but you made it through.</p><p>Keep an eye out for the rest of these <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 coding challenges</a> articles. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-profile/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8db45b80f949" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Longest Increasing Subsequence (LeetCode #300)]]></title>
            <link>https://nwthomas.medium.com/longest-increasing-subsequence-leetcode-300-f888b3657c03?source=rss-9a175cd0696f------2</link>
            <guid isPermaLink="false">https://medium.com/p/f888b3657c03</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[coding-challenge]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[interview-questions]]></category>
            <category><![CDATA[interview-prep]]></category>
            <dc:creator><![CDATA[Nathan Thomas]]></dc:creator>
            <pubDate>Mon, 22 Aug 2022 20:08:18 GMT</pubDate>
            <atom:updated>2022-08-22T20:08:18.112Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6tUugEDQOs2Kp-67Js1kUQ.jpeg" /><figcaption>Image by <a href="https://unsplash.com/@edwardhowellphotography">Edward Howell</a> on <a href="https://unsplash.com/">Unsplash</a></figcaption></figure><p><em>This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include </em><a href="https://nwthomas.medium.com/building-your-own-bitcoin-node-c7d36ab1fa94"><em>Building Your Own Bitcoin Node</em></a><em> and </em><a href="https://nwthomas.medium.com/clone-graph-leetcode-133-144ebcecd985"><em>Clone Graph</em></a><em>.</em></p><h3>Introduction</h3><p>If you’re looking for a quick walkthrough of an optimal solution to the LeetCode <a href="https://leetcode.com/problems/longest-increasing-subsequence/">Longest Increasing Subsequence</a> problem, you’re in the right spot.</p><p>This is a question in the <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 LeetCode code challenge list</a>, a group of questions put together by a tech lead at Facebook that’s been touted as a <em>great </em>way to prep for interviews.</p><p>Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.</p><p>Let’s get it started!</p><h3>Understanding the Problem 🕵🏻‍♂️</h3><p>The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see <a href="https://math.berkeley.edu/~gmelvin/polya.pdf">Polya’s Problem Solving Techniques</a>):</p><ol><li>We’ll be given a list of nums</li><li>nums will have a minimum length of 1 and a maximum of 2500</li><li>We should return the length of the longest increasing subsequence (but not necessarily with these numbers being consecutively increasing)</li></ol><p>I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.</p><p>We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.</p><p>Okay. I think that’s enough housekeeping items for us to get started!</p><h3>Setup 🏗</h3><p>This problem is a dynamic programming problem! This means that we’ll be using a data structure to dynamically track results and also break down the problem into smaller “sub-problems.”</p><p>We’ll be using a list of the same length as nums, and we’ll initialize each index position with 1. You’ll see why shortly, I promise!</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b006251ae65ab29aee8a7d75f39994aa/href">https://medium.com/media/b006251ae65ab29aee8a7d75f39994aa/href</a></iframe><p>For instance, a list of nums of length 6 will produce a tracker list that look like this:</p><pre>nums = [2, 6, 4, 5, 9, 10]</pre><pre>tracker = [1, 1, 1, 1, 1, 1]</pre><p>We’re using 1 as the initial value since each number marks a longest increasing subsequence of at least 1. In other words, a list of nums = [4] with one value 4 would be correct with an initial value of tracker = [1] since the longest increasing subsequence would be 1. Make sense?</p><p>This gives us a dynamic programming list to track our progress and an initial value for each index position.</p><p>Now that we have this setup, let’s jump straight into our loops which are the bread and butter for this problem! 🍞</p><h3>Building Our Loops 🔁</h3><p>It turns out that the optimal solution for this problem uses two loops.</p><p>The first thing we want to do is set up a for loop that iterates over every number in the nums list:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3b1ef4d3f8811ac5ca0915db48a8553e/href">https://medium.com/media/3b1ef4d3f8811ac5ca0915db48a8553e/href</a></iframe><p>The fact that we’re starting at index 1 here is just because we’ve been asked in this problem to find an <em>increasing</em> subsequence. This means we can skip the first number since we’ll be looking at it in a second in our look-back.</p><p>You can’t have an increasing subsequence without numbers beforehand to increase upon, right?</p><p>The second thing we want to do is write a second, inner for loop that will iterate from the start of the list all the way up to (but not including) the current index i:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3e9cd0588ff40119c17f8f3bcf0d5395/href">https://medium.com/media/3e9cd0588ff40119c17f8f3bcf0d5395/href</a></iframe><p>Inside of this inner loop, we want to compare the numbers at nums[j] and nums[i]:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3bc30ddacbb2e78a8f2358626c823215/href">https://medium.com/media/3bc30ddacbb2e78a8f2358626c823215/href</a></iframe><p>Essentially, we’re updating tracker at position i with whatever the tracker[j] + 1 value is if it’s greater than current tracker[i].</p><p>If none of that made sense, just hold on — I’ll walk you through it.</p><p>First we start with our nums list and initialize a tracker list:</p><pre>nums = [1, 10, 5, 2, 7, 8]<br>tracker = [1, 1, 1, 1, 1, 1]</pre><p>We then start traversing our nums list with our outer loop, starting at index 1:</p><pre># We then start traversing our nums list, starting at index 1<br>nums = [1, 10, 5, 2, 7, 8]<br>           ^^</pre><p>We then iterate in our inner loop from 0 up to (but not including) the outer loop index. At each step (which is only once for this iteration), we compare the inner loop index of nums to the outer loop to see if the values are increasing:</p><pre>nums = [1, 10, 5, 2, 7, 8]<br>        ^  ^^</pre><p>They are, so we need to update tracker at the outer loop index (1) to be the value of tracker at the inner loop index (0) + 1:</p><pre>tracker = [1, 2, 1, 1, 1, 1]<br>           ^  ^</pre><p>We will continue walking through the values of nums with our outer and inner loops which will gradually build up an answer of the longest increasing subsequence.</p><p>For instance, the next few indices will build up like this:</p><pre>nums = [1, 10, 5, 2, 7, 8]</pre><pre># Second iteration at index 2, inner loop running up to it<br># No updates because the num is not increasing<br>tracker = [1, 2, 1, 1, 1, 1]<br>                 ^</pre><pre># Third iteration at index 3, inner loop running up to it<br># Update because the num is increasing<br>tracker = [1, 2, 1, 3, 1, 1]<br>                    ^</pre><p>I’d like to challenge you to finish the rest of this on a piece of paper or even on a text file. 💪🏻</p><p>See how this progressively builds up an answer for us?</p><p>The last thing we need to do is scan through the tracker list and return the maximum value in it. While my example above had the biggest increasing subsequence at the end, that won’t always be the case.</p><p>We can easily find our answer like this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/06713f9a5cb43cba3fa8bbc55ac11273/href">https://medium.com/media/06713f9a5cb43cba3fa8bbc55ac11273/href</a></iframe><p>This max(tracker) does exactly what it says on the box; it iterates through the list once and returns the largest value in the list.</p><p>This entire solution will run in O(n^2) time in the worst case (as we have a nested loop setup iterating over our loop) and have a space complexity of O(n) (for our tracker list).</p><h3>Conclusion</h3><p>Great job! What did you think? I hope you enjoyed this one.</p><p>Keep an eye out for the rest of these <a href="https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions">Blind 75 coding challenges</a> articles. It’s going to be a fun ride.</p><p>Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).</p><p>Thanks for reading. 🔥</p><p>Nathan</p><p>(<a href="https://github.com/nwthomas">GitHub</a>, <a href="https://www.linkedin.com/in/nwthomas-profile/">LinkedIn</a>, <a href="https://twitter.com/nwthomas_">Twitter</a>, and <a href="https://nathanthomas.dev/">Personal Site</a>)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f888b3657c03" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>