Skip to content

1824. Minimum Sideway Jumps 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int minSideJumps(vector<int>& obstacles) {
    constexpr int kInf = 1e6;
    // dp[i] := the minimum jump to reach the i-th lane
    vector<int> dp{kInf, 1, 0, 1};

    for (const int obstacle : obstacles) {
      if (obstacle > 0)
        dp[obstacle] = kInf;
      for (int i = 1; i <= 3; ++i)  // the current
        if (i != obstacle)
          for (int j = 1; j <= 3; ++j)  // the previous
            dp[i] = min({dp[i], dp[j] + (i == j ? 0 : 1)});
    }

    return ranges::min(dp);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int minSideJumps(int[] obstacles) {
    final int kInf = (int) 1e6;
    // dp[i] := the minimum jump to reach the i-th lane
    int[] dp = {kInf, 1, 0, 1};

    for (final int obstacle : obstacles) {
      if (obstacle > 0)
        dp[obstacle] = kInf;
      for (int i = 1; i <= 3; ++i) // the current
        if (i != obstacle)
          for (int j = 1; j <= 3; ++j) // the previous
            dp[i] = Math.min(dp[i], dp[j] + (i == j ? 0 : 1));
    }

    return Arrays.stream(dp).min().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minSideJumps(self, obstacles: list[int]) -> int:
    kInf = 1e6
    # dp[i] := the minimum jump to reach the i-th lane
    dp = [kInf, 1, 0, 1]

    for obstacle in obstacles:
      print(dp)
      if obstacle > 0:
        dp[obstacle] = kInf
      for i in range(1, 4):  # the current
        if i != obstacle:
          for j in range(1, 4):  # the previous
            dp[i] = min(dp[i], dp[j] + (0 if i == j else 1))

    return min(dp)