The input in test 1 is confusing. Does it mean the following which is not an undirected graph?
0:4
1:1 2
2:0 2 3
3:0 1
4:1
5:0
6:3
How to input custom test
n = graph.size() in my demo
Input:
n
1 node
2 nodes
…
n
a
b
Welp… looks like this site doesnt support formatting that well
who tf wrote these javascript solutions. why is there a method to just get the key value pair. Honestly makes it more confusing and more code for no reason
private static List<Integer> getNeighbors(List<List<Integer>> graph, int node) {
return graph.get(node);
}I think its cause they’re trying to follow the “template”. Either way i’m just mad theres no native heap/pqueue support for js.
Structured Programming JS Solution:
function shortestPath(graph, root, target) {
const queue = [root];
const visited = new Set();
visited.add(root);
let level = -1;
let foundTarget = false;
while (queue.length > 0 && !foundTarget) {
level += 1;
for (
let i = 0;
i < queue.length && !foundTarget;
i++
) {
const node = queue.shift();
if (node == target) {
foundTarget = true;
} else {
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
visited.add(neighbor);
}
}
}
}
}
return level;
}
Same as other comments: more tests would be great. And adding a visual representation of the graph (in tests) could help to understand
hi guys, i use golang for this problem, at first i use my solution and Time limit exceeded happened.
so, i convert the solution to Golang but still have the time limit,
here’s my code.
func shortestPath(graph [][]int, a int, b int) int {
queue := make([]int, 0)
queue = append(queue, a)
visited := make(map[int]bool)
visited[a] = true
level := 0
for len(queue) > 0 {
n := len(queue)
for i:=0; i<n; i++ {
node := queue[0]
queue := queue[1:]
if node == b {
return level
}
for _, neighbour := range graph[node] {
if _, ok := visited[neighbour]; ok {
continue
}
queue = append(queue, neighbour)
visited[neighbour]=true
}
}
level++
}
return level
}
Is my code wrong? or is it a bug from algomonster? thanks
nevermind guys, it’s my code tehe
i took a little optimization in golang slice
func shortestPath(graph [][]int, a int, b int) int {
queue := make([]int, 0)
queue = append(queue, a)
visited := make(map[int]bool)
visited[a] = true
level :=0
for len(queue) > 0 {
n := len(queue)
for i:=0; i<n; i++ {
node := queue[i]
if node == b {
return level
}
for _, neighbour := range graph[node] {
if _, ok := visited[neighbour]; ok {
continue
}
queue = append(queue, neighbour)
visited[neighbour] = true
}
}
queue = queue[n:]
level++
}
return level
}
tests:
def test_shortestpath():
inputs = [
[[[1, 2], [0, 2, 3], [0, 1], [1]], 0, 3],
[
[
[1, 4],
[0, 2],
[1, 3],
[2, 4, 5],
[0, 3],
[3, 6, 9],
[5, 8],
[8, 9],
[6, 7],
[5, 7],
],
0,
7,
],
[[[1, 2], [0], [0]], 1, 2],
[[[1], [0]], 1, 0],
]
expected = [2, 5, 2, 1]
DFS Solution
from typing import List
def get_neighbors(graph, node):
return graph[node]
def shortest_path(graph: List[List[int]], a: int, b: int) -> int:
visited = set()
min_distance = float('inf')
def dfs(node, depth):
nonlocal min_distance, visited
if node == b:
min_distance = min(min_distance, depth)
return
visited.add(node)
for neighbor in get_neighbors(graph, node):
if neighbor not in visited:
dfs(neighbor, depth + 1)
visited.remove(node)
dfs(a, 0)
return min_distance if min_distance != float('inf') else -1
In Javascript the time complexity for Array.shift() is O(n) in the worst case. Wouldn’t it impact the overall time complexity for the solution, since it is inside the loop?
you mistake was local reinitializing queue, instead of updating the global queue
queue := queue[1:]
change it to
queue = queue[1:]