LeetCode 2538: Difference Between Maximum and Minimum Price Sum
Problem Description
Explanation
To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the tree and calculate the maximum and minimum price sum for each subtree rooted at a particular node. We can maintain two arrays to store the maximum and minimum price sum for each node. We can then calculate the cost (difference between maximum and minimum sum) for each node as the maximum difference between the maximum and minimum sum of its children nodes plus the price of the current node. The answer will be the maximum cost over all nodes considered as the root.
Time Complexity: O(n) where n is the number of nodes in the tree
Space Complexity: O(n) for storing the maximum and minimum price sums
Solutions
class Solution {
int[] maxSum;
int[] minSum;
int[] price;
List<List<Integer>> adjList;
int answer;
public int maxCost(int n, int[][] edges, int[] prices) {
maxSum = new int[n];
minSum = new int[n];
price = prices;
adjList = new ArrayList<>();
answer = 0;
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
for (int[] edge : edges) {
adjList.get(edge[0]).add(edge[1]);
adjList.get(edge[1]).add(edge[0]);
}
dfs(0, -1);
return answer;
}
private void dfs(int node, int parent) {
maxSum[node] = price[node];
minSum[node] = price[node];
int maxChild = Integer.MIN_VALUE;
int minChild = Integer.MAX_VALUE;
for (int child : adjList.get(node)) {
if (child == parent) continue;
dfs(child, node);
maxSum[node] = Math.max(maxSum[node], maxSum[child]);
minSum[node] = Math.min(minSum[node], minSum[child]);
maxChild = Math.max(maxChild, maxSum[child]);
minChild = Math.min(minChild, minSum[child]);
}
answer = Math.max(answer, Math.max(Math.abs(maxSum[node] - minChild), Math.abs(maxChild - minSum[node])));
}
}Loading editor...