{"id":368,"date":"2025-06-24T23:07:13","date_gmt":"2025-06-24T17:37:13","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=368"},"modified":"2025-06-24T23:22:45","modified_gmt":"2025-06-24T17:52:45","slug":"path-with-minimum-effort","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/","title":{"rendered":"Path With Minimum Effort | Leetcode 1631 | Explained"},"content":{"rendered":"\n<p>Path With Minimum Effort made easy: understand LeetCode 1631 with a Dijkstra heap, 4-way moves, and fully commented Python code for students.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/path-with-minimum-effort\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-8a2dd1c0-a6c3-4e61-af84-54d6e08192d3\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#0-1-what-does-the-problem-ask\" style=\"\">1. What does the problem ask?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#1-2-tiny-examples\" style=\"\">2 Tiny examples<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#2-3-intuition-amp-approach-trainer-style\" style=\"\">3 Intuition &amp; approach (trainer style)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#3-31-why-classic-shortest-path-ideas-fail\" style=\"\">3.1 Why classic shortest-path ideas fail<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#4-32-the-trick-treat-effort-so-far-as-the-key\" style=\"\">3.2 The trick: treat effort so far as the key<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#5-33-algorithm-steps\" style=\"\">3.3 Algorithm steps<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#6-4-code-original-lines-comments-added\" style=\"\">4 Code (original lines, comments added)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#7-5-line-by-line-walkthrough\" style=\"\">5 Line-by-line walkthrough<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#8-6-dry-run-on-a-3-%C3%97-3-grid\" style=\"\">6 Dry run on a 3 \u00d7 3 grid<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#9-7-complexity\" style=\"\">7 Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/path-with-minimum-effort\/#10-8-conclusion\" style=\"\">8 Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-1-what-does-the-problem-ask\">1. What does the problem ask?<\/h2>\n\n\n\n<p>You get an <code>m \u00d7 n<\/code> matrix <code>heights<\/code>, where <code>heights[r][c]<\/code> is the altitude of cell <code>(r, c)<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>You start at the <strong>top-left<\/strong> cell <code>(0,0)<\/code> and must reach the <strong>bottom-right<\/strong> cell <code>(m-1,n-1)<\/code>.<\/li>\n\n\n\n<li>You may step <strong>up, down, left, or right<\/strong> (no diagonals).<\/li>\n\n\n\n<li><strong>Effort of a path<\/strong> = the <strong>largest absolute height difference<\/strong> between <strong>any<\/strong> two consecutive cells along that path.<\/li>\n<\/ul>\n\n\n\n<p>Return the <strong>smallest possible effort<\/strong> among all valid paths.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-2-tiny-examples\">2. Tiny examples<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th><code>heights<\/code><\/th><th>Best path<\/th><th>Effort<\/th><\/tr><\/thead><tbody><tr><td><code>[[1,2,2],[3,8,2],[5,3,5]]<\/code><\/td><td>1\u21922\u21922\u21922\u21923\u21925<\/td><td><strong>2<\/strong> (max diff 2)<\/td><\/tr><tr><td><code>[[1,2,3],[3,8,4],[5,3,5]]<\/code><\/td><td>1\u21922\u21923\u21924\u21925<\/td><td><strong>1<\/strong><\/td><\/tr><tr><td><code>[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]<\/code><\/td><td>snake-like path<\/td><td><strong>0<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-3-intuition-amp-approach-trainer-style\">3. Intuition &amp; approach<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-31-why-classic-shortest-path-ideas-fail\">3.1 Why classic shortest-path ideas fail<\/h3>\n\n\n\n<p>If we tried normal BFS (each step cost = 1) we would only count <em>how many<\/em> steps, ignoring height gaps.<br>If we tried Dijkstra with \u201cedge weight = absolute height diff\u201d, we would minimise <strong>total<\/strong> sum, not the <strong>maximum<\/strong> diff.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-32-the-trick-treat-effort-so-far-as-the-key\">3.2 The trick: treat <strong>effort so far<\/strong> as the key<\/h3>\n\n\n\n<p>Think of each move having a <strong>cost equal to its height gap<\/strong>, but our goal is to minimise the <strong>worst cost seen so far<\/strong> on the path.<\/p>\n\n\n\n<p>Dijkstra\u2019s greedy rule still works if we define the <strong>key<\/strong> of each cell as:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"effort(cell) = min possible maximum gap to reach this cell\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">effort(cell) = <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\"> possible maximum gap to reach this cell<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Because the algorithm always pops the currently <strong>smallest effort<\/strong> cell, once we pop the bottom-right cell we are <strong>guaranteed<\/strong> that no smaller effort exists.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-33-algorithm-steps\">3.3 Algorithm steps<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Distance grid<\/strong> <code>effort_arr<\/code> \u2013 keeps best known effort for every cell, initialised to <code>\u221e<\/code>, except <code>effort_arr[0][0] = 0<\/code>.<\/li>\n\n\n\n<li><strong>Min-heap<\/strong> \u2013 store <code>(current_effort, row, col)<\/code>. Start with <code>(0,0,0)<\/code>.<\/li>\n\n\n\n<li><strong>Loop<\/strong> until heap is empty\n<ol class=\"wp-block-list\">\n<li>Pop the cell with the smallest effort so far.<\/li>\n\n\n\n<li>If it is the goal, return its effort (greedy guarantee).<\/li>\n\n\n\n<li>For each of the four neighbours inside the grid and not blocked:\n<ul class=\"wp-block-list\">\n<li><code>step_gap = |height[next] \u2212 height[curr]|<\/code><\/li>\n\n\n\n<li><code>new_effort = max(current_effort, step_gap)<\/code><\/li>\n\n\n\n<li>If <code>new_effort<\/code> improves the neighbour\u2019s value in <code>effort_arr<\/code>, update and push it into the heap.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li>If we exhaust the heap (the grid is always connected so this won\u2019t happen), return <code>0<\/code>.<\/li>\n<\/ol>\n\n\n\n<p>Because each cell may improve at most once, the loop is <code>O(m \u00d7 n log(m \u00d7 n))<\/code>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-4-code-original-lines-comments-added\">4. Code<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"import sys\nimport heapq\nfrom typing import List\n\n\nclass Solution:\n    def minimumEffortPath(self, heights: List[List[int]]) -&gt; int:\n        rows = len(heights)\n        cols = len(heights[0])\n\n        # 1. distance grid: best effort seen so far for every cell\n        effort_arr = [[sys.maxsize for _ in range(cols)] for _ in range(rows)]\n        effort_arr[0][0] = 0\n\n        # 2. min-heap with tuples (effort, row, col)\n        priority_queue = [[0, 0, 0]]\n\n        while priority_queue:\n            eff, i, j = heapq.heappop(priority_queue)\n\n            # 3. goal reached \u2013 current effort is already minimal\n            if i == rows - 1 and j == cols - 1:\n                return eff\n\n            # 4. explore four neighbours\n            for x, y in [[-1, 0], [0, -1], [1, 0], [0, 1]]:\n                new_i, new_j = i + x, j + y\n                # skip when out of bounds\n                if new_i &lt; 0 or new_j &lt; 0 or new_i &gt;= rows or new_j &gt;= cols:\n                    continue\n\n                # effort of stepping into neighbour\n                step_gap = abs(heights[new_i][new_j] - heights[i][j])\n                new_eff  = max(eff, step_gap)\n\n                # 5. relax if we found a gentler path\n                if new_eff &lt; effort_arr[new_i][new_j]:\n                    effort_arr[new_i][new_j] = new_eff\n                    heapq.heappush(priority_queue, [new_eff, new_i, new_j])\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> sys<\/span><\/span>\n<span class=\"line\"><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> heapq<\/span><\/span>\n<span class=\"line\"><span style=\"color: #C586C0\">from<\/span><span style=\"color: #D4D4D4\"> typing <\/span><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> List<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">minimumEffortPath<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">heights<\/span><span style=\"color: #D4D4D4\">: List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        rows = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(heights)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        cols = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(heights[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># 1. distance grid: best effort seen so far for every cell<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        effort_arr = [[sys.maxsize <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(cols)] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(rows)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        effort_arr[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># 2. min-heap with tuples (effort, row, col)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        priority_queue = [[<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> priority_queue:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            eff, i, j = heapq.heappop(priority_queue)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># 3. goal reached \u2013 current effort is already minimal<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i == rows - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> j == cols - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> eff<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># 4. explore four neighbours<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> x, y <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> [[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, -<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">], [<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">], [<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                new_i, new_j = i + x, j + y<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># skip when out of bounds<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> new_i &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> new_j &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> new_i &gt;= rows <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> new_j &gt;= cols:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># effort of stepping into neighbour<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                step_gap = <\/span><span style=\"color: #DCDCAA\">abs<\/span><span style=\"color: #D4D4D4\">(heights[new_i][new_j] - heights[i][j])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                new_eff  = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(eff, step_gap)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># 5. relax if we found a gentler path<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> new_eff &lt; effort_arr[new_i][new_j]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    effort_arr[new_i][new_j] = new_eff<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    heapq.heappush(priority_queue, [new_eff, new_i, new_j])<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-5-line-by-line-walkthrough\">5. Line-by-line walkthrough<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Rows &amp; Cols<\/strong> \u2013 grid size.<\/li>\n\n\n\n<li><strong><code>effort_arr<\/code><\/strong> \u2013 imagine each cell filled with \u201c\u221e degrees of pain\u201d; source cell has 0.<\/li>\n\n\n\n<li><strong>Heap push<\/strong> \u2013 <code>(0,0,0)<\/code> means <em>no effort yet at (0,0)<\/em>.<\/li>\n\n\n\n<li><strong>Pop lowest effort<\/strong> \u2013 greedily safe because all weights are non-negative.<\/li>\n\n\n\n<li><strong>Neighbour loop<\/strong> \u2013 only 4 directions (problem requirement).<\/li>\n\n\n\n<li><strong><code>step_gap<\/code><\/strong> \u2013 vertical difference between the two cells.<\/li>\n\n\n\n<li><strong><code>new_eff<\/code><\/strong> \u2013 worst gap encountered on the candidate path to neighbour.<\/li>\n\n\n\n<li><strong>Relaxation<\/strong> \u2013 keep the gentlest path; push neighbour for future processing.<\/li>\n\n\n\n<li><strong>Early return<\/strong> \u2013 the first time we pop the bottom-right, we\u2019re done.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-6-dry-run-on-a-3-%C3%97-3-grid\">6. Dry run on a 3 \u00d7 3 grid<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"1  2  2\n3  8  2\n5  3  5\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">8<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">2<\/span><\/span>\n<span class=\"line\"><span style=\"color: #B5CEA8\">5<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #B5CEA8\">5<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Heap pop <code>(eff,r,c)<\/code><\/th><th>Updates &amp; pushes<\/th><th>Key <code>effort_arr<\/code> cells<\/th><\/tr><\/thead><tbody><tr><td>(0,0,0)<\/td><td>push (1,0,1), (2,1,0)<\/td><td>start 0<\/td><\/tr><tr><td>(1,0,1)<\/td><td>push (1,0,2), (6,1,1)<\/td><td>(0,1)=1<\/td><\/tr><tr><td>(1,0,2)<\/td><td>push (1,1,2)<\/td><td>(0,2)=1<\/td><\/tr><tr><td>(1,1,2)<\/td><td>push (2,2,2), (3,1,1)<\/td><td>(1,2)=1<\/td><\/tr><tr><td><strong>(2,2,2)<\/strong><\/td><td>goal reached \u2192 return <strong>2<\/strong><\/td><td>\u2013<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Path taken: <code>(0,0) \u2192 (0,1) \u2192 (0,2) \u2192 (1,2) \u2192 (2,2)<\/code> with max gap 2.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"9-7-complexity\">7. Complexity<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Measure<\/th><th>Value<\/th><th>Reason<\/th><\/tr><\/thead><tbody><tr><td><strong>Time<\/strong><\/td><td><code>O(m \u00d7 n log(m \u00d7 n))<\/code><\/td><td>Each cell enters heap \u2264 once; heap ops cost <code>log<\/code> cells.<\/td><\/tr><tr><td><strong>Space<\/strong><\/td><td><code>O(m \u00d7 n)<\/code><\/td><td><code>effort_arr<\/code> plus heap (worst-case all cells).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"10-8-conclusion\">8. Conclusion<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Treat <strong>effort<\/strong> as a distance metric whose cost of an edge is its height gap and whose path cost is the <strong>maximum<\/strong> edge cost so far.<\/li>\n\n\n\n<li>Running Dijkstra on that metric directly solves <em>Path With Minimum Effort<\/em>.<\/li>\n\n\n\n<li>Early-exit once the destination cell leaves the heap \u2013 the answer is already optimal.<\/li>\n<\/ul>\n\n\n\n<p>Remember: when you see \u201cminimise the maximum along the path\u201d, think of <strong>Dijkstra with a custom aggregation<\/strong> like <code>max()<\/code> instead of <code>+<\/code>.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/www.codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Path With Minimum Effort made easy: understand LeetCode 1631 with a Dijkstra heap, 4-way moves, and fully commented Python code for students. Here&#8217;s the [Problem Link] to begin with. 1. What does the problem ask? You get an m \u00d7 n matrix heights, where heights[r][c] is the altitude of cell (r, c). Return the smallest<\/p>\n","protected":false},"author":1,"featured_media":371,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,5],"tags":[24,17,18],"class_list":{"0":"post-368","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-dijkstra-algorithm","10":"tag-graph","11":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/path-with-minimum-effort-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/368","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=368"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/368\/revisions"}],"predecessor-version":[{"id":382,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/368\/revisions\/382"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/371"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}