LeetCode 2714: Find Shortest Path with K Hops Solution

Master LeetCode problem 2714 (Find Shortest Path with K Hops), 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.

2714. Find Shortest Path with K Hops

Hard

Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation:

To solve this problem, we can use Dijkstra's algorithm with a slight modification to track the number of hops as well. We maintain a priority queue to explore the nodes with the shortest distance and hops first. We keep track of the number of hops made so far while exploring the nodes. Whenever we reach the destination node within the specified number of hops (k), we return the shortest distance to that node.

Algorithm:

Initialize a priority queue to store the nodes with their distance and number of hops.
Add the source node to the priority queue with distance 0 and hops 0.
While the priority queue is not empty, do the following:
- Pop the node with the smallest distance and hops from the priority queue.
- If this node is the destination node and the number of hops is less than or equal to k, return the distance.
- Explore the neighbors of the current node and update their distance and hops in the priority queue if it results in a shorter path.
If the destination node is not reached within k hops, 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) for the priority queue and O(V) for the graph representation.

: :

Solution Code

import java.util.*;

class Solution {
    public int findShortestPath(int[][] graph, int src, int dst, int k) {
        int n = graph.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, src, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int distance = curr[0];
            int node = curr[1];
            int hops = curr[2];

            if (node == dst && hops <= k) {
                return distance;
            }

            if (hops > k) {
                continue;
            }

            for (int[] neighbor : graph[node]) {
                int nextNode = neighbor[0];
                int edgeWeight = neighbor[1];
                pq.offer(new int[]{distance + edgeWeight, nextNode, hops + 1});
            }
        }

        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2714 (Find Shortest Path with K Hops)?

This page provides optimized solutions for LeetCode problem 2714 (Find Shortest Path with K Hops) 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 2714 (Find Shortest Path with K Hops)?

The time complexity for LeetCode 2714 (Find Shortest Path with K Hops) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2714 on DevExCode?

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

Back to LeetCode Solutions