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.

- How not to overwrite user data in FireStore for returning user when login using Angularifre?
- using spread operator in typescript
- javascript postMessage not working
- Is there a way to add/remove several classes in one single instruction with classList?
- Appending .js extension on relative import statements during Typescript compilation (ES6 modules)
- How do I "preventDefault" for custom events
- React Hooks useState+useEffect+event gives stale state
- How to check if a string ONLY contains specific strings
- How to prevent changes to a prototype?
- Creating a textarea with auto-resize
- Javascript file upload - PDF to image(s)
- Truncate number to two decimal places without rounding
- How browsers store data for autocomplete and where?
- Debt Snowball Function
- JSON Web Token (JWT) Error: Invalid Signature with RSA Key Pairs
- What a RegEx that can match text in parentheses with nested parentheses
- How would I get the full response from this Axios request?
- next js - the style of the tailwind class i get from API doesnt apply on my element
- How can I disable sort on a specific element?
- Is it a bad idea to use the meta tag in HTML to specify custom metadata for retrieval with JavaScript?
- Detecting when user scrolls to bottom of div with React js
- Mongoose partial update of an object
- in javascript, how do you sort a subset of an array?
- Firebase email link authentication leads to a page that says "Error encountered" - "The selected page mode is invalid"
- How to fire window.scrollY only one time
- How to call a method from child component to parent one in vue2?
- Switch value for clicked button from group of buttons in jQuery
- Smooth scroll to specific div on click
- How to use MaterializeCss with Vue.js?
- Can't find variable: React