2467. Most Profitable Path in a Tree LeetCode Solution
In this guide, you will get 2467. Most Profitable Path in a Tree LeetCode Solution with the best time and space complexity. The solution to Most Profitable Path in a Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Most Profitable Path in a Tree
There is an undirected tree with n nodes labeled from 0 to n – 1, rooted at node 0. You are given a 2D integer array edges of length n – 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
At every node i, there is a gate. You are also given an array of even integers amount, where amount[i] represents:
the price needed to open the gate at node i, if amount[i] is negative, or,
the cash reward obtained on opening the gate at node i, otherwise.
The game goes on as follows:
Initially, Alice is at node 0 and Bob is at node bob.
At every second, Alice and Bob each move to an adjacent node. Alice moves towards some leaf node, while Bob moves towards node 0.
For every node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:
If the gate is already open, no price will be required, nor will there be any cash reward.
If Alice and Bob reach the node simultaneously, they share the price/reward for opening the gate there. In other words, if the price to open the gate is c, then both Alice and Bob pay c / 2 each. Similarly, if the reward at the gate is c, both of them receive c / 2 each.
If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node 0, he stops moving. Note that these events are independent of each other.
Return the maximum net income Alice can have if she travels towards the optimal leaf node.
Example 1:
Input: edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
Output: 6
Explanation:
The above diagram represents the given tree. The game goes as follows:
– Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes.
Alice’s net income is now -2.
– Both Alice and Bob move to node 1.
Since they reach here simultaneously, they open the gate together and share the reward.
Alice’s net income becomes -2 + (4 / 2) = 0.
– Alice moves on to node 3. Since Bob already opened its gate, Alice’s income remains unchanged.
Bob moves on to node 0, and stops moving.
– Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6.
Now, neither Alice nor Bob can make any further moves, and the game ends.
It is not possible for Alice to get a higher net income.
Example 2:
Input: edges = [[0,1]], bob = 1, amount = [-7280,2350]
Output: -7280
Explanation:
Alice follows the path 0->1 whereas Bob follows the path 1->0.
Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280.
Constraints:
2 <= n <= 105
edges.length == n – 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.
1 <= bob < n
amount.length == n
amount[i] is an even integer in the range [-104, 104].
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2467. Most Profitable Path in a Tree LeetCode Solution in C++
class Solution {
public:
int mostProfitablePath(vector<vector<int>>& edges, int bob,
vector<int>& amount) {
const int n = amount.size();
vector<vector<int>> tree(n);
vector<int> parent(n);
vector<int> aliceDist(n, -1);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(tree, 0, -1, 0, parent, aliceDist);
// Modify the amount along the path from node Bob to node 0.
// For each node,
// 1. If Bob reaches earlier than Alice does, change the amount to 0.
// 2. If Bob and Alice reach simultaneously, devide the amount by 2.
for (int u = bob, bobDist = 0; u != 0; u = parent[u], ++bobDist)
if (bobDist < aliceDist[u])
amount[u] = 0;
else if (bobDist == aliceDist[u])
amount[u] /= 2;
return getMoney(tree, 0, -1, amount);
}
private:
// Fills `parent` and `dist`.
void dfs(const vector<vector<int>>& tree, int u, int prev, int d,
vector<int>& parent, vector<int>& dist) {
parent[u] = prev;
dist[u] = d;
for (const int v : tree[u]) {
if (dist[v] == -1)
dfs(tree, v, u, d + 1, parent, dist);
}
}
int getMoney(const vector<vector<int>>& tree, int u, int prev,
const vector<int>& amount) {
// a leaf node
if (tree[u].size() == 1 && tree[u][0] == prev)
return amount[u];
int maxPath = INT_MIN;
for (const int v : tree[u])
if (v != prev)
maxPath = max(maxPath, getMoney(tree, v, u, amount));
return amount[u] + maxPath;
}
}; /* code provided by PROGIEZ */
2467. Most Profitable Path in a Tree LeetCode Solution in Java
class Solution {
public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
final int n = amount.length;
List<Integer>[] tree = new List[n];
int[] parent = new int[n];
int[] aliceDist = new int[n];
Arrays.fill(aliceDist, -1);
for (int i = 0; i < n; ++i)
tree[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
tree[u].add(v);
tree[v].add(u);
}
dfs(tree, 0, -1, 0, parent, aliceDist);
// Modify the amount along the path from node Bob to node 0.
// For each node,
// 1. If Bob reaches earlier than Alice does, change the amount to 0.
// 2. If Bob and Alice reach simultaneously, devide the amount by 2.
for (int u = bob, bobDist = 0; u != 0; u = parent[u], ++bobDist)
if (bobDist < aliceDist[u])
amount[u] = 0;
else if (bobDist == aliceDist[u])
amount[u] /= 2;
return getMoney(tree, 0, -1, amount);
}
// Fills `parent` and `dist`.
private void dfs(List<Integer>[] tree, int u, int prev, int d, int[] parent, int[] dist) {
parent[u] = prev;
dist[u] = d;
for (final int v : tree[u]) {
if (dist[v] == -1)
dfs(tree, v, u, d + 1, parent, dist);
}
}
private int getMoney(List<Integer>[] tree, int u, int prev, int[] amount) {
// a leaf node
if (tree[u].size() == 1 && tree[u].get(0) == prev)
return amount[u];
int maxPath = Integer.MIN_VALUE;
for (final int v : tree[u])
if (v != prev)
maxPath = Math.max(maxPath, getMoney(tree, v, u, amount));
return amount[u] + maxPath;
}
} // code provided by PROGIEZ
2467. Most Profitable Path in a Tree LeetCode Solution in Python
class Solution:
def mostProfitablePath(
self,
edges: list[list[int]],
bob: int,
amount: list[int],
) -> int:
n = len(amount)
tree = [[] for _ in range(n)]
parent = [0] * n
aliceDist = [-1] * n
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
# Fills `parent` and `aliceDist`.
def dfs(u: int, prev: int, d: int) -> None:
parent[u] = prev
aliceDist[u] = d
for v in tree[u]:
if aliceDist[v] == -1:
dfs(v, u, d + 1)
dfs(0, -1, 0)
# Modify amount athe path from node bob to node 0.
# For each node,
# 1. If Bob reaches earlier than Alice does, change the amount to 0.
# 2. If Bob and Alice reach simultaneously, devide the amount by 2.
u = bob
bobDist = 0
while u != 0:
if bobDist < aliceDist[u]:
amount[u] = 0
elif bobDist == aliceDist[u]:
amount[u] //= 2
u = parent[u]
bobDist += 1
return self._getMoney(tree, 0, -1, amount)
def _getMoney(
self,
tree: list[list[int]],
u: int,
prev: int,
amount: list[int],
) -> int:
# a leaf node
if len(tree[u]) == 1 and tree[u][0] == prev:
return amount[u]
maxPath = -math.inf
for v in tree[u]:
if v != prev:
maxPath = max(maxPath, self._getMoney(tree, v, u, amount))
return amount[u] + maxPath # code by PROGIEZ
