{"id":8346,"date":"2021-04-13T00:00:03","date_gmt":"2021-04-13T07:00:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8346"},"modified":"2021-04-13T00:00:38","modified_gmt":"2021-04-13T07:00:38","slug":"leetcode-1824-minimum-sideway-jumps","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1824-minimum-sideway-jumps\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1824. Minimum Sideway Jumps"},"content":{"rendered":"\n<p>There is a&nbsp;<strong>3 lane road<\/strong>&nbsp;of length&nbsp;<code>n<\/code>&nbsp;that consists of&nbsp;<code>n + 1<\/code>&nbsp;<strong>points<\/strong>&nbsp;labeled from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n<\/code>. A frog&nbsp;<strong>starts<\/strong>&nbsp;at point&nbsp;<code>0<\/code>&nbsp;in the&nbsp;<strong>second&nbsp;<\/strong>laneand wants to jump to point&nbsp;<code>n<\/code>. However, there could be obstacles along the way.<\/p>\n\n\n\n<p>You are given an array&nbsp;<code>obstacles<\/code>&nbsp;of length&nbsp;<code>n + 1<\/code>&nbsp;where each&nbsp;<code>obstacles[i]<\/code>&nbsp;(<strong>ranging from 0 to 3<\/strong>) describes an obstacle on the lane&nbsp;<code>obstacles[i]<\/code>&nbsp;at point&nbsp;<code>i<\/code>. If&nbsp;<code>obstacles[i] == 0<\/code>, there are no obstacles at point&nbsp;<code>i<\/code>. There will be&nbsp;<strong>at most one<\/strong>&nbsp;obstacle in the 3 lanes at each point.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if&nbsp;<code>obstacles[2] == 1<\/code>, then there is an obstacle on lane 1 at point 2.<\/li><\/ul>\n\n\n\n<p>The frog can only travel from point&nbsp;<code>i<\/code>&nbsp;to point&nbsp;<code>i + 1<\/code>&nbsp;on the same lane if there is not an obstacle on the lane at point&nbsp;<code>i + 1<\/code>. To avoid obstacles, the frog can also perform a&nbsp;<strong>side jump<\/strong>&nbsp;to jump to&nbsp;<strong>another<\/strong>&nbsp;lane (even if they are not adjacent) at the&nbsp;<strong>same<\/strong>&nbsp;point if there is no obstacle on the new lane.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.<\/li><\/ul>\n\n\n\n<p>Return<em>&nbsp;the&nbsp;<strong>minimum number of side jumps<\/strong>&nbsp;the frog needs to reach&nbsp;<strong>any lane<\/strong>&nbsp;at point n starting from lane&nbsp;<code>2<\/code>&nbsp;at point 0.<\/em><\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;There will be no obstacles on points&nbsp;<code>0<\/code>&nbsp;and&nbsp;<code>n<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/25\/ic234-q3-ex1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> obstacles = [0,1,2,3,0]\n<strong>Output:<\/strong> 2 \n<strong>Explanation:<\/strong> The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).\nNote that the frog can jump over obstacles only when making side jumps (as shown at point 2).\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/25\/ic234-q3-ex2.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> obstacles = [0,1,1,3,3,0]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> There are no obstacles on lane 2. No side jumps are required.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/25\/ic234-q3-ex3.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> obstacles = [0,2,1,0,3,0]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> The optimal solution is shown by the arrows above. There are 2 side jumps.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>obstacles.length == n + 1<\/code><\/li><li><code>1 &lt;= n &lt;= 5 * 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= obstacles[i] &lt;= 3<\/code><\/li><li><code>obstacles[0] == obstacles[n] == 0<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n*k)<br>Space complexity: O(n*k) -&gt; O(k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int minSideJumps(vector<int>& obstacles) {\n    const int n = obstacles.size();\n    vector<vector<int>> dp(3, vector<int>(n, INT_MAX \/ 2));\n    dp[1][0] = 0;\n    dp[0][0] = dp[2][0] = 1;\n    for (int i = 1; i < n; ++i) {      \n      for (int k = 0; k < 3; ++k)\n        if (obstacles[i] != k + 1)\n          dp[k][i] = dp[k][i - 1];\n      for (int k = 0; k < 3; ++k)\n        if (obstacles[i] != k + 1)\n          dp[k][i] = min({dp[k][i], \n                          dp[(k + 1) % 3][i] + 1, \n                          dp[(k + 2) % 3][i] + 1});\n    }\n    return min({dp[0].back(), dp[1].back(), dp[2].back()});\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/O(1) Space<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int minSideJumps(vector<int>& obstacles) {\n    const int n = obstacles.size();\n    vector<int> dp{1, 0, 1};    \n    for (int o : obstacles) {\n      if (o) dp[o - 1] = 1e9;\n      for (int k = 0; k < 3; ++k) {      \n        if (k == o - 1) continue;\n        dp[k] = min({dp[k], \n                     dp[(k + 1) % 3] + 1, \n                     dp[(k + 2) % 3] + 1});\n      }\n    }\n    return *min_element(begin(dp), end(dp));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is a&nbsp;3 lane road&nbsp;of length&nbsp;n&nbsp;that consists of&nbsp;n + 1&nbsp;points&nbsp;labeled from&nbsp;0&nbsp;to&nbsp;n. A frog&nbsp;starts&nbsp;at point&nbsp;0&nbsp;in the&nbsp;second&nbsp;laneand wants to jump to point&nbsp;n. However, there could be obstacles&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,177],"class_list":["post-8346","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8346","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8346"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8346\/revisions"}],"predecessor-version":[{"id":8348,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8346\/revisions\/8348"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8346"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8346"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8346"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}