<?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[Gateway To Thoughts - Medium]]></title>
        <description><![CDATA[We aim to share our experiences from different domains so that knowledge doesn’t stay confined. - Medium]]></description>
        <link>https://medium.com/gateway-to-thoughts?source=rss----1860b682f7---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Gateway To Thoughts - Medium</title>
            <link>https://medium.com/gateway-to-thoughts?source=rss----1860b682f7---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 15:19:12 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/gateway-to-thoughts" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Approaches To Problem Solving #21 (Multiset | Array)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-21-multiset-array-12c4b9c58e4a?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/12c4b9c58e4a</guid>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[multiset]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Mon, 20 Sep 2021 23:02:55 GMT</pubDate>
            <atom:updated>2021-09-20T23:02:55.581Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*JILyXtNZcLDfWzms" /><figcaption>Photo by <a href="https://unsplash.com/@modry_dinosaurus?utm_source=medium&amp;utm_medium=referral">Frantisek Duris</a></figcaption></figure><h3>Problem : Given a list of lists of integers, return the smallest difference that can be made by choosing exactly one integer from each of the lists and taking the difference between the maximum and the minimum number of the chosen integers.</h3><p>Let us consider an example to understand the problem better,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*CpNq4LgrVNitWRwV_JnzXg.png" /><figcaption>Fig-1: Taken from <a href="https://binarysearch.com/problems/Smallest-Difference">binarysearch.com</a></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/616/1*efE2MMFTo3LFpdu-EedvqA.png" /><figcaption>Fig-2: Output and Explanation taken from <a href="https://binarysearch.com/problems/Smallest-Difference">binarysearch.com</a></figcaption></figure><p>At first glance, this problem seems like one of those in which we have to <em>choose</em> integers from each list and maintain the maximum and minimum out of the elements that have been chosen.</p><p>Whenever we think about <em>choosing </em>elements, recursive approaches such as Dynamic Programming comes through as one of the best tools. Let us try to explore one such solution for this problem.</p><p><strong>Approach #1: </strong>Let us try to define the states for our dynamic programming first. If we consider the given list of lists as a matrix, then to define our position in the given matrix, we need both, row and column. But, are these two variables sufficient to define a state, in the given problem? No. We need two more state variables. One to maintain the maximum integer and another to maintain the minimum integer found so far.</p><p>The base case, here, is relatively easier to determine. We start from the first row and when we reach some row that is out of bounds, we return the difference between the maximum and minimum value found so far.</p><p>Let us discuss the transitions for our dynamic programming now. At any {row, column} position, we either pick the element or we don’t. If we pick the element, we update our maximum and minimum elements found so far. Otherwise, we move to the next element in the current row.</p><p>Talking about the time complexity of this approach, we would roughly get ~O(N * M * K * K), where N is the size of the longest row, M is the size of the longest column and K is the largest value that can be picked from all the lists. Not very impressive, of course.</p><p>We can try to solve this problem by maintaining N pointers, where every list (row) gets a single pointer. Since, the ordering of the numbers in the lists don’t really matter. We can try sorting all the lists first and then finding our solution. How does having N pointers help? If we can imagine having a data structure that can provide us with the minimum and maximum item out of the elements that the N pointers currently point to, it can ease the complexity of the problem.</p><blockquote>Multiset is one such data structure that can be used to fetch the smallest and largest element in O(1), each, whereas maintaining them can be done in O(logN).</blockquote><p>With all this information in our minds, let us discuss our approach.</p><p><strong>Approach #2: </strong>We sort all the lists and appoint a pointer to each of the lists. These pointers will be pointing at the smallest element i.e., the first element of each list, initially. We insert the values being pointed to the multiset. It is easy to figure out, at this stage, that the multiset will be having one element for each list at any given instance.</p><p>How do we maintain the multiset to always have ≤ N elements? We keep updating our answer by comparing the current answer to the difference of the maximum and the minimum element in the multiset. It can be proved using some intuition that the minimum element once compared with some maximum element, won’t be getting used again. Why? because, as the lists are sorted, next elements getting explored are always going to be larger, hence increasing the difference between the maximum and minimum elements.</p><p>Hence, after updating our answer for the minimum difference, we pop the minimum element out from the multiset and if there are more elements left in that list that contains the current minimum element, we increment that list’s pointer to point to the next element.</p><p>The complexity for this solution is ~O(N * M * log(N)), where N and M represent the number of lists and the maximum size of the list present, respectively.</p><p>Hence, we have made a significant improvement over our first solution.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h3>Problem : We are looking to paint a row of N fences that can be of K different colors. Our goal is to minimise the cost while ensuring that no two neighboring fences are of the same color. Given a N by K matrix where the ith row and jth column represents the cost to paint the ith fence with jth color, return the minimum cost which achieves this goal.</h3><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Dynamic Programming, N-pointers and Multisets further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>21st</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-20-dp-string-palindrome-afbdd71aeb6e">Approaches To Problem Solving #20 (DP | String | Palindrome)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-19-bfs-tree-aebb1e822161">Approaches To Problem Solving #19 (BFS | Tree)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-18-bfs-2-d-matrix-c9fc3f39242b">Approaches To Problem Solving #18 (BFS | 2-D Matrix)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=12c4b9c58e4a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-21-multiset-array-12c4b9c58e4a">Approaches To Problem Solving #21 (Multiset | Array)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #20 (DP | String | Palindrome)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-20-dp-string-palindrome-afbdd71aeb6e?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/afbdd71aeb6e</guid>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[palindrome]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Mon, 07 Jun 2021 17:11:47 GMT</pubDate>
            <atom:updated>2021-06-07T17:11:28.282Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*nv8SrV26foP4BXMR" /><figcaption>Photo by <a href="https://unsplash.com/@robertlukeman?utm_source=medium&amp;utm_medium=referral">Robert Lukeman</a></figcaption></figure><h3>Problem : Given two strings S and T. Consider taking a non-empty subsequence from S, a non-empty subsequence from T, and then concatenating the first subsequence with the second. Return the longest possible palindrome that can be constructed.</h3><p>Let us consider an example to understand what we are required to do.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/543/1*dEaUraMAWDAeNmWX2A8ATg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/542/1*UCzDd5x8OI_cnVHdCb73Wg.png" /><figcaption>Fig-1: Taken from <a href="https://binarysearch.com/problems/Longest-Palindrome-From-Concatenating-Two-Subsequences">binarysearch.com</a></figcaption></figure><p>We can explain the above example as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*Qyfnq6PJGoayd5OE4gRbyw.png" /><figcaption>Fig-2: Explanation taken from <a href="https://binarysearch.com/problems/Longest-Palindrome-From-Concatenating-Two-Subsequences">binarysearch.com</a></figcaption></figure><blockquote>This problem is an extension to a very famous problem where we are supposed to find the longest palindromic subsequence in a string.</blockquote><p>The intuition before we dive into solving this problem can be to reduce the given problem into the other, where we were given just a single string.</p><p>The problem statement mentions “concatenated subsequence”. What happens when we concatenate two strings? We get a single string out of adding the two. Hence, after concatenation, we have only a single string to deal with.</p><p>Will finding the longest palindromic subsequence out of this concatenated string give us our solution?</p><p>Let us try,</p><p><strong>Approach #1: </strong>To find the longest palindromic subsequence, we maintain a 2-D array. This 2-D array has one dimension for the left bound index and the other for the right bound index. Basically, this 2-D array holds the value of the longest palindromic subsequence that can be obtained between some index L to some index R (L ≤ R). Through tabulation, this can be mathematically computed as,</p><p>cache[L][L] = 1 (0 ≤ L ≤ length of String — 1),</p><p>if(S’[L] == S’[R]):<br> cache[L][R] = 2;<br> if(L &lt; R— 1):<br> cache[L][R] += cache[L + 1][R — 1];</p><p>else <br>cache[L][R] = max(cache[L][R], max(cache[L + 1][R], cache[L][R — 1]))</p><p><em>where S’ is the concatenated string (S + T), 0≤ L ≤ R &lt; length of S’ and cache is the table for storing solutions for all pairs (L, R).</em></p><p>Is doing this sufficient? NO.</p><p>Let us take a look at an example,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/171/1*ephG52nfbJhqiz_r6Wmh0g.png" /><figcaption>Fig-3: Example</figcaption></figure><p>The answer returned through the above approach is <strong>4</strong>, but the expected answer to the given problem for the same example should be <strong>3</strong>. Why? Because, we need to make sure that we pick <strong>non-empty subsequences</strong> from both the input strings.</p><p><strong>Approach #2: </strong>The core of our solution will stay the same. We will do everything that we did in <em>Approach #1</em>, we will just add a small check to ensure that we are considering the right candidates amongst all the pairs of L and R, for determining the answer.</p><p>Once we have created the table, we loop through the pairs of L and R in our concatenated string S’, and update our solution with the maximum value found yet, only when our L belongs to the first string, S and R belongs to the second string, T. Thus, we ensure that we are picking non-empty subsequences from both the input strings.</p><p>The time complexity for this solution is O(N * N), where ‘N’ is the length of the concatenated string S’.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h3>Problem : Given a list of lists of integers, return the smallest difference that can be made by choosing exactly one integer from each of the lists and taking the difference between the maximum and the minimum number of the chosen integers.</h3><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Dynamic Programming and Palindromes further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>20th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-19-bfs-tree-aebb1e822161">Approaches To Problem Solving #19 (BFS | Tree)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-18-bfs-2-d-matrix-c9fc3f39242b">Approaches To Problem Solving #18 (BFS | 2-D Matrix)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-17-tree-dfs-8590b43915fb">Approaches To Problem Solving #17(Tree | DFS)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=afbdd71aeb6e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-20-dp-string-palindrome-afbdd71aeb6e">Approaches To Problem Solving #20 (DP | String | Palindrome)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #19 (BFS | Tree)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-19-bfs-tree-aebb1e822161?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/aebb1e822161</guid>
            <category><![CDATA[trees]]></category>
            <category><![CDATA[fb]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Mon, 10 May 2021 11:58:43 GMT</pubDate>
            <atom:updated>2021-05-10T11:57:51.935Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*UnPWlBatOUHUcuyZ" /><figcaption>Photo by <a href="https://unsplash.com/@thesaboo?utm_source=medium&amp;utm_medium=referral">Sascha Bosshard</a></figcaption></figure><h3>Problem : Given a binary tree root, return the top view of the tree, sorted left to right.</h3><p>Let us consider an example to understand what we are required to do.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/420/1*Ko4IGn7PA8RaRQdH0_6tXw.png" /><figcaption>Fig-1: Taken from <a href="https://binarysearch.com/problems/Top-View-of-a-Tree">binarysearch.com</a></figcaption></figure><p>We can explain the above example as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/552/1*44VG58CQNbfvb26_Fof-tQ.png" /><figcaption>Fig-2: Explanation taken from <a href="https://binarysearch.com/problems/Top-View-of-a-Tree">binarysearch.com</a></figcaption></figure><p>In most of the problems related to the concept of Trees, thinking on the lines of picking the best way to traverse the tree, often makes it easier to find a solution.</p><p>Since we are concerned with showing the top view of the tree in some order, we can safely assume that the nodes closer to the root have to be given more priority compared to the ones below them, if they meet the right criteria.</p><blockquote>This gives us a hint that we should try to approach this problem with keeping Level Order Traversal in our minds.</blockquote><p><strong>Approach : </strong>If we provide each node with some reference id, we can distinguish between the nodes on the basis of how left do they appear in the given tree. This can be done if we sequentially provide the reference ids from left to right on each level independent of the other levels.</p><p>Since we are providing ids to the nodes closer to the root node first, we perform a Breadth First Search starting from the root node.</p><p>Assigning of the reference ids can be done as; if the current node has an id ‘i’, its left child gets the id ‘i — 1’ and its right child gets the id ‘i + 1’. The first time a node gets some unique id, the node is pushed to our answer array.</p><p>Keeping in mind that we have to return our answer array sorted in the form of the smallest reference id first, we sort the answer array on the basis of the reference id. We have our solution !!</p><p>The time complexity for this solution is O(N + N * logN), where ’N’ is the number of nodes in the tree.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h3>Problem : Given two strings S and T. Consider taking a non-empty subsequence from S, a non-empty subsequence from T, and then concatenating the first subsequence with the second. Return the longest possible palindrome that can be constructed.</h3><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of BFS and Trees further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>19th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-18-bfs-2-d-matrix-c9fc3f39242b">Approaches To Problem Solving #18 (BFS | 2-D Matrix)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-17-tree-dfs-8590b43915fb">Approaches To Problem Solving #17(Tree | DFS)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-16-dp-subsequences-3a27701c7824">Approaches To Problem Solving #16(DP| Subsequences)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=aebb1e822161" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-19-bfs-tree-aebb1e822161">Approaches To Problem Solving #19 (BFS | Tree)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #18 (BFS | 2-D Matrix)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-18-bfs-2-d-matrix-c9fc3f39242b?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/c9fc3f39242b</guid>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[matrix]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[fb]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Mon, 19 Apr 2021 15:19:18 GMT</pubDate>
            <atom:updated>2021-04-19T15:18:54.042Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*o5Uz7DylG9H_vH86" /><figcaption>Photo by <a href="https://unsplash.com/@mynameisged?utm_source=medium&amp;utm_medium=referral">Ged Lawson</a></figcaption></figure><h4>Problem: Given a 2-D list of integers containing 1s and 0s. Return a 2-D matrix representing the Manhattan distance of the current cell from the nearest 0 cell. It can be assumed that at least one 0 exists in the matrix.</h4><p>Let us consider an example to understand what we are required to do.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/352/1*KNlePTaI6Nu1SWV5ciTgfA.png" /><figcaption>Fig-1: Taken from <a href="https://binarysearch.com/problems/Matrix-Nearest-Zero">binarysearch.com</a></figcaption></figure><p>We can explain the above example as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/634/1*tA-GmCyIAi8_fWKAUnx8lw.png" /><figcaption>Fig-2: Explanation taken from <a href="https://binarysearch.com/problems/Matrix-Nearest-Zero">binarysearch.com</a></figcaption></figure><p>We can identify the given matrix as a graph, with all the cells of the matrix depicting the nodes in the graph. Since, we are dealing with manhattan distances, the iterations from one node to the other can only be made from one cell to an adjacent cell.</p><p>As we are dealing with finding the nearest zero for every cell in the given matrix, we can safely assume that we are supposed to find the shortest distance of all cells from some cell containing a value of 0.</p><p>We know that the cost of iteration from one cell to another is constant (i.e., 1). Hence, we can use a standard Breadth First Search to figure out the shortest distances that we seek.</p><blockquote>Which cell should we start our iterations from?</blockquote><p>Since we can have multiple 0 values in our matrix and all of them can act as the source node, we can use Multi-source BFS to solve this problem.</p><p><strong>Approach : </strong>We iterate over the matrix and push all the cells containing 0 in them to a queue. We keep popping the front element of the queue, keep pushing the adjacent element to the queue and updating the minimum distances for each cell from the source cells.</p><p>We keep an answer matrix and update the answers for each cell by using the above method i.e., BFS. When we are done with all the cells, the answer matrix obtained is what we return as our solution.</p><p>The time complexity for this solution is O(N * M), where ’N’ is the number of rows and ‘M’ is the number of columns in the matrix.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h4>Problem : Given a binary tree root, return the top view of the tree, sorted left to right.</h4><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Multi-source BFS and 2-D matrices further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>18th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-17-tree-dfs-8590b43915fb">Approaches To Problem Solving #17(Tree | DFS)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-16-dp-subsequences-3a27701c7824">Approaches To Problem Solving #16(DP| Subsequences)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-15-graph-scc-2378edae0232">Approaches To Problem Solving #15(Graph | SCC)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c9fc3f39242b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-18-bfs-2-d-matrix-c9fc3f39242b">Approaches To Problem Solving #18 (BFS | 2-D Matrix)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #17(Tree | DFS)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-17-tree-dfs-8590b43915fb?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/8590b43915fb</guid>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[share-learnings]]></category>
            <category><![CDATA[trees]]></category>
            <category><![CDATA[dfs]]></category>
            <category><![CDATA[problem-solving]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Mon, 05 Apr 2021 18:27:51 GMT</pubDate>
            <atom:updated>2021-04-05T18:27:29.003Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*YxvvoZk7o2ZdSm7o" /><figcaption>Photo by <a href="https://unsplash.com/@zane404?utm_source=medium&amp;utm_medium=referral">Zane Lee</a></figcaption></figure><h3>Problem: Given a binary tree, return the longest path that alternates, going down from one child to the other child. For example, it may alternate between right child, left child, right child, etc. Or left child, right child, left child, etc, going down.</h3><p>Let us consider an example to understand the problem better,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*pvrWmBMfRCJcGmUHj3MuIw.png" /><figcaption>Fig-1: Taken from <a href="https://binarysearch.com/problems/ZigZag-Path">BinarySearch</a></figcaption></figure><p>We can explain the above example as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*cni8CYZyOrhfbD8vx4lTmQ.png" /><figcaption>Fig-2: Explanation Taken from <a href="https://binarysearch.com/problems/ZigZag-Path">BinarySearch</a></figcaption></figure><p>We will try to approach this problem, by keeping in mind what information does each node require. It is intuitive to think of having two pieces of information to be returned to each node, one from its left child and other from its right child. What information are we talking about? Let us think of this information in terms of a pair.</p><p>The first entry of this pair tells us what the contribution of the current node is if we were to move to the right child and similarly, the second entry of this pair should tell us about the contribution if we were to go left, next.</p><p><strong>Approach: </strong>We start traversing the tree from the root node using Depth First Search. We return a pair from all the nodes as stated above. For the above given example we can visualise our given method as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*t9VUsX_6USbFkN7RGAvjJw.png" /><figcaption>Fig-3: Given input tree and the return values for the respective nodes.</figcaption></figure><p>If we look at the picture above closely, we will be able to figure out how the return values have been generated for each node. Again, for each node, the pair of values getting returned tell us about the longest alternating path that we can take starting from this node. Why did we use the concept of pairs here? Well, the reason behind considering pairs here is that, we need to find out the best solution for the given node if we move to either the left child or the right child, next.</p><p>We use these values getting returned from children nodes to construct the answer for the current node.</p><p>Mathematically,</p><blockquote>answer[curr-&gt;left] = dfs(curr-&gt;left),</blockquote><blockquote>answer[curr-&gt;right] = dfs(curr-&gt;right),</blockquote><blockquote>answer[curr] = {1 + answer[curr-&gt;right].second, 1 + answer[curr-&gt;left].first}</blockquote><p>where “curr” denotes the current node being explored and “answer” is an array of pairs holding the solutions for all the nodes.</p><p>Finding the maximum out of the first and second pair values of all the nodes would lead us to the final solution.</p><blockquote>We need to keep in mind that a NULL node returns {0, 0}</blockquote><p>The time complexity for this solution is O(N), where “N” is the total number of nodes in the tree.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h3>Problem: Given a 2-D list of integers containing 1s and 0s. Return a 2-D matrix representing the Manhattan distance of the current cell from the nearest 0 cell. It can be assumed that at least one 0 exists in the matrix.</h3><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Tree and DFS further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>17th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-16-dp-subsequences-3a27701c7824">Approaches To Problem Solving #16(DP| Subsequences)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-15-graph-scc-2378edae0232">Approaches To Problem Solving #15(Graph | SCC)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-14-divide-and-conquer-dp-array-9260fc61cf9a">Approaches To Problem Solving #14(Divide and Conquer | DP | Array)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8590b43915fb" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-17-tree-dfs-8590b43915fb">Approaches To Problem Solving #17(Tree | DFS)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #16(DP| Subsequences)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-16-dp-subsequences-3a27701c7824?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/3a27701c7824</guid>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[string]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[subsequence]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Sun, 28 Mar 2021 10:48:21 GMT</pubDate>
            <atom:updated>2021-04-04T22:20:11.265Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*CUZcDmOYvtXFFQp6" /><figcaption>Photo by <a href="https://unsplash.com/@gautamarora1991?utm_source=medium&amp;utm_medium=referral">Gautam Arora</a></figcaption></figure><h3>Problem: Given the strings “A” and “B” consisting of lowercase alphabet characters, return the number of subsequences of “A” that are equal to “B”. Mod the result by 10**9 + 7.</h3><p>Let us consider an example to understand the problem better,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/506/1*IYhI1zSxFwbkyiXrm2Q5Iw.png" /><figcaption>Fig-1: Taken from <a href="https://binarysearch.com/problems/Unique-Subsequences-Equal-to-Target">BinarySearch</a></figcaption></figure><p>We can explain the above example as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*xcdYhrQnoYlEuVdm4CUvag.png" /><figcaption>Fig-2: Explanation Taken from <a href="https://binarysearch.com/problems/Unique-Subsequences-Equal-to-Target">BinarySearch</a></figcaption></figure><p>In majority of the cases when we are dealing with problems in which we have to return the number of ways of doing something and the total number of ways can be really large, it is better to memoize our solutions for some states so that we can refer to the solutions of the sub-problems for finding solution for a given problem.</p><p>Let us dive into a recursive solution that involves memoization as well,</p><p><strong>Approach #1 : </strong>Let us break our problem into States, Transistions and Base Cases. Initially, we define our states using two iterators, one to traverse the first string and the other for traversing the other. We can have more variables to define our states later, if we need them.</p><p>Let us try to define our transitions. Assuming the first string be “A” and the other one be “B”, if the indices for the current state points to the same character in both A and B, then we have two options either we increment both the iterators by 1 for checking the next character in B, or explore the next possibilities for this character in B by just incrementing the iterator pointing to string A by 1. In the case when the characters defined by the current states don’t point to the same character in both the strings, we increment the iterator pointing to string A by 1. There cannot be any other case and hence the above transitions seem sufficient.</p><p>Talking about the base cases, there can be two possibilities, either we run out of bounds for the first string, or we run out of bounds for the other string. In the first case, if we are out of bounds for the string B too, we add 1 to our number of ways. Considering the case when we only run out of bounds for string B, we know that we have found some subsequence in A that equals B, hence we add 1 to our number of ways.</p><p>Defining our transitions mathematically,</p><blockquote>dp[indA][indB] = rec(indA + 1, indB)</blockquote><blockquote>if(A[indA] == B[indB]):<br> dp[indA][indB] += rec(indA + 1, indB + 1)</blockquote><p>where ‘dp’ array is used for memoization, and ‘rec’ is the recursive function.</p><blockquote>Not to forget that we keep the account of the result Mod 10⁹ + 7.</blockquote><p>The time complexity for this solution is O(N * M), where N is the size of string A and M is the size of string B.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h4>Problem: Given a binary tree, return the longest path that alternates, going down from one child to the other child. For example, it may alternate between right child, left child, right child, etc. Or left child, right child, left child, etc, going down.</h4><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Dynamic Programming, String and Subsequences further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>16th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-15-graph-scc-2378edae0232">Approaches To Problem Solving #15(Graph | SCC)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-14-divide-and-conquer-dp-array-9260fc61cf9a">Approaches To Problem Solving #14(Divide and Conquer | DP | Array)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-applying-dynamic-programming-on-2-d-matrices-a765892596e3">Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3a27701c7824" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-16-dp-subsequences-3a27701c7824">Approaches To Problem Solving #16(DP| Subsequences)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #15(Graph | SCC)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-15-graph-scc-2378edae0232?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/2378edae0232</guid>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[connected-components]]></category>
            <category><![CDATA[scc]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Thu, 18 Mar 2021 15:17:07 GMT</pubDate>
            <atom:updated>2021-03-28T10:49:19.581Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*TwEwb7LJFUOchijX" /><figcaption>Photo by <a href="https://unsplash.com/@jerrykavan?utm_source=medium&amp;utm_medium=referral">Jaromír Kavan</a></figcaption></figure><h3>Problem : You are given N cities represented as integers and a list of one-way roads that connects one city to another. Return whether you can reach one city from any city.</h3><p>Let us consider an example to understand the problem better,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/416/1*pJ8oV7cvBmWLOwj1NfZUzA.png" /><figcaption>Fig-1: Taken From <a href="https://binarysearch.com/problems/Connected-Cities">BinarySearch</a></figcaption></figure><p>In the majority of the cases when we are dealing with cities and one-way or two-way roads, it helps to think about the problem as a Graph theory problem.</p><p>Since we are concerned about reaching all the cities starting from any random city, it is pretty intuitive to think of the desired solution as a single component that accommodates all the nodes from 0 to N — 1, where ‘N’ is as given in the problem.</p><p>But, is it sufficient for all of the cities to belong to the same component, in order to prove that all the cities can be reached from any city picked at random? The answer is NO. Why? Let us consider an example given below,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/1*ySLb2a5wiNL8-l7gElKXiQ.png" /><figcaption>Fig-2: Example of a Connected but not Strongly Connected Component</figcaption></figure><p>Here, all 3 cities belong to the same component but, we cannot reach city ‘A’ from any other city. Hence, we need some addition to our given algorithm of connected components. The missing enhancement that we seek is the concept of Strongly Connected Components (<a href="https://en.wikipedia.org/wiki/Strongly_connected_component">SCC</a>). Consider the following,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/443/1*MyOlIVbGKyPaeb8jXqtS8A.png" /><figcaption>Fig-3: Example of a Strongly Connected Component</figcaption></figure><p><strong>Approach #1</strong>: We can break our solution into two steps:-</p><blockquote><strong>Step #1:</strong> Checking if all the cities belong to a single connected component.</blockquote><blockquote><strong>Step #2:</strong> Checking if the connected component consisting of all the N cities is a strongly connected component or not.</blockquote><p>If any of the above steps give us FALSE as a result, then the answer is FALSE and is TRUE otherwise.</p><p>We can verify the first step by choosing a node or city, arbitrarily, as the source city and performing a DFS. If all the cities are visited, after the DFS traversal is complete, we can be assured that all of the cities belong to a single component.</p><p>In order to perform a check on the second step, we need to make some enhancements in our dfs traversal performed earlier. We use <a href="https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm">Kosaraju’s Algorithm</a>, and maintain a Stack along with our DFS traversal. Once a city or node has been completely explored, we push that city onto the Stack. How does this Stack help us? The Stack tells us about the sequence in which we performed our DFS traversal.</p><p>Verifying the second step involves reversing all the edges. Why? Because, if we can reach all the nodes after reversing all the edges by traversing through in the same sequence as we did on our first DFS traversal, we can be sure that collective directions of the edges do not matter and thus, we can always find a way of reaching a destination city, starting from any other city in this component.</p><blockquote>Again, if any of the above steps return FALSE as a response, the answer is FALSE and TRUE otherwise.</blockquote><p>The time complexity for this solution is ~O(N), where N is the number of cities.</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h3>Problem: Given the strings “A” and “B” consisting of lowercase alphabet characters, return the number of subsequences of “A” that are equal to “B”. Mod the result by 10**9 + 7.</h3><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Graph, Connected Components and Strongly Connected Components further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>15th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-14-divide-and-conquer-dp-array-9260fc61cf9a">Approaches To Problem Solving #14(Divide and Conquer | DP | Array)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-applying-dynamic-programming-on-2-d-matrices-a765892596e3">Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-12-string-dp-60135b441005">Approaches To Problem Solving #12(String | DP)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2378edae0232" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-15-graph-scc-2378edae0232">Approaches To Problem Solving #15(Graph | SCC)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #14(Divide and Conquer | DP | Array)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-14-divide-and-conquer-dp-array-9260fc61cf9a?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/9260fc61cf9a</guid>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[divide-and-conquer]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[sport-programming]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Tue, 09 Mar 2021 09:29:37 GMT</pubDate>
            <atom:updated>2021-03-09T09:52:06.892Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ZljTUNgeoyAfSMEh" /><figcaption>Photo by <a href="https://unsplash.com/@chrisjdavis?utm_source=medium&amp;utm_medium=referral">Chris J. Davis</a></figcaption></figure><h3>Problem: Given a list of integers, arr. Consider a tree where arr represents the values of its leaves in an inorder traversal. All internal nodes have 2 children each and their value is equal to the product of the largest leaf value of its left subtree and the largest leaf value of its right subtree. Find the tree with the minimum sum of its values and return the sum.</h3><p>Let us consider the following example to get a clearer idea of this problem,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/522/1*gkBgRXU6994bBvxF0aUL7w.png" /><figcaption>Fig-1. Example Input and Output (Taken from <a href="https://binarysearch.com/problems/Minimum-Tree-From-Leaves/editorials">binarysearch.com</a>).</figcaption></figure><p>The answer tree for the above given input array can be created as follows,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/126/1*XI3gnJS_Eg3GMJqaUK1-cQ.png" /><figcaption>Fig-2. Tree created for the above given example (Taken from <a href="https://binarysearch.com/problems/Minimum-Tree-From-Leaves/editorials">binarysearch.com</a>).</figcaption></figure><p>It is given that the array provided to us as input depicts the leaves of the tree and that too in inorder manner. Hence, we can safely assume that we should not alter this array by say, sorting or reversing the array.</p><p>Since we are only considering the leaves to begin the construction of the tree, it seems intuitive to think about fixing the root node for the tree first and then build the tree subsequently. How? Let us use the concept of fixing the pivot for doing it. If we fix a pivot for a given array, we can divide the given array into two parts (<em>Left </em>and <em>Right</em>), where <em>Left </em>part indicates all the leaves that should belong to the left subtree for the root node and <em>Right </em>part indicates all the leaves that should belong to the right subtree for the root node.</p><p><strong>Approach #1</strong>: Let us extend this idea to all the subtrees that we are going to explore. Whenever solving for some subtree, we will fix a pivot and try to create the left and right partitions and then lay it as the basis for finding the next answers for the other subarrays respectively.</p><p>Consider the following representation,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*8X0eqKfGvPPGX2m7zonFZA.png" /><figcaption>Fig-3. Given an array of integers, where red and blue depict some division of the given array.</figcaption></figure><p>We can create a tree using the above division as,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/559/1*8r43SjXwbIeeUFXvPqE-lg.png" /><figcaption>Fig-4. One of the candidate trees possible using the array in Fig-3.</figcaption></figure><p>We can approach the proposed solution in a recursive manner. We break our current subarray under consideration into two partitions, [L, i] and [i + 1, R], where ‘i’ denotes the pivot, ‘L’ denotes the left bound of the subarray and ‘R’ denotes the right bound of the subarray, and then progress further to find the answers for other subarrays and combining all the solutions to figure out the best solution.</p><p>Talking about the states, Left bound and Right bound for a given array are sufficient to define the current state of the recursion. Transitions can be defined as follows,</p><p>answer[L][R] = min(answer[L][R], maxElement(L, i) * maxElement(i + 1, R) + recursion(L, i) + recursion(i + 1, R))</p><p>where 1 ≤ i ≤ N, and N is the length of the array.</p><p>Basically, we keep fixing the pivot for a given [L, R] as i, and since we know that [L, i] depicts the left subtree for the current subarray and [i + 1, R] depicts the right subtree, we return the product of the maximum leaves of both the left and the right subtree and add them to the answer for the rest of the subarrays. The best solution from all the candidates can be found by checking if the found solution is the minimum of them all or not, and updating the minimum answer found accordingly.</p><p>We compute the answer for the given input array by calculating the value for answer[1][N].</p><p>We need to take care of the base case where L is equal to R, in that case we just return the Lth value of the input array.</p><p>We can use memoization for storing the answers for each state, so that we don’t end up visiting the same state more than once.</p><p>The time complexity for the given solution is O(N²), since there can be at most N² states.</p><blockquote>We can find a solution for the given problem using concepts of heaps and monoqueues too.</blockquote><p>In our next article, one of the problems that we are going to discuss is given below,</p><h4><strong>Problem: You are given N cities represented as integers and a list of one-way roads that connects one city to another. Return whether you can reach one city from any city.</strong></h4><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Divide and Conquer, Dynamic Programming and Arrays further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>14th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-applying-dynamic-programming-on-2-d-matrices-a765892596e3">Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-12-string-dp-60135b441005">Approaches To Problem Solving #12(String | DP)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-11-tree-dynamic-programming-d440c34dbdc8">Approaches To Problem Solving #11(Tree | Dynamic Programming)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9260fc61cf9a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-14-divide-and-conquer-dp-array-9260fc61cf9a">Approaches To Problem Solving #14(Divide and Conquer | DP | Array)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-applying-dynamic-programming-on-2-d-matrices-a765892596e3?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/a765892596e3</guid>
            <category><![CDATA[matrix]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[share-learnings]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Mon, 01 Mar 2021 05:51:37 GMT</pubDate>
            <atom:updated>2021-03-01T05:51:14.979Z</atom:updated>
            <content:encoded><![CDATA[<h3>Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ihNmXgLjPoNnO3ui" /><figcaption>Photo by <a href="https://unsplash.com/@skabrera?utm_source=medium&amp;utm_medium=referral">Sergi Kabrera</a></figcaption></figure><h3>Problem : Given a two-dimensional matrix of integers containing 1s and 0s, return the total number of square submatrices with all 1s.</h3><p>Let us consider the following example to get a clearer idea of this problem,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*yGTPrItyAzHZFpcy5ENGqA.png" /><figcaption>Taken from <a href="https://leetcode.com/problems/count-square-submatrices-with-all-ones/">LeetCode</a></figcaption></figure><p>Let us consider a brute force solution first.</p><p><strong>Approach #1</strong>: We can try to break down the entire matrix into submatrices. A brute force solution will lead us to creating all the submatrices that are possible for the given matrix and then checking all of them one by one for the calculation of our answer. We can define two steps to our solution as :-</p><p><strong>Step 1: </strong>We generate all the submatrices possible from the given matrix. There are a total of N * M * N * M submatrices for an N * M matrix.</p><p><strong>Step 2: </strong>We check each submatrix one by one to find out if all the elements in that submatrix are 1s or not. If we find no 0-element in our submatrix, we add 1 to our answer and keep repeating this process for all such submatrices.</p><p>The time complexity for this solution is ~O(N⁶), where N is the number of rows or columns and assuming that rows and columns can be of interchangeable range of sizes.</p><p>We can reduce this time complexity a lot, by trying to store answers for submatrices and using these stored values for finding answers for the remaining submatrices of the given matrix.</p><p><strong>Approach #2</strong>: After spending some time with pen and paper, trying to understand how we can frame our dynamic programming solution, we find out that we can use a given cell in this matrix to figure out if a square submatrix containing all 1s ends at this cell or not. By “ends at this cell”, we mean that this cell being considered, is the bottom-rightmost corner cell of some submatrix.</p><p>Since we are only concerned about the square submatrices, one important observation is that for any bottom-rightmost cell, there are only three cells which need to be considered when determining if this cell being considered contributes to some square submatrix containing all 1s or not.</p><p>Whenever we consider some cell defined by (i, j), where i represents the ith row and j represents the jth column, we check for the largest dimension of matrices ending at (i — 1, j), (i — 1, j — 1) and (i, j — 1). These three values tell us the maximum dimensions for the submatrices ending at the cells mentioned above. One interesting observation is that if the current cell being considered is 1, then adding 1 to the minimum of the three values found above will tell us the maximum dimension of the square matrix containing all 1s, ending at the current cell.</p><p>We can define our transition as,</p><blockquote>For all (i, j), 1 ≤ i ≤ N and 1 ≤ j ≤ M, if matrix[i][j] = 1,</blockquote><blockquote>maxDimension[i][j] = 1 + min({maxDimension[i — 1][j], maxDimension[i — 1][j — 1], maxDimension[i][j — 1})</blockquote><p>The “maxDimension” matrix for the given input matrix can be built as,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/684/1*OAuiku4TO8ogwUZ8kMPbFA.png" /><figcaption>Fig — 1: We can see that adding all the values in this matrix give us 15 as our answer.</figcaption></figure><blockquote>It seems obvious now, that only the row and the column on which we currently are, contribute to the state of our dynamic programming.</blockquote><p>All that is left is to traverse over this “maxDimension” matrix and add up all the values in the matrix. Why? Because, if the maximum dimension of some submatrix containing all 1s, for a cell in a matrix is say ‘X’, then it will contribute to all square submatrices 1, 2,…,X.</p><blockquote>We need to take care of the cells that are out of bound (which serves as the base case for our dynamic programming) and we have our answer.</blockquote><p>The time complexity for the above solution is ~O(N * M).</p><p>This proves to be a huge improvement over the brute force solution proposed solution!!</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h4>Problem: Given a list of integers, arr. Consider a tree where arr represents the values of its leaves in an inorder traversal. All internal nodes have 2 children each and their value is equal to the product of the largest leaf value of its left subtree and the largest leaf value of its right subtree. Find the tree with the minimum sum of its values and return the sum.</h4><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Matrices and Dynamic Programming further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>This is the <strong>13th</strong> article of the “Approaches To Problem Solving” series.</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-12-string-dp-60135b441005">Approaches To Problem Solving #12(String | DP)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-11-tree-dynamic-programming-d440c34dbdc8">Approaches To Problem Solving #11(Tree | Dynamic Programming)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-10-heaps-sliding-window-786fdd48d8dd">Approaches To Problem Solving #10(Heaps | Sliding Window)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a765892596e3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-applying-dynamic-programming-on-2-d-matrices-a765892596e3">Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Approaches To Problem Solving #12(String | DP)]]></title>
            <link>https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-12-string-dp-60135b441005?source=rss----1860b682f7---4</link>
            <guid isPermaLink="false">https://medium.com/p/60135b441005</guid>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[sport-programming]]></category>
            <category><![CDATA[string-theory]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[share-learnings]]></category>
            <dc:creator><![CDATA[Ankesh Krishna Prasad]]></dc:creator>
            <pubDate>Sun, 21 Feb 2021 18:05:28 GMT</pubDate>
            <atom:updated>2021-02-21T18:18:17.830Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*LbvY6jZAmYcLABUe" /><figcaption>Photo by <a href="https://unsplash.com/@markuswinkler?utm_source=medium&amp;utm_medium=referral">Markus Winkler</a></figcaption></figure><p>In our previous blog, we already started with the introduction to one of the problems that we are going to discuss. We will try to discuss further about the topics involved.</p><p>Let us revisit the problem statement,</p><h4>Problem #1: Given two strings A and B, find the minimum edit distance between the two strings. Edit distance is defined using: (a) Deleting a character, (b) Inserting a character, (c) Replacing a character.</h4><p>Let us consider the following example to get a clearer idea of this problem,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/613/1*dipKXwxL0ADpGaDjaVGG-g.png" /><figcaption>Fig-1. Taken from <a href="https://binarysearch.com/problems/Edit-Distance">binarysearch.com</a></figcaption></figure><p>Since we are asked to find out the<em> minimum number of moves</em> to transform a source string into a target string, the problem hints us towards thinking in terms of Dynamic Programming.</p><p>Let us move forth and discuss how we can frame the states, base cases and transitions for the given problem to be solved using dynamic programming.</p><blockquote>We need States, base cases and transitions to understand how our dynamic programming should work.</blockquote><p><strong>Approach #1:</strong> First of all, if we try to think about states, it seems pretty intuitive to keep two parameters with ourselves to determine a given state in our recursive solution. First one to tell us where we are currently on the first string and second to tell us where we are currently on the second string. We will try to add more parameters to define our state if necessary, as we progress.</p><p>With our states known, let us work on determining the transitions. We have three types of operations i.e., deleting, inserting and replacing a character from the source string.</p><p>a)<strong> Deleting a characte</strong>r :- Let us assume that we are on the ith position in source string ‘A’ and on the jth position in target string ‘B’. So when we plan to delete a character from string ‘A’, it is equivalent to increasing i by 1 and letting j stay as it is.</p><p>b)<strong> Inserting a character</strong> :- When we insert a character in source string ‘A’ at the current position, it is fair to assume that we only insert a character that is equal to jth character in string ‘B’. Since we are inserting a new character just before the ith character (for the sake of simplicity), for the next state, i stays as it is and j is increased by 1.</p><p>c) <strong>Replacing a character</strong> :- When we replace a character in source string ‘A’ at the current position, it is again beneficial to replace the ith character with a character that is equal to the jth character in string ‘B’. Hence, our new state should have i and j both incremented by 1.</p><p>Not to forget, we can choose not to perform any of these operations and it is intuitive to only skip these operations when the ith character in string ‘A’ and jth character in string ‘B’ match.</p><p>Formally,</p><p>if(A[i] == B[j]) : dp[i][j] = rec(i + 1, j + 1),</p><p>else : dp[i][j] = 1 + min(rec(i + 1, j), rec(i + 1, j + 1), rec(i, j + 1))</p><p>With our states and transitions defined, only part left is to define the base cases. If i and j are both beyond the lengths of the strings A and B respectively, we return 0. In all the other cases, in which one of either i or j has reached beyond the length of their respective strings, we add the remaining length of the other string to our answer, as the only option left to equate both the strings is to delete the remaining characters left over in the other string.</p><p>Thus, we have our solution!! Assuming that the source string ‘A’ has length N and the target string ‘B’ has length M, the time complexity for this solution is ~O(N * M).</p><p>In our next article, one of the problems that we are going to discuss is given below,</p><h3>Problem : Given a two-dimensional matrix of integers containing 1s and 0s, return the total number of square submatrices with all 1s.</h3><p>We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Strings and Dynamic Programming further!</p><p>We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.</p><p>For hugs and bugs, please comment down below. Till then.. Happy Coding!</p><p>More such posts can be found at :-</p><ul><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-11-tree-dynamic-programming-d440c34dbdc8">Approaches To Problem Solving #11(Tree | Dynamic Programming)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-10-heaps-sliding-window-786fdd48d8dd">Approaches To Problem Solving #10(Heaps | Sliding Window)</a></li><li><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-9-dfs-dynamic-programming-b6ca75c3eb3c">Approaches To Problem Solving #9 (DFS | Dynamic Programming)</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=60135b441005" width="1" height="1" alt=""><hr><p><a href="https://medium.com/gateway-to-thoughts/approaches-to-problem-solving-12-string-dp-60135b441005">Approaches To Problem Solving #12(String | DP)</a> was originally published in <a href="https://medium.com/gateway-to-thoughts">Gateway To Thoughts</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>