LeetCode 2814: Minimum Time Takes to Reach Destination Without Drowning Solution

Master LeetCode problem 2814 (Minimum Time Takes to Reach Destination Without Drowning), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2814. Minimum Time Takes to Reach Destination Without Drowning

Hard

Array Breadth-First Search Matrix

Problem Explanation

Explanation:

This problem can be solved using Dijkstra's algorithm with a slight modification to handle the constraints given. The idea is to maintain a priority queue of nodes to visit, where the priority is based on the arrival time at that node. We initialize the priority queue with the starting node and its arrival time as 0. At each step, we pop the node with the minimum arrival time from the priority queue and update the arrival time of its neighbors based on the constraints provided in the problem. We continue this process until we reach the destination node or exhaust all reachable nodes.

Algorithm:

Create a priority queue (min heap) to store nodes based on their arrival time.
Initialize the priority queue with the starting node and arrival time as 0.
While the priority queue is not empty:
- Pop the node with the minimum arrival time from the priority queue.
- If the popped node is the destination, return its arrival time.
- Update the arrival time of its neighbors based on the constraints:
  - If the water level at the neighbor's arrival time is less than or equal to the current water level and the neighbor's arrival time is greater than the current arrival time plus the time taken to travel to that neighbor, update the neighbor's arrival time and push it back to the priority queue.
If the destination node is not reachable, return -1.

Time Complexity:

The time complexity of this algorithm is O((V + E) log V), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity:

The space complexity is O(V) to store the nodes in the priority queue.

: :

Solution Code

import java.util.*;

class Solution {
    public int minimumTime(int[][] obstacles, int[] source, int[] destination) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m = obstacles.length, n = obstacles[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{source[0], source[1], 0});
        dist[source[0]][source[1]] = 0;
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], time = cur[2];
            if (x == destination[0] && y == destination[1]) {
                return time;
            }
            
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int nt = Math.max(time, dist[x][y]);
                    if (nt < dist[nx][ny] && nt < obstacles[nx][ny]) {
                        dist[nx][ny] = nt;
                        pq.offer(new int[]{nx, ny, nt});
                    }
                }
            }
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2814 (Minimum Time Takes to Reach Destination Without Drowning)?

This page provides optimized solutions for LeetCode problem 2814 (Minimum Time Takes to Reach Destination Without Drowning) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2814 (Minimum Time Takes to Reach Destination Without Drowning)?

The time complexity for LeetCode 2814 (Minimum Time Takes to Reach Destination Without Drowning) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2814 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2814 in Java, C++, or Python.

Back to LeetCode Solutions