Leetcode

Frog Jump

May 26, 2022 by aAshish

Approach 1: Jump to

  • Time:O(n^2)
  • Space:O(n^2)

C++

 
class Solution {
 public:
  bool canCross(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := true if a frog can make a size j jump to stones[i]
    vector<vector<bool>> dp(n, vector<bool>(n + 1));
    dp[0][0] = true;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        const int k = stones[i] - stones[j];
        if (k > n)
          continue;
        for (const int x : {k - 1, k, k + 1})
          if (0 <= x && x <= n)
            dp[i][k] = dp[i][k] || dp[j][x];
      }

    return any_of(begin(dp.back()), end(dp.back()),
                  [](bool val) { return val; });
  }
};

JAVA

 
class Solution {
  public boolean canCross(int[] stones) {
    final int n = stones.length;
    // dp[i][j] := 1 if a frog can make a size j jump to stones[i]
    int[][] dp = new int[n][n + 1];
    dp[0][0] = 1;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        final int k = stones[i] - stones[j];
        if (k > n)
          continue;
        for (final int x : new int[] {k - 1, k, k + 1})
          if (0 <= x && x <= n)
            dp[i][k] |= dp[j][x];
      }

    return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1);
  }
}

Python

 
class Solution:
  def canCross(self, stones: List[int]) -> bool:
    n = len(stones)
    # dp[i][j] := True if a frog can make a size j jump to stones[i]
    dp = [[False] * (n + 1) for _ in range(n)]
    dp[0][0] = True

    for i in range(1, n):
      for j in range(i):
        k = stones[i] - stones[j]
        if k > n:
          continue
        for x in (k - 1, k, k + 1):
          if 0 <= x <= n:
            dp[i][k] |= dp[j][x]

    return any(dp[-1])

Approach 2: Jump from

  • Time:O(n^2)
  • Space:O(n^2)

C++

 
class Solution {
 public:
  bool canCross(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := true if a frog can make a size j jump from stones[i]
    vector<vector<bool>> dp(n, vector<bool>(n + 1));
    dp[0][1] = true;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        const int k = stones[i] - stones[j];
        if (k <= n && dp[j][k]) {
          dp[i][k - 1] = true;
          dp[i][k] = true;
          dp[i][k + 1] = true;
        }
      }

    return any_of(begin(dp.back()), end(dp.back()),
                  [](bool val) { return val; });
  }
};

JAVA

 
class Solution {
  public boolean canCross(int[] stones) {
    final int n = stones.length;
    // dp[i][j] := 1 if a frog can make a size j jump from stones[i]
    int[][] dp = new int[n][n + 1];
    dp[0][1] = 1;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        final int k = stones[i] - stones[j];
        if (k <= n && dp[j][k] == 1) {
          dp[i][k - 1] = 1;
          dp[i][k] = 1;
          dp[i][k + 1] = 1;
        }
      }

    return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1);
  }
}

Python

 
class Solution:
  def canCross(self, stones: List[int]) -> bool:
    n = len(stones)
    # dp[i][j] := True if a frog can make a size j jump from stones[i]
    dp = [[False] * (n + 1) for _ in range(n)]
    dp[0][1] = True

    for i in range(1, n):
      for j in range(i):
        k = stones[i] - stones[j]
        if k <= n and dp[j][k]:
          dp[i][k - 1] = True
          dp[i][k] = True
          dp[i][k + 1] = True

    return any(dp[-1])