Skip to main content
Talentd

Total Sum of Interaction Cost in Tree Groups - Solution & Explanation

HardArrayTreeDepth-First Search4 min readAsked at: Amazon
Practice this problem

Problem Statement

You are given an integer n and an undirected tree with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between nodes ui and vi.

You are also given an integer array group of length n, where group[i] denotes the group label assigned to node i.

  • Two nodes u and v are considered part of the same group if group[u] == group[v].
  • The interaction cost between u and v is defined as the number of edges on the unique path connecting them in the tree.

Return an integer denoting the sum of interaction costs over all unordered pairs (u, v) with u != v such that group[u] == group[v].

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], group = [1,1,1]

Output: 4

Explanation:

All nodes belong to group 1. The interaction costs between the pairs of nodes are:

  • Nodes (0, 1): 1
  • Nodes (1, 2): 1
  • Nodes (0, 2): 2

Thus, the total interaction cost is 1 + 1 + 2 = 4.

Example 2:

Input: n = 3, edges = [[0,1],[1,2]], group = [3,2,3]

Output: 2

Explanation:

  • Nodes 0 and 2 belong to group 3. The interaction cost between this pair is 2.
  • Node 1 belongs to a different group and forms no valid pair. Therefore, the total interaction cost is 2.

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[0,3]], group = [1,1,4,4]

Output: 3

Explanation:

Nodes belonging to the same groups and their interaction costs are:

  • Group 1: Nodes (0, 1): 1
  • Group 4: Nodes (2, 3): 2

Thus, the total interaction cost is 1 + 2 = 3.

Example 4:

Input: n = 2, edges = [[0,1]], group = [9,8]

Output: 0

Explanation:

All nodes belong to different groups and there are no valid pairs. Therefore, the total interaction cost is 0.

 

Constraints:

  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ui, vi]
  • 0 <= ui, vi <= n - 1
  • group.length == n
  • 1 <= group[i] <= 20
  • The input is generated such that edges represents a valid tree.

Approach Overview

Problem Overview: You are given nodes organized as a tree and an array describing which group each node belongs to. The interaction cost between two nodes is the distance along the tree. The goal is to compute the total cost across all pairs of nodes that belong to the same group.

Approach 1: Pairwise Distance with LCA (Brute Force) (Time: O(k^2 log n), Space: O(n))

Group nodes by their group id using a hash map. For each group, iterate over every pair of nodes and compute their tree distance using a Lowest Common Ancestor structure such as binary lifting. The distance formula is dist(u,v) = depth[u] + depth[v] - 2 * depth[lca(u,v)]. This approach is easy to implement after building the LCA preprocessing in O(n log n). The downside is the quadratic pair iteration inside each group, which becomes too slow when a group contains many nodes.

Approach 2: DFS Subtree Aggregation (Optimal) (Time: O(n log n), Space: O(n))

Use a depth-first traversal of the tree and maintain frequency maps that track how many nodes of each group appear inside the current subtree. When processing an edge between a node and its child, the edge contributes to the distance between any pair of nodes whose path crosses that edge. If a group has a nodes in the child subtree and b nodes outside it, that edge contributes a * b to the total distance for that group.

During DFS, each node returns a map {group -> count} representing how many nodes of each group exist in its subtree. Merge child maps into the parent map using the small-to-large merging technique to keep the complexity under control. While merging, update the global interaction cost using the edge contribution formula. Small-to-large ensures each element moves only O(log n) times, giving overall O(n log n) time.

This method leverages the structure of a tree and processes every edge exactly once while maintaining group counts discovered via depth-first search. The grouping information originates from the input array, but the heavy work happens during the DFS aggregation.

Recommended for interviews: The DFS subtree aggregation approach is the expected solution. Interviewers want to see whether you can translate pairwise distance calculations into edge contributions on a tree. Starting with the brute-force pair approach shows understanding of the distance formula, but optimizing with DFS aggregation demonstrates strong tree and counting techniques.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise Distance with LCAO(k^2 log n)O(n)Small groups or quick prototype solution
DFS Subtree Aggregation with Map MergingO(n log n)O(n)General optimal solution for large trees and many groups
Small-to-Large Map Merging OptimizationO(n log n)O(n)Efficient when many group ids appear across subtrees

Video Solution

Leetcode 3786 | Total Sum of Interaction Cost in Tree Groups • CodeWithMeGuys • 728 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Total Sum of Interaction Cost in Tree Groups easy or hard?
Total Sum of Interaction Cost in Tree Groups is categorized as Hard because it requires transforming pairwise distance calculations into edge contributions on a tree. Efficient solutions combine DFS traversal, subtree counting, and optimized map merging techniques.
Total Sum of Interaction Cost in Tree Groups Python/Java solution
In Python or Java, build the tree using adjacency lists and run a DFS from the root. Each recursive call returns a map of group counts for its subtree. While merging child maps, update the total interaction cost using the edge contribution formula and combine the maps using a small-to-large optimization.
How to solve Total Sum of Interaction Cost in Tree Groups in O(n log n)?
Run a depth-first search and maintain a map of group counts for every subtree. When processing an edge, compute contributions for each group based on how many nodes lie inside the subtree versus outside it. Merge child maps into the parent using a small-to-large strategy so each entry moves only logarithmically many times.
What is the best approach for Total Sum of Interaction Cost in Tree Groups?
The most efficient solution uses DFS with subtree aggregation. Each subtree tracks how many nodes belong to each group, and every tree edge contributes a * b to the total cost where a is the count of a group in the child subtree and b is the remaining count outside. Using small-to-large map merging keeps the complexity around O(n log n) with O(n) space.
Is Total Sum of Interaction Cost in Tree Groups asked at Google/Amazon/Meta?
Tree aggregation and pair-distance problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem title may vary, the underlying pattern of computing pair contributions on a tree using DFS is a common advanced interview topic.
What data structure is used in Total Sum of Interaction Cost in Tree Groups?
The solution relies on adjacency lists to represent the tree, hash maps (or dictionaries) to track group frequencies inside subtrees, and recursion or an explicit stack for depth-first search. Some implementations also use small-to-large merging to optimize map operations.
What is the time complexity of Total Sum of Interaction Cost in Tree Groups?
The optimal DFS aggregation solution runs in O(n log n) time and O(n) space due to map merging during traversal. A naive pairwise approach that computes distances using LCA can take O(k^2 log n) per group, which becomes inefficient when groups contain many nodes.

Ready to solve this problem?

Practice Total Sum of Interaction Cost in Tree Groups with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays