Dijkstra’s Magic | Find the Fastest Path | C++ | Java | Python | JavaScript 🚀
\n# \u2B06\uFE0FUpvote if it helps \u2B06\uFE0F  \n\n---\n\n## Connect with me on Linkedin Bijoy Sing.\n\n---\n\n\n###### Solution in C++, Python, Java, and Jav
\n# \u2B06\uFE0FUpvote if it helps \u2B06\uFE0F  \n\n---\n\n## Connect with me on Linkedin [Bijoy Sing](https://www.linkedin.com/in/bijoy-sing-236a5a1b2/).\n\n---\n\n\n###### *Solution in C++, Python, Java, and JavaScript*\n\n```cpp []\nclass Solution {\npublic:\n    int minimumTime(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n\n        // Check if it\'s impossible to reach the destination from the start\n        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n\n        vector<vector<int>> time(m + 1, vector<int>(n + 1, INT_MAX));\n        vector<vector<int>> vis(m + 1, vector<int>(n + 1, 0));\n\n        priority_queue<pair<int, pair<int, int>>, \n                        vector<pair<int, pair<int, int>>>, \n                        greater<pair<int, pair<int, int>>>> pq;\n        pq.push({0, {0, 0}});  // Start from the top-left corner\n\n        int x[] = {0, 0, 1, -1};\n        int y[] = {1, -1, 0, 0};\n\n        while (!pq.empty()) {\n            auto p = pq.top();\n            pq.pop();\n\n            int t = p.first;\n            int curx = p.second.first;\n            int cury = p.second.second;\n\n            // Return time if we reach the bottom-right corner\n            if (curx == m - 1 && cury == n - 1) {\n                return t;\n            }\n\n            if (vis[curx][cury]) continue;\n            vis[curx][cury] = 1;\n\n            for (int i = 0; i < 4; i++) {\n                int newx = curx + x[i];\n                int newy = cury + y[i];\n\n                if (newx >= 0 && newx < m && newy >= 0 && newy < n) {\n                    int needtime = t + 1;\n\n                    // Adjust time based on grid values\n                    if (grid[newx][newy] > t + 1) {\n                        int diff = grid[newx][newy] - t;\n                        needtime = (diff % 2) ? grid[newx][newy] : grid[newx][newy] + 1;\n                    }\n\n                    if (needtime < time[newx][newy]) {\n                        time[newx][newy] = needtime;\n                        pq.push({needtime, {newx, newy}});\n                    }\n                }\n            }\n        }\n\n        return -1;\n    }\n};\n```\n\n```python []\nclass Solution:\n    def minimumTime(self, grid):\n        m = len(grid)\n        n = len(grid[0])\n\n        # Check if it\'s impossible to reach the destination from the start\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n\n        time = [[float(\'inf\')] * (n + 1) for _ in range(m + 1)]\n        vis = [[0] * (n + 1) for _ in range(m + 1)]\n\n        pq = []\n        heapq.heappush(pq, (0, (0, 0)))  # Start from the top-left corner\n\n        x = [0, 0, 1, -1]\n        y = [1, -1, 0, 0]\n\n        while pq:\n            t, (curx, cury) = heapq.heappop(pq)\n\n            # Return time if we reach the bottom-right corner\n            if curx == m - 1 and cury == n - 1:\n                return t\n\n            if vis[curx][cury]:\n                continue\n            vis[curx][cury] = 1\n\n            for i in range(4):\n                newx = curx + x[i]\n                newy = cury + y[i]\n\n                if 0 <= newx < m and 0 <= newy < n:\n                    needtime = t + 1\n\n                    # Adjust time based on grid values\n                    if grid[newx][newy] > t + 1:\n                        diff = grid[newx][newy] - t\n                        needtime = grid[newx][newy] if diff % 2 else grid[newx][newy] + 1\n\n                    if needtime < time[newx][newy]:\n                        time[newx][newy] = needtime\n                        heapq.heappush(pq, (needtime, (newx, newy)))\n\n        return -1\n```\n\n```java []\nclass Solution {\n    public int minimumTime(int[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n\n        // Check if it\'s impossible to reach the destination from the start\n        if (grid[0][1] > 1 && grid[1][0] > 1)\n            return -1;\n\n        int[][] time = new int[m + 1][n + 1];\n        int[][] vis = new int[m + 1][n + 1];\n\n        for (int i = 0; i <= m; i++) {\n            for (int j = 0; j <= n; j++) {\n                vis[i][j] = 0;\n                time[i][j] = Integer.MAX_VALUE;\n            }\n        }\n\n        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));\n        pq.add(new int[]{0, 0, 0});  // Start from the top-left corner\n\n        int[] x = {0, 0, 1, -1};\n        int[] y = {1, -1, 0, 0};\n\n        while (!pq.isEmpty()) {\n            int[] p = pq.poll();\n            int t = p[0];\n            int curx = p[1];\n            int cury = p[2];\n\n            // Return time if we reach the bottom-right corner\n            if (curx == m - 1 && cury == n - 1) {\n                return t;\n            }\n\n            if (vis[curx][cury] == 1) continue;\n            vis[curx][cury] = 1;\n\n            for (int i = 0; i < 4; i++) {\n                int newx = curx + x[i];\n                int newy = cury + y[i];\n\n                if (newx >= 0 && newx < m && newy >= 0 && newy < n) {\n                    int needtime = t + 1;\n\n                    // Adjust time based on grid values\n                    if (grid[newx][newy] > t + 1) {\n                        int diff = grid[newx][newy] - t;\n                        if (diff % 2 == 1)\n                            needtime = grid[newx][newy];\n                        else\n                            needtime = grid[newx][newy] + 1;\n                    }\n\n                    if (needtime < time[newx][newy]) {\n                        time[newx][newy] = needtime;\n                        pq.add(new int[]{needtime, newx, newy});\n                    }\n                }\n            }\n        }\n\n        return -1;\n    }\n}\n```\n\n```javascript []\nclass Solution {\n    minimumTime(grid) {\n        const m = grid.length;\n        const n = grid[0].length;\n\n        // Check if it\'s impossible to reach the destination from the start\n        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;\n\n        const time = Array.from({ length: m + 1 }, () => Array(n + 1).fill(Infinity));\n        const vis = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));\n\n        const pq = [];\n        pq.push([0, 0, 0]);  // Start from the top-left corner\n\n        const x = [0, 0, 1, -1];\n        const y = [1, -1, 0, 0];\n\n        while (pq.length) {\n            pq.sort((a, b) => a[0] - b[0]);\n            const [t, curx, cury] = pq.shift();\n\n            // Return time if we reach the bottom-right corner\n            if (curx === m - 1 && cury === n - 1) {\n                return t;\n            }\n\n            if (vis[curx][cury]) continue;\n            vis[curx][cury] = 1;\n\n            for (let i = 0; i < 4; i++) {\n                const newx = curx + x[i];\n                const newy = cury + y[i];\n\n                if (newx >= 0 && newx < m && newy >= 0 && newy < n) {\n                    let needtime = t + 1;\n\n                    // Adjust time based on grid values\n                    if (grid[newx][newy] > t + 1) {\n                        const diff = grid[newx][newy] - t;\n                        needtime = diff % 2 ? grid[newx][newy] : grid[newx][newy] + 1;\n                    }\n\n                    if (needtime < time[newx][newy]) {\n                        time[newx][newy] = needtime;\n                        pq.push([\n\nneedtime, newx, newy]);\n                    }\n                }\n            }\n        }\n\n        return -1;\n    }\n}\n```\n\n\n---\n\n# Intuition\nThe problem is about finding the minimum time required to travel from the top-left corner to the bottom-right corner of a grid, where each cell has a time delay that varies based on the previous time spent. The goal is to determine the shortest time by navigating through the grid while respecting these delays.\n\nWe can treat this problem as a shortest path problem on a weighted graph. Each grid cell is a node, and the edges between nodes are the possible movements between adjacent cells, with edge weights determined by the time constraints of the grid.\n\n# Approach\nWe will use **Dijkstra\'s algorithm**, a well-known algorithm for finding the shortest path in a graph with non-negative edge weights. The key idea is:\n1. Initialize a priority queue to store the current minimum time to reach each cell.\n2. Start from the top-left corner (0,0) and initialize the time taken to reach it as 0.\n3. For each cell, explore its neighboring cells (up, down, left, right) and update their minimum travel time.\n4. If a cell\'s new computed time is less than its previously computed time, update it and push the new time into the priority queue.\n5. Stop when we reach the bottom-right corner, at which point the accumulated time will be the minimum time.\n\n# Complexity\n- **Time complexity**: $$O(E \\log V)$$  \n  Where \\(E\\) is the number of edges (which is approximately \\(4 \\times m \\times n\\)) and \\(V\\) is the number of vertices (which is \\(m \\times n\\)). The log factor arises from the priority queue operations.\n\n- **Space complexity**: $$O(m \\times n)$$  \n  We use two \\(m \\times n\\) matrices: one for the `time` array (storing the shortest times to reach each cell) and one for the `visited` array.\n\n---\n# Feel free to comment! \uD83D\uDE0A\n### *If you have any questions or need further clarification, feel free to drop a comment below! I\'m happy to help!*
['Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']