LeetCode Entry

2849. Determine if a Cell Is Reachable at a Given Time

08.11.2023 medium 2023 kotlin

Is path possible on grid sx, sy -> fx, fy

2849. Determine if a Cell Is Reachable at a Given Time medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/397

Problem TLDR

Is path possible on grid sx, sy -> fx, fy

Intuition

Given the problem size, we can’t use DP, as it will take O(n^2). However, we must notice, that if the shortest path is reachable, than any other path can be formed to travel at any time.

Approach

The shortest path will consist of only the difference between coordinates.

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


    fun isReachableAtTime(sx: Int, sy: Int, fx: Int, fy: Int, t: Int): Boolean {
      var dx = Math.abs(fx - sx)
      var dy = Math.abs(fy - sy)
      var both = min(dx, dy)
      var other = max(dx, dy) - both
      var total = both + other
      return total <= t && (total > 0 || t != 1)
    }