Beats 100% ✅✅|Dijkstra's Algorithm|Kotlin
Intuition\nIn this problem, we\'re looking for the minimum time to reach the bottom-right cell, where each cell has a minimum time requirement. This creates a w
# Intuition\nIn this problem, we\'re looking for the minimum time to reach the bottom-right cell, where each cell has a minimum time requirement. This creates a weighted graph problem, where the weights are the time we need to wait at each cell.\n\n# Approach\n\nLet\'s break down the solution:\n\n1. Initial Setup:\n   The solution starts by creating a grid called `times` where each cell is initialized to infinity (Int.MAX_VALUE). This grid keeps track of the minimum time needed to reach each cell. We set times[0][0] = 0 since we start at the top-left.\n\n2. Priority Queue:\n   We use a priority queue (PriorityQueue in Kotlin) that orders cells by their time. Each element in the queue contains (row, col, time). The priority queue ensures we always process the cell with the minimum time first.\n\n3. Main Algorithm Loop:\n   ```kotlin\n   while (pq.isNotEmpty()) {\n       val (row, col, time) = pq.poll()\n       \n       if (time > times[row][col]) continue  // Skip if we found a better time\n       if (row == m - 1 && col == n - 1) return time  // Reached destination\n   ```\n   We keep processing cells until we either reach the destination or run out of cells to process.\n\n4. Time Calculation: For each neighboring cell, we calculate two times:\n   ```kotlin\n   val newTime = time + 1  // Basic time to move to next cell\n   val waitTime = if (grid[newRow][newCol] > newTime) {\n       grid[newRow][newCol] + (grid[newRow][newCol] - newTime) % 2\n   } else newTime\n   ```\n   This is where the problem gets interesting. If we can\'t enter the cell immediately (grid[newRow][newCol] > newTime), we need to wait. The waiting calculation ensures we wait long enough to satisfy the cell\'s minimum time requirement.\n\nLet\'s see an example with the input grid:\n```\n[[0,1,3,2],\n [5,1,2,5],\n [4,3,8,6]]\n```\n\nStarting at (0,0):\n1. Initial state: times[0][0] = 0\n2. From (0,0), we can move to (0,1) or (1,0):\n   - For (0,1): grid[0][1] = 1, we can move there at time 1\n   - For (1,0): grid[1][0] = 5, we need to wait until time 5\n\n3. The priority queue will process (0,1) first since it has lower time\n4. From (0,1), we explore (0,2) and (1,1)\n   And so on...\n\nThe algorithm continues this way, always choosing the path with minimum time, until we reach the bottom-right cell or determine it\'s impossible.\n\n# Complexity\n\n- Time complexity: O(MN log(MN))\n    - Priority queue operations take O(log(MN)) time\n    - Each cell can be visited multiple times but bounded by maximum time\n    - Total operations = O(MN) vertices \xD7 O(log(MN)) for priority queue\n\n- Space complexity: O(MN)\n    - times[][] array: O(MN)\n    - Priority queue: O(MN) worst case\n    - Additional space (directions array, temp variables): O(1)\n\n# Code\n```kotlin []\nclass Solution {\n    fun minimumTime(grid: Array<IntArray>): Int {\n        if (grid[0][1] > 1 && grid[1][0] > 1) return -1\n        \n        val m = grid.size\n        val n = grid[0].size\n        val directions = arrayOf(intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(0, -1))\n        val times = Array(m) { Array(n) { Int.MAX_VALUE } }\n        times[0][0] = 0\n        \n        val pq = PriorityQueue<IntArray>(compareBy { it[2] })\n        pq.offer(intArrayOf(0, 0, 0))\n        \n        while (pq.isNotEmpty()) {\n            val (row, col, time) = pq.poll()\n            \n            if (time > times[row][col]) continue\n            if (row == m - 1 && col == n - 1) return time\n            \n            for ((dr, dc) in directions) {\n                val newRow = row + dr\n                val newCol = col + dc\n                \n                if (newRow in 0 until m && newCol in 0 until n) {\n                    val newTime = time + 1\n                    val waitTime = if (grid[newRow][newCol] > newTime) {\n                        grid[newRow][newCol] + (grid[newRow][newCol] - newTime) % 2\n                    } else newTime\n                    \n                    if (waitTime < times[newRow][newCol]) {\n                        times[newRow][newCol] = waitTime\n                        pq.offer(intArrayOf(newRow, newCol, waitTime))\n                    }\n                }\n            }\n        }\n        return -1\n    }\n}\n```\n\n## [Updated] How are we calculating waitTime?\nLet me break down the waitTime calculation and explain the intuition behind it. This is one of the trickier parts of the solution.\n\nFirst, let\'s understand what we\'re trying to solve:\n```kotlin\nval newTime = time + 1  // Time after moving to the new cell\nval waitTime = if (grid[newRow][newCol] > newTime) {\n    grid[newRow][newCol] + (grid[newRow][newCol] - newTime) % 2\n} else newTime\n```\n\nLet\'s say we\'re at time 3 and want to move to a cell that requires minimum time 7 (grid[newRow][newCol] = 7). What should we do?\n\nCase 1: When grid[newRow][newCol] <= newTime\n- If we can enter the cell immediately (the cell\'s required time is less than or equal to our arrival time)\n- We just use newTime (time + 1)\n- Example: We arrive at time 8, cell requires time 7 \u2192 we can enter immediately at time 8\n\nCase 2: When grid[newRow][newCol] > newTime\nThis is where it gets interesting. Let\'s work through an example:\n- We arrive at time 4 (newTime)\n- Cell requires time 7 (grid[newRow][newCol])\n- We can\'t enter immediately, so we need to wait\n- But here\'s the key insight: We can\'t just wait until time 7!\n\nWhy? Because of an important constraint in the problem: we must keep moving every second. We can\'t stay in the same place. So if we need to wait, we need to move back and forth between adjacent cells until we reach the required time.\n\nThe formula `grid[newRow][newCol] + (grid[newRow][newCol] - newTime) % 2` handles this:\n1. First part `grid[newRow][newCol]`: We need at least this much time\n2. Second part `(grid[newRow][newCol] - newTime) % 2`: This accounts for the back-and-forth movement\n\nLet\'s see a concrete example:\n```\nCurrent time: 4\nCell requires: 7\ngap = 7 - 4 = 3\n\nWe need to:\nt=4: Try to enter but can\'t\nt=5: Move back\nt=6: Move forward\nt=7: Finally enter\n\nThe formula gives us:\n7 + (7-4)%2 = 7 + 3%2 = 7 + 1 = 8\n```\n\nThe %2 part is crucial because:\n- If the gap is even, we\'ll end up back at the cell at exactly the required time\n- If the gap is odd, we\'ll need one extra move to get back to the cell
['Heap (Priority Queue)', 'Kotlin']