2538. Difference Between Maximum and Minimum Price Sum LeetCode Solution
In this guide, you will get 2538. Difference Between Maximum and Minimum Price Sum LeetCode Solution with the best time and space complexity. The solution to Difference Between Maximum and Minimum Price Sum 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 Difference Between Maximum and Minimum Price Sum
There exists an undirected and initially unrooted tree with n nodes indexed from 0 to n – 1. You are given the integer n and 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.
Each node has an associated price. You are given an integer array price, where price[i] is the price of the ith node.
The price sum of a given path is the sum of the prices of all nodes lying on that path.
The tree can be rooted at any node root of your choice. The incurred cost after choosing root is the difference between the maximum and minimum price sum amongst all paths starting at root.
Return the maximum possible cost amongst all possible root choices.
Example 1:
Input: n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
Output: 24
Explanation: The diagram above denotes the tree after rooting it at node 2. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum.
– The first path contains nodes [2,1,3,4]: the prices are [7,8,6,10], and the sum of the prices is 31.
– The second path contains the node [2] with the price [7].
The difference between the maximum and minimum price sum is 24. It can be proved that 24 is the maximum cost.
Input: n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
Output: 2
Explanation: The diagram above denotes the tree after rooting it at node 0. The first part (colored in red) shows the path with the maximum price sum. The second part (colored in blue) shows the path with the minimum price sum.
– The first path contains nodes [0,1,2]: the prices are [1,1,1], and the sum of the prices is 3.
– The second path contains node [0] with a price [1].
The difference between the maximum and minimum price sum is 2. It can be proved that 2 is the maximum cost.
Constraints:
1 <= n <= 105
edges.length == n – 1
0 <= ai, bi <= n – 1
edges represents a valid tree.
price.length == n
1 <= price[i] <= 105
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2538. Difference Between Maximum and Minimum Price Sum LeetCode Solution in C++
class Solution {
public:
long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
int ans = 0;
vector<vector<int>> tree(n);
// maxSums[i] := the maximum the sum of path rooted at i
vector<int> maxSums(n);
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);
}
// Precalculate `maxSums`.
maxSum(tree, 0, /*prev=*/-1, maxSums, price);
reroot(tree, 0, /*prev=*/-1, /*parentSum=*/0, maxSums, price, ans);
return ans;
}
private:
int maxSum(const vector<vector<int>>& tree, int u, int prev,
vector<int>& maxSums, const vector<int>& price) {
int maxChildSum = 0;
for (const int v : tree[u])
if (v != prev)
maxChildSum = max(maxChildSum, maxSum(tree, v, u, maxSums, price));
return maxSums[u] = price[u] + maxChildSum;
}
void reroot(const vector<vector<int>>& tree, int u, int prev, int parentSum,
const vector<int>& maxSums, const vector<int>& price, int& ans) {
// Get the top two subtree sums and the top one node index.
int maxSubtreeSum1 = 0;
int maxSubtreeSum2 = 0;
int maxNode = -1;
for (const int v : tree[u]) {
if (v == prev)
continue;
if (maxSums[v] > maxSubtreeSum1) {
maxSubtreeSum2 = maxSubtreeSum1;
maxSubtreeSum1 = maxSums[v];
maxNode = v;
} else if (maxSums[v] > maxSubtreeSum2) {
maxSubtreeSum2 = maxSums[v];
}
}
if (tree[u].size() == 1)
ans = max({ans, parentSum, maxSubtreeSum1});
for (const int v : tree[u]) {
if (v == prev)
continue;
const int nextParentSum =
(v == maxNode ? price[u] + max(parentSum, maxSubtreeSum2)
: price[u] + max(parentSum, maxSubtreeSum1));
reroot(tree, v, u, nextParentSum, maxSums, price, ans);
}
}
}; /* code provided by PROGIEZ */
2538. Difference Between Maximum and Minimum Price Sum LeetCode Solution in Java
class Solution {
public long maxOutput(int n, int[][] edges, int[] price) {
List<Integer>[] tree = new List[n];
// maxSums[i] := the maximum the sum of path rooted at i
int[] maxSums = new int[n];
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);
}
// Precalculate `maxSums`.
maxSum(tree, 0, /*prev=*/-1, maxSums, price);
reroot(tree, 0, /*prev=*/-1, /*parentSum=*/0, maxSums, price);
return (long) ans;
}
private int ans = 0;
private int maxSum(List<Integer>[] tree, int u, int prev, int[] maxSums, int[] price) {
int maxChildSum = 0;
for (final int v : tree[u])
if (v != prev)
maxChildSum = Math.max(maxChildSum, maxSum(tree, v, u, maxSums, price));
return maxSums[u] = price[u] + maxChildSum;
}
private void reroot(List<Integer>[] tree, int u, int prev, int parentSum, int[] maxSums,
int[] price) {
// Get top two sums and top one node index.
int maxSubtreeSum1 = 0;
int maxSubtreeSum2 = 0;
int maxNode = -1;
for (final int v : tree[u]) {
if (v == prev)
continue;
if (maxSums[v] > maxSubtreeSum1) {
maxSubtreeSum2 = maxSubtreeSum1;
maxSubtreeSum1 = maxSums[v];
maxNode = v;
} else if (maxSums[v] > maxSubtreeSum2) {
maxSubtreeSum2 = maxSums[v];
}
}
if (tree[u].size() == 1)
ans = Math.max(ans, Math.max(parentSum, maxSubtreeSum1));
for (final int v : tree[u]) {
if (v == prev)
continue;
final int nextParentSum = (v == maxNode ? price[u] + Math.max(parentSum, maxSubtreeSum2)
: price[u] + Math.max(parentSum, maxSubtreeSum1));
reroot(tree, v, u, nextParentSum, maxSums, price);
}
}
} // code provided by PROGIEZ
2538. Difference Between Maximum and Minimum Price Sum LeetCode Solution in Python
class Solution:
def maxOutput(self, n: int, edges: list[list[int]], price: list[int]) -> int:
ans = 0
tree = [[] for _ in range(n)]
maxSums = [0] * n # maxSums[i] := the maximum the sum of path rooted at i
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
def maxSum(u: int, prev: int) -> int:
maxChildSum = 0
for v in tree[u]:
if v != prev:
maxChildSum = max(maxChildSum, maxSum(v, u))
maxSums[u] = price[u] + maxChildSum
return maxSums[u]
# Precalculate `maxSums`.
maxSum(0, -1)
def reroot(u: int, prev: int, parentSum: int) -> None:
nonlocal ans
# Get the top two subtree sums and the top one node index.
maxSubtreeSum1 = 0
maxSubtreeSum2 = 0
maxNode = -1
for v in tree[u]:
if v == prev:
continue
if maxSums[v] > maxSubtreeSum1:
maxSubtreeSum2 = maxSubtreeSum1
maxSubtreeSum1 = maxSums[v]
maxNode = v
elif maxSums[v] > maxSubtreeSum2:
maxSubtreeSum2 = maxSums[v]
if len(tree[u]) == 1:
ans = max(ans, parentSum, maxSubtreeSum1)
for v in tree[u]:
if v == prev:
continue
nextParentSum = (
price[u] + max(parentSum, maxSubtreeSum2) if v == maxNode else
price[u] + max(parentSum, maxSubtreeSum1))
reroot(v, u, nextParentSum)
reroot(0, -1, 0)
return ans # code by PROGIEZ
