Count Subtrees With Max Distance Between Cities solution and explanation
7 more videos on this problem
花花酱 LeetCode 1617. Count Subtrees With Max Distance Between Cities - 刷题找工作 EP362Hua Hua · 25:11 · 2K views
LeetCode 1617. Count Subtrees With Max Distance Between CitiesHappy Coding · 33:03 · 1K views
Count Subtrees With Max Distance Between Cities | Explaination | trees | bit maskingAthar Mohd · 23:51 · 1K views
Leetcode Solutions 1617 Count Subtrees With Max Distance Between CitiesAbrar & Software Engineering · 19:49 · 925 views
【每日一题】1617. Count Subtrees With Max Distance Between Cities, 10/12/2020Huifeng Guan · 39:46 · 636 views
1617. Count Subtrees With Max Distance Between Cities (Leetcode Hard)Programming Live with Larry · 23:45 · 595 views
Daily Code Challenge 6 - Count Subtrees With Max Distance Between CitiesSoftware the Hard Way · 1:42:00 · 92 views
LeetCode 1617: Count Subtrees With Max Distance Between CitiesAlitaCode · 32:06 · 10 views
The problem
There are n cities numbered from 1 to n. You are given an array edges of size n-1, where edges[i] = [ui, vi] represents a bidirectional edge between cities ui and vi. There exists a unique path between each pair of cities. In other words, the cities form a tree.
A subtree is a subset of cities where every city is reachable from every other city in the subset, where the path between each pair passes through only the cities from the subset. Two subtrees are different if there is a city in one subtree that is not present in the other.
For each d from 1 to n-1, find the number of subtrees in which the maximum distance between any two cities in the subtree is equal to d.
Return an array of size n-1 where the dth element (1-indexed) is the number of subtrees in which the maximum distance between any two cities is equal to d.
Notice that the distance between the two cities is the number of edges in the path between them.
Example 1:
Input: n = 4, edges = [[1,2],[2,3],[2,4]]
Output: [3,4,0]
Explanation:
The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.
The subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.
No subtree has two nodes where the max distance between them is 3.
Example 2:
Input: n = 2, edges = [[1,2]] Output: [1]
Example 3:
Input: n = 3, edges = [[1,2],[2,3]] Output: [2,1]
Constraints:
2 <= n <= 15edges.length == n-1edges[i].length == 21 <= ui, vi <= n- All pairs
(ui, vi)are distinct.
Approach overview
Problem Overview: You are given n cities connected as a tree. For every possible connected subset of cities (a subtree), compute its diameter—the maximum distance between any two cities inside that subset. The task is to count how many subtrees have diameter d for each 1 ≤ d < n.
Approach 1: Bitmask Enumeration + Floyd-Warshall (O(n^3 * 2^n) time, O(n^2) space)
Enumerate every subset of cities using a bitmask. For each subset, verify that it forms a connected subtree by counting edges or running a DFS. Precompute all-pairs shortest paths with the Floyd-Warshall algorithm so distance queries are constant time. Once the subset is validated, iterate over every pair of nodes inside the mask and compute the maximum pairwise distance to get the diameter. This method is straightforward and works because n ≤ 15, making 2^n manageable.
Approach 2: Dynamic Programming with DFS (O(n * 2^n) time, O(n * 2^n) space)
This approach still enumerates subsets but avoids repeated distance calculations. For each subset, run a DFS restricted to nodes inside the mask. Track the farthest node to compute the diameter using the classic two-DFS tree diameter trick. The DP component caches valid subtree states so connectivity checks are efficient. Since each subset processes only its internal edges, the complexity improves significantly compared to recomputing all-pairs distances.
Approach 3: Dynamic Programming on Subsets (O(n * 2^n) time, O(2^n) space)
Instead of recomputing properties from scratch, build results incrementally. Maintain DP information about the farthest node distances for subsets while expanding masks. If adding a node preserves connectivity, update the maximum path length using distances to existing nodes. This avoids repeated DFS traversals and keeps computations localized to the subset transition. This version is common in optimized competitive programming solutions involving bitmask subset DP.
Approach 4: Iterative Enumeration with Tree Properties (O(n * 2^n) time, O(n) space)
Because the original graph is a tree, any valid subtree with k nodes must contain exactly k-1 edges. Iterate through subsets, count included edges, and reject masks that violate this property. Once a mask represents a tree, compute its diameter using two DFS passes restricted to the nodes in the mask. This approach is simple and avoids heavy preprocessing while still leveraging tree structure.
Recommended for interviews: The subset enumeration combined with DFS diameter computation is the expected solution. It demonstrates understanding of tree diameter algorithms plus subset generation using bit manipulation. Starting with brute-force subset enumeration shows reasoning about constraints, while optimizing with DP or efficient DFS demonstrates strong algorithmic thinking.
Approach 1: Using Bitmask and Floyd-Warshall Algorithm
This approach uses a combination of bit masking to enumerate all possible subtrees and Floyd-Warshall to compute all-pairs shortest paths for each subset.
def count_subtrees_with_max_distance(n, edges):
from itertools import combinations
from math import inf
graph = [[inf] * n for _ in range(n)]
for i in range(n):
graph[i][i] = 0
for u, v in edges:
graph[u - 1][v - 1] = 1
graph[v - 1][u - 1] = 1
for k in range(n):
for i in range(n):
for j in range(n):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
answer = [0] * (n - 1)
for mask in range(1, 1 << n):
nodes = [i for i in range(n) if (mask & (1 << i))]
if len(nodes) < 2:
continue
max_dist = 0
for i, j in combinations(nodes, 2):
max_dist = max(max_dist, graph[i][j])
if max_dist <= n - 1:
answer[max_dist - 1] += 1
return answerThe code iterates over all subsets of nodes using a bitmask approach for subsets, and then leverages the Floyd-Warshall algorithm to find the shortest paths between all node pairs. It finds the maximum distance between any pair of nodes in each subset and updates the answer array accordingly.
The time complexity is O(2^n * n^3) due to iterating over all subsets and using the Floyd-Warshall for each pair. The space complexity is O(n^2) due to the adjacency matrix used in Floyd-Warshall.
Approach 2: Dynamic Programming with Depth First Search (DFS)
This approach uses dynamic programming techniques paired with DFS to calculate the maximum distances within each subtree.
import java.util.*;
public class CountSubtrees {
public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] edge : edges) {
graph[edge[0] - 1].add(edge[1] - 1);
graph[edge[1] - 1].add(edge[0] - 1);
}
int[] res = new int[n - 1];
for (int mask = 3; mask < (1 << n); mask++) {
List<Integer> nodes = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) nodes.add(i);
}
int[] dp = new int[nodes.size()];
boolean[] visited = new boolean[n];
boolean connected = dfs(nodes.get(0), -1, mask, visited, dp, graph);
if (connected) {
Arrays.fill(dp, 0);
int d = maxDistance(nodes.get(0), -1, mask, dp, graph);
if (d > 0) res[d - 1]++;
}
}
return res;
}
private boolean dfs(int node, int parent, int mask, boolean[] visited, int[] dp, List<Integer>[] graph) {
int nodeIndex = Integer.numberOfTrailingZeros(mask & (1 << node));
visited[node] = true;
for (int next : graph[node]) {
if (next == parent || (mask & (1 << next)) == 0) continue;
if (!dfs(next, node, mask, visited, dp, graph)) return false;
}
return true;
}
private int maxDistance(int node, int parent, int mask, int[] dp, List<Integer>[] graph) {
int nodeIndex = Integer.numberOfTrailingZeros(mask & (1 << node));
for (int next : graph[node]) {
if (next != parent && (mask & (1 << next)) != 0) {
dp[nodeIndex] = Math.max(dp[nodeIndex], maxDistance(next, node, mask, dp, graph) + 1);
}
}
return dp[nodeIndex];
}
}In this solution, we use DFS to ensure that each subset of nodes forms a connected subtree. Then, through dynamic programming, we calculate and track the maximum distance within the subtree by iterating over possible node pairs.
The time complexity is O(2^n * n^2) due to working with dfs and bitmasking over subsets. The space complexity is O(n), primarily due to the storage required for visited states and the dynamic programming table.
Approach 3: Dynamic Programming Approach
The dynamic programming approach is ideal for problems that can be broken down into overlapping sub-problems and that exhibit optimal substructure. By saving solutions to these sub-problems, the algorithm avoids redundant work, significantly cutting down on computation time.
def solveDP(n, dp):
if n <= 1:
return n
if dp[n] != -1:
return dp[n]
dp[n] = solveDP(n-1, dp) + solveDP(n-2, dp)
return dp[n]
n = 10
dp = [-1]*1000
print(solveDP(n, dp))import java.util.Arrays;
public class Fibonacci {
static int MAX = 1000;
static int[] dp = new int[MAX];
public static int solveDP(int n) {
if (n <= 1)
return n;
if (dp[n] != -1)
return dp[n];
dp[n] = solveDP(n - 1) + solveDP(n - 2);
return dp[n];
}
public static void main(String[] args) {
Arrays.fill(dp, -1);
int n = 10;
System.out.println(solveDP(n));
}
}#include <iostream>
#include <vector>
#define MAX 1000
using namespace std;
vector<int> dp(MAX, -1);
int solveDP(int n) {
if(n <= 1)
return n;
if(dp[n] != -1)
return dp[n];
dp[n] = solveDP(n-1) + solveDP(n-2);
return dp[n];
}
int main() {
int n = 10;
cout << solveDP(n) << endl;
return 0;
}function solveDP(n, dp) {
if (n <= 1)
return n;
if (dp[n] !== -1)
return dp[n];
dp[n] = solveDP(n - 1, dp) + solveDP(n - 2, dp);
return dp[n];
}
let dp = Array(1000).fill(-1);
let n = 10;
console.log(solveDP(n, dp));#include <stdio.h>
#define MAX 1000
int dp[MAX];
int solveDP(int n) {
if(n <= 1)
return n;
if(dp[n] != -1)
return dp[n];
dp[n] = solveDP(n-1) + solveDP(n-2);
return dp[n];
}
int main() {
for(int i = 0; i < MAX; i++) dp[i] = -1;
int n = 10;
printf("%d\n", solveDP(n));
return 0;
}using System;
class Program {
static int MAX = 1000;
static int[] dp = new int[MAX];
static int solveDP(int n) {
if (n <= 1)
return n;
if (dp[n] != -1)
return dp[n];
dp[n] = solveDP(n - 1) + solveDP(n - 2);
return dp[n];
}
static void Main() {
Array.Fill(dp, -1);
int n = 10;
Console.WriteLine(solveDP(n));
}
}This Python implementation leverages memoization through a list, capturing intermediate Fibonacci numbers to ensure each is computed only once.
Time Complexity: O(n)
Space Complexity: O(n) due to the dp list.
Approach 4: Iterative Approach
An iterative approach to problems like Fibonacci is often more space-efficient than recursive approaches because it doesn’t require additional space for recursion stack. This method typically uses a simple loop to compute results.
def solveIterative(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
n = 10
print(solveIterative(n))public class Fibonacci {
public static int solveIterative(int n) {
if (n <= 1)
return n;
int prev2 = 0, prev1 = 1, cur = 0;
for (int i = 2; i <= n; ++i) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur;
}
public static void main(String[] args) {
int n = 10;
System.out.println(solveIterative(n));
}
}#include <iostream>
using namespace std;
int solveIterative(int n) {
if (n <= 1)
return n;
int prev2 = 0, prev1 = 1, cur;
for (int i = 2; i <= n; ++i) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur;
}
int main() {
int n = 10;
cout << solveIterative(n) << endl;
return 0;
}function solveIterative(n) {
if (n <= 1)
return n;
let prev2 = 0, prev1 = 1, cur;
for (let i = 2; i <= n; ++i) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur;
}
let n = 10;
console.log(solveIterative(n));#include <stdio.h>
int solveIterative(int n) {
if (n <= 1)
return n;
int prev2 = 0, prev1 = 1, cur;
for (int i = 2; i <= n; ++i) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur;
}
int main() {
int n = 10;
printf("%d\n", solveIterative(n));
return 0;
}using System;
class Program {
public static int solveIterative(int n) {
if (n <= 1)
return n;
int prev2 = 0, prev1 = 1, cur = 0;
for (int i = 2; i <= n; ++i) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur;
}
static void Main() {
int n = 10;
Console.WriteLine(solveIterative(n));
}
}This Python solution iteratively computes Fibonacci numbers with just two variables to store preceding values, achieving optimal space efficiency.
Time Complexity: O(n)
Space Complexity: O(1) due to constant additional storage.
Approach 5: Default Approach
function countSubgraphsForEachDiameter(n: number, edges: number[][]): number[] {
const g = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u - 1].push(v - 1);
g[v - 1].push(u - 1);
}
const ans: number[] = new Array(n - 1).fill(0);
let [mx, msk, nxt] = [0, 0, 0];
const dfs = (u: number, d: number) => {
if (mx < d) {
mx = d;
nxt = u;
}
msk ^= 1 << u;
for (const v of g[u]) {
if ((msk >> v) & 1) {
dfs(v, d + 1);
}
}
};
for (let mask = 1; mask < 1 << n; ++mask) {
if ((mask & (mask - 1)) === 0) {
continue;
}
msk = mask;
mx = 0;
const cur = 31 - numberOfLeadingZeros(msk);
dfs(cur, 0);
if (msk === 0) {
msk = mask;
mx = 0;
dfs(nxt, 0);
++ans[mx - 1];
}
}
return ans;
}
function numberOfLeadingZeros(i: number): number {
if (i == 0) return 32;
let n = 1;
if (i >>> 16 == 0) {
n += 16;
i <<= 16;
}
if (i >>> 24 == 0) {
n += 8;
i <<= 8;
}
if (i >>> 28 == 0) {
n += 4;
i <<= 4;
}
if (i >>> 30 == 0) {
n += 2;
i <<= 2;
}
n -= i >>> 31;
return n;
}func countSubgraphsForEachDiameter(n int, edges [][]int) []int {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0]-1, e[1]-1
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
ans := make([]int, n-1)
var msk, nxt, mx int
var dfs func(int, int)
dfs = func(u, d int) {
msk ^= 1 << u
if mx < d {
mx, nxt = d, u
}
for _, v := range g[u] {
if msk>>v&1 == 1 {
dfs(v, d+1)
}
}
}
for mask := 1; mask < 1<<n; mask++ {
if mask&(mask-1) == 0 {
continue
}
msk, mx = mask, 0
cur := bits.Len(uint(msk)) - 1
dfs(cur, 0)
if msk == 0 {
msk, mx = mask, 0
dfs(nxt, 0)
ans[mx-1]++
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Bitmask and Floyd-Warshall Algorithm | The time complexity is O(2^n * n^3) due to iterating over all subsets and using the Floyd-Warshall for each pair. The space complexity is O(n^2) due to the adjacency matrix used in Floyd-Warshall. |
| Dynamic Programming with Depth First Search (DFS) | The time complexity is O(2^n * n^2) due to working with dfs and bitmasking over subsets. The space complexity is O(n), primarily due to the storage required for visited states and the dynamic programming table. |
| Dynamic Programming Approach | Time Complexity: O(n) |
| Iterative Approach | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask + Floyd-Warshall | O(n^3 * 2^n) | O(n^2) | Simplest implementation when precomputing all pair distances is acceptable |
| DP with DFS Diameter | O(n * 2^n) | O(n * 2^n) | Efficient enumeration with cached connectivity checks |
| Subset Dynamic Programming | O(n * 2^n) | O(2^n) | Best for optimized competitive programming solutions using bitmask transitions |
| Iterative Subset + DFS | O(n * 2^n) | O(n) | Interview-friendly approach leveraging tree diameter via two DFS passes |
Frequently asked questions
Is Count Subtrees With Max Distance Between Cities easy or hard?
LeetCode classifies this problem as Hard because it combines multiple concepts: tree diameter, subset enumeration, and bitmask dynamic programming. Handling connectivity checks and efficiently computing diameters for many subsets makes the implementation non-trivial.
Count Subtrees With Max Distance Between Cities Python/Java solution
Python and Java implementations typically enumerate subsets using integer bitmasks and maintain adjacency lists for the tree. Each subset is validated and processed with DFS to compute the diameter. The overall approach remains O(n * 2^n) and works well within the constraint n ≤ 15.
How to solve Count Subtrees With Max Distance Between Cities in O(n * 2^n)?
Enumerate all subsets using a bitmask and filter subsets that form valid trees by verifying they contain exactly k−1 edges for k nodes. For each valid subset, run a DFS to find the farthest node, then run another DFS from that node to compute the subtree diameter. Increment the answer bucket for that diameter value.
What is the best approach for Count Subtrees With Max Distance Between Cities?
The most practical approach enumerates all subsets of cities using a bitmask and checks whether the subset forms a connected subtree. For each valid subset, compute the diameter using two DFS traversals restricted to the subset nodes. This solution runs in about O(n * 2^n) time because each subset processes only its internal nodes and edges.
Is Count Subtrees With Max Distance Between Cities asked at Google/Amazon/Meta?
Tree diameter and subset enumeration problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants combining tree traversal with bitmask DP are common in advanced algorithm rounds, especially for roles focused on graph algorithms or competitive programming skills.
What data structure is used in Count Subtrees With Max Distance Between Cities?
The solution relies on adjacency lists to represent the tree and bitmasks to represent subsets of nodes. DFS or BFS is used to traverse nodes within a subset, while dynamic programming or subset enumeration helps track valid subtree states efficiently.
What is the time complexity of Count Subtrees With Max Distance Between Cities?
The optimal solutions run in O(n * 2^n) time with O(n) to O(2^n) space. Every subset of nodes is enumerated using a bitmask, and for each valid subtree a DFS-based diameter calculation is performed. Simpler implementations using Floyd-Warshall preprocessing may reach O(n^3 * 2^n).