javascriptpythonalgorithmdata-structuresgraph

# LeetCode 2467: Most Profitable Path in a Tree

For LeetCode Problem 2467, I am using the following Python solution that is posted on Leetcode which passes all tests.

``````import collections
class Solution:
def mostProfitablePath(self, edges, bob: int, amount) -> int:
graph = collections.defaultdict(list)
for n1, n2 in edges:
graph[n1].append(n2)
graph[n2].append(n1)

# depth of bob traversal path (DFS)
self.bob_path = []
def dfs(node, parent, path):
if node == 0:
self.bob_path = list(path)
return True

for neighbor in graph[node]:
if neighbor == parent:
continue
path.append(neighbor)
if dfs(neighbor, node, path):
return True
path.pop()

return False

dfs(bob, -1, [bob])
step = dict()
for i in range(len(self.bob_path)):
step[self.bob_path[i]] = i

# loop all possible Alice traversal path (BFS)
ans = float('-Inf')
# Base case if bob is also at node 0
profit_ini = amount[0] if bob != 0 else amount[0] // 2

que = collections.deque([(0, -1, profit_ini)])
depth = 0
while que:
# For loop is to make sure we iterate over every node in level before moving on to next level and seperate nodes on each level with depth counter
for _ in range(len(que)):
cur, parent, profit = que.pop(0)

# Not the root node and it only has one connection == leaf node ==> update potential answer
if cur != 0 and len(graph[cur]) == 1:
ans = max(ans, profit)

for neighbor in graph[cur]:
if neighbor == parent:
continue
# case where either alice node was not encountered by bob or it is in bob's path but he is not yet there
if neighbor not in step or depth + 1 < step[neighbor]:
new_profit = amount[neighbor]
# Reached at same time (depth of neighbor == the depth of bob (as indicated by i in step))
elif depth + 1 == step[neighbor]:
new_profit = amount[neighbor] // 2
else:
new_profit = 0
que.append((neighbor, cur, profit + new_profit))

depth += 1

return ans
``````

I am attempting to translate the solution to Javascript and one test case fails and I don't understand why. Could this be caused by a typo or by the way Javascript handles comparisons, division, etc.?

``````/**
* @param {number[][]} edges
* @param {number} bob
* @param {number[]} amount
* @return {number}
*/
var mostProfitablePath = function (edges, bob, amount) {
let n = amount.length
let graph = new Array(n).fill(0).map(() => [])

for (const [n1, n2] of edges) {
graph[n1].push(n2)
graph[n2].push(n1)
}

var DFS = (node, parent, path) => {
if (node === 0) {
return path
}

for (const neighbor of graph[node]) {
if (neighbor === parent) {
continue
}
path.push(neighbor)
let result = DFS(neighbor, node, path)
if (result !== undefined && result !== false) {
return result
}
path.pop()
}
return false
}

let bob_path = DFS(bob, -1, [bob])
let step = {}
for (let i = 0; i < bob_path.length; i++) {
step[bob_path[i]] = i
}

let ans = -Infinity
let ini_profit = bob_path[0] === 0 ? Math.floor(amount[0] / 2) : amount[0]
let depth = 0
let queue = [[0, -1, ini_profit]]

while (queue.length) {
for (let j = 0; j < queue.length; j++) {
let [cur, parent, profit] = queue.shift()

if (graph[cur].length === 1 && cur != 0) {
ans = Math.max(profit, ans)
}

for (const neighbor of graph[cur]) {
if (neighbor === parent) continue

let new_profit
if (!step.hasOwnProperty(neighbor) || depth + 1 < step[neighbor]) {
new_profit = amount[neighbor]
}
else if (depth + 1 === step[neighbor]) {
new_profit = Math.floor(amount[neighbor] / 2)
} else {
new_profit = 0
}
queue.push([neighbor, cur, new_profit + profit])
}
}
depth++
}

return ans
};
``````

Test Case for which is fails:

``````edges =
[[0,38],[0,59],[1,30],[1,62],[1,53],[2,41],[2,37],[3,21],[4,35],[4,54],[5,32],[5,69],[6,26],[6,16],[6,61],[6,52],[7,34],[8,10],[9,11],[9,43],[10,48],[11,29],[12,63],[12,58],[12,13],[13,36],[13,34],[14,65],[14,15],[15,17],[15,49],[16,40],[17,20],[17,24],[18,58],[19,25],[21,34],[22,55],[23,45],[23,59],[25,43],[27,32],[28,49],[28,33],[31,61],[33,39],[33,51],[33,53],[34,68],[34,69],[37,52],[42,52],[43,61],[44,58],[46,49],[47,55],[47,50],[48,56],[48,66],[50,58],[52,66],[52,65],[53,57],[54,63],[55,57],[59,60],[59,67],[59,65],[64,69]]

bob =
47

amount =
[4664,5822,-9152,7258,-5468,4698,2568,9880,-4046,9884,-3540,-2260,5264,-7050,-6998,-1688,-6256,-5350,5136,7476,-4108,1288,1336,-6126,2940,698,-2900,-2342,-2310,858,572,640,-9674,5746,5068,7128,636,6680,-1840,3574,7592,-5882,-1974,-2766,-620,1088,-8930,7756,9966,380,8884,-954,-8198,-5862,-3100,7728,7090,-4648,4076,994,4232,9810,-2904,-1106,-4172,-5884,-9582,5320,-4086,6346]

Output
16435
Expected
17590
``````

Solution

• You have not converted the Python code correctly at this point:

``````for _ in range(len(que)):
``````

to:

``````for (let j = 0; j < queue.length; j++) {
``````

The difference is that Python evaluates `len(que)` once, while your JavaScript code evaluates `queue.length` at the start of each iteration. And this has an impact because the loop adds items to the queue.

So make sure to only evaluate `queue.length` once. For example, it could be like this:

``````for (let j = queue.length; j > 0; j--) {
``````

With that correction it will work.