BFS | Min Heap | 100% (Space & Time)
Recommended problems to get familiar with BFS & Min Heap\n\n3341. Find Minimum Time to Reach Last Room I\n2577. Minimum Time to Visit a Cell In a Grid\n\n# Intu
Recommended problems to get familiar with BFS & Min Heap\n\n[3341. Find Minimum Time to Reach Last Room I](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/)\n[2577. Minimum Time to Visit a Cell In a Grid](https://leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find minimum time to reach last room (aka room at [m-1][n-1]), we need to go to that room, starting from [0][0]. As we go through each room, we need to calculate at which time we get there.\nFor each step, it takes us 1 second or 2 second interleavely\n# Approach\n<!-- Describe your approach to solving the problem. -->\nInitialize a move array containing possible horizontal & vertical move\nInitialize a visited set to mark positions already are visited\nInitialize a min heap with initial value (0, 0, 0, 0) indicates (time, row, col, count)\nWith:\n- `time`: current time to get to that row, col\n- `row`, `col`: current position\n- `count`: number of steps\nImplement `isValid` function to validate a row, column should be visited or not.\n\nWhile heap is not empty:\nGet last element of heap. \nIf current position is at last room, return time\nIterate over moves array:\n    - For each move, calculate adjecent row `adjx` and adjeccent column `adjy`. If this position is valid, calculate `altTime` based on count value. Then push `newTime`, `adjx`, `adjy`, `count + 1` into heap.\n    - `newTime` is calculated by using max calue of moveTime at the position and current time, plus altTime\n    - Mark `adjx`, `adjy` visited\n\n# Complexity\n- Time complexity: O(m * n * log(m*n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m * n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minTimeToReach(self, moveTime: List[List[int]]) -> int:\n        moves = [\n          [0, 1],\n          [1, 0],\n          [0, -1],\n          [-1, 0]\n        ]\n        heap = [(0, 0, 0, 0)]\n        visited = set((0, 0))\n        numRows, numCols = len(moveTime), len(moveTime[0])\n        def isValid(row, col):\n          return (\n            0 <= row < numRows\n            and 0 <= col < numCols\n            and (row, col) not in visited\n          )\n        while heap:\n          time, row, col, count = heapq.heappop(heap)\n          if row == numRows - 1 and col == numCols - 1:\n            return time\n          for x, y in moves:\n            adjx = row + x\n            adjy = col + y\n            if isValid(adjx, adjy):\n              altTime = 1 if (count % 2 == 0) else 2\n              newTime = max(moveTime[adjx][adjy], time) + altTime\n              heappush(heap, (newTime, adjx, adjy, count + 1))\n              visited.add((adjx, adjy))\n        \n        return -1\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Python3']