Difference Between Maximum and Minimum Price Sum

Hard

#2318Time: O(N^2), where N is the number of nodes. For each of the N possible roots, we perform a graph traversal (BFS/DFS) which takes O(N + E) time. Since it's a tree, E = N-1, so each traversal is O(N). The total time complexity is N * O(N) = O(N^2).Space: O(N), where N is the number of nodes. We need O(N) space for the adjacency list. Additionally, during each traversal, we use a queue or recursion stack and a visited array, which take O(N) space.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree.

Each node has an associated price. You are given an integer array price, where price[i] is the price of the i^th 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.

Example 2:

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 <= 10⁵
edges.length == n - 1
0 <= a_i, b_i <= n - 1
edges represents a valid tree.
price.length == n
1 <= price[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process described in the problem. We can iterate through every node, consider it as the root, calculate the cost associated with it, and find the maximum cost among all possible roots.

Algorithm

Build an adjacency list representation of the tree from the edges array.\n- Initialize a variable max_cost to 0.\n- Iterate through each node i from 0 to n-1, considering it as the potential root.\n- For each i, perform a graph traversal (like BFS) starting from i to find the maximum price sum of a path starting at i.\n- In the traversal, maintain the sum of prices along the current path. Keep track of the maximum sum found.\n- After the traversal, calculate the cost for root i as max_path_sum_from_i - price[i].\n- Update max_cost = max(max_cost, cost_for_i).\n- After iterating through all nodes, max_cost will hold the result.

Walkthrough

For each node i from 0 to n-1, we treat it as the root of the tree. The cost for a given root is the difference between the maximum and minimum price sum of all paths starting from that root. The minimum price sum for any path starting at root i is simply the price of the node i itself, price[i], as this corresponds to the path containing only the root. To find the maximum price sum, we need to find the path starting at i that yields the highest sum of prices. This can be achieved by performing a graph traversal, like Breadth-First Search (BFS) or Depth-First Search (DFS), starting from node i. During the traversal, we keep track of the cumulative price sum for each path from i. After the traversal completes, we will have found the maximum path sum starting from i. The cost for root i is then max_path_sum - price[i]. We repeat this process for all n nodes and return the maximum cost found. Here is a Java implementation using this approach:\n

1java\nclass Solution {\n    public long maxOutput(int n, int[][] edges, int[] price) {\n        List<List<Integer>> adj = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            adj.add(new ArrayList<>());\n        }\n        for (int[] edge : edges) {\n            adj.get(edge[0]).add(edge[1]);\n            adj.get(edge[1]).add(edge[0]);\n        }\n\n        long maxOverallCost = 0;\n\n        for (int i = 0; i < n; i++) {\n            long maxPathSumFromI = 0;\n            Queue<long[]> queue = new LinkedList<>();\n            queue.offer(new long[]{i, price[i]}); // {node, current_path_sum}\n            boolean[] visited = new boolean[n];\n            visited[i] = true;\n\n            while (!queue.isEmpty()) {\n                long[] current = queue.poll();\n                int u = (int) current[0];\n                long currentSum = current[1];\n                maxPathSumFromI = Math.max(maxPathSumFromI, currentSum);\n\n                for (int v : adj.get(u)) {\n                    if (!visited[v]) {\n                        visited[v] = true;\n                        queue.offer(new long[]{v, currentSum + price[v]});\n                    }\n                }\n            }\n            \n            long costI = maxPathSumFromI - price[i];\n            maxOverallCost = Math.max(maxOverallCost, costI);\n        }\n\n        return maxOverallCost;\n    }\n}\n

Complexity

Time

O(N^2), where N is the number of nodes. For each of the N possible roots, we perform a graph traversal (BFS/DFS) which takes O(N + E) time. Since it's a tree, E = N-1, so each traversal is O(N). The total time complexity is N * O(N) = O(N^2).

Space

O(N), where N is the number of nodes. We need O(N) space for the adjacency list. Additionally, during each traversal, we use a queue or recursion stack and a visited array, which take O(N) space.

Trade-offs

Pros

Simple to understand and implement directly from the problem definition.

Cons

Inefficient for large inputs. An O(N^2) solution will likely result in a 'Time Limit Exceeded' error for constraints where N is up to 10^5.

A much more efficient approach relies on a key insight about tree paths. The cost for any root i depends on the maximum price sum path starting from i. It turns out this path always ends at one of the two endpoints of a 'price diameter' of the tree. A 'price diameter' is a path between two nodes with the maximum possible sum of prices. By pre-calculating information related to the diameter, we can find the answer in linear time.

Algorithm

Step 1: Find endpoints of a price diameter (x, y). This is a standard two-pass traversal algorithm.\n - a. Pick an arbitrary node (e.g., 0). Run a BFS/DFS to find the node x farthest from it in terms of price sum.\n - b. Run a BFS/DFS from x to find the node y farthest from x. The path between x and y is a price diameter.\n- Step 2: Calculate path sums from x and y to all other nodes.\n - The traversal from x in Step 1b already gives us the path sums from x to all other nodes (S(x, i)). Store these in an array dist_x.\n - Run one more BFS/DFS, this time starting from y, to compute S(y, i) for all i. Store these in an array dist_y.\n- Step 3: Calculate the maximum cost.\n - Initialize max_cost = 0.\n - Iterate i from 0 to n-1:\n - cost_i = max(dist_x[i], dist_y[i]) - price[i].\n - max_cost = max(max_cost, cost_i).\n - Return max_cost.

Walkthrough

The core idea is to transform the problem from re-calculating path sums for each root to a problem that can be solved with a few global traversals.\n1. Price Diameter: First, we define a 'price diameter' as a path between two nodes u and v such that the sum of prices of all nodes on the path is maximized over the entire tree.\n2. Key Insight: For any node i in the tree, the path starting at i with the maximum price sum will always end at one of the endpoints of any price diameter. Let's say the endpoints of a price diameter are x and y. Then, for any i, the maximum price sum path starting from i is max(S(i, x), S(i, y)), where S(u, v) is the price sum of the path between u and v. The minimum price sum path is always price[i]. Therefore, the cost for root i is cost(i) = max(S(i, x), S(i, y)) - price[i].\n3. Algorithm: The problem is now reduced to: find diameter endpoints x and y, then for every node i, find its path sum to x and y, and compute the maximum cost. This can be done efficiently.\nHere is the Java implementation:\n

1java\nimport java.util.*;\n\nclass Solution {\n    private List<List<Integer>> adj;\n    private int[] price;\n    private int n;\n\n    public long maxOutput(int n, int[][] edges, int[] price) {\n        this.n = n;\n        this.price = price;\n        this.adj = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            adj.add(new ArrayList<>());\n        }\n        for (int[] edge : edges) {\n            adj.get(edge[0]).add(edge[1]);\n            adj.get(edge[1]).add(edge[0]);\n        }\n\n        // Step 1: Find endpoints of a price diameter (x, y)\n        Object[] res1 = bfs(0);\n        int x = (int) res1[0];\n\n        Object[] res2 = bfs(x);\n        int y = (int) res2[0];\n        long[] distFromX = (long[]) res2[2];\n\n        // Step 2: Get distances from y\n        Object[] res3 = bfs(y);\n        long[] distFromY = (long[]) res3[2];\n\n        // Step 3: Calculate max cost\n        long maxCost = 0;\n        for (int i = 0; i < n; i++) {\n            long cost = Math.max(distFromX[i], distFromY[i]) - price[i];\n            maxCost = Math.max(maxCost, cost);\n        }\n\n        return maxCost;\n    }\n\n    private Object[] bfs(int startNode) {\n        long[] dist = new long[n];\n        Arrays.fill(dist, -1);\n        Queue<Integer> queue = new LinkedList<>();\n\n        queue.offer(startNode);\n        dist[startNode] = price[startNode];\n\n        int farthestNode = startNode;\n        long maxDist = price[startNode];\n\n        while (!queue.isEmpty()) {\n            int u = queue.poll();\n            for (int v : adj.get(u)) {\n                if (dist[v] == -1) { // Not visited\n                    dist[v] = dist[u] + price[v];\n                    if (dist[v] > maxDist) {\n                        maxDist = dist[v];\n                        farthestNode = v;\n                    }\n                    queue.offer(v);\n                }\n            }\n        }\n        return new Object[]{farthestNode, maxDist, dist};\n    }\n}\n

Complexity

Time

O(N), where N is the number of nodes. The algorithm consists of three separate graph traversals (BFS/DFS), each taking O(N) time. The final loop to calculate the maximum cost also takes O(N). Thus, the total time complexity is linear.

Space

O(N), where N is the number of nodes. This space is used for the adjacency list, the distance arrays (`dist_x`, `dist_y`), and the data structures required for traversal (queue for BFS or recursion stack for DFS).

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
It's an optimal solution for this problem.

Cons

The solution is not immediately obvious and relies on understanding a specific property of trees (the diameter concept), making it more complex to derive than the brute-force approach.

Solutions

Solution

1class Solution {2private3  List<Integer>[] g;4private5  long ans;6private7  int[] price;8public9  long maxOutput(int n, int[][] edges, int[] price) {10    g = new List[n];11    Arrays.setAll(g, k->new ArrayList<>());12    for (var e : edges) {13      int a = e[0], b = e[1];14      g[a].add(b);15      g[b].add(a);16    }17    this.price = price;18    dfs(0, -1);19    return ans;20  }21private22  long[] dfs(int i, int fa) {23    long a = price[i], b = 0;24    for (int j : g[i]) {25      if (j != fa) {26        var e = dfs(j, i);27        long c = e[0], d = e[1];28        ans = Math.max(ans, Math.max(a + d, b + c));29        a = Math.max(a, price[i] + c);30        b = Math.max(b, price[i] + d);31      }32    }33    return new long[]{a, b};34  }35}

1class Solution {2public:3  long long maxOutput(int n, vector<vector<int>> &edges, vector<int> &price) {4    vector<vector<int>> g(n);5    for (auto &e : edges) {6      int a = e[0], b = e[1];7      g[a].push_back(b);8      g[b].push_back(a);9    }10    using ll = long long;11    using pll = pair<ll, ll>;12    ll ans = 0;13    function<pll(int, int)> dfs = [&](int i, int fa) {14      ll a = price[i], b = 0;15      for (int j : g[i]) {16        if (j != fa) {17          auto [c, d] = dfs(j, i);18          ans = max({ans, a + d, b + c});19          a = max(a, price[i] + c);20          b = max(b, price[i] + d);21        }22      }23      return pll{a, b};24    };25    dfs(0, -1);26    return ans;27  }28};

1class Solution:2    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int: def dfs(i, fa): a, b = price[i], 0 for j in g[i]: if j != fa: c, d = dfs(j, i) nonlocal ans ans = max(ans, a + d, b + c) a = max(a, price[i] + c) b = max(b, price[i] + d) return a, b g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) ans = 0 dfs(0, - 1) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem