FastPrep
Problem · Tree

Find Minimum Possible Diameter

Learn this problem
● HardGoogleOA
See Google hiring insights

Problem statement

You are given a tree consisting of n vertices.

You can perform the following operation at most k times: delete a single leaf of the tree (the operation can produce new leaves, that can be deleted later). The resulting tree must have as small diameter as possible. Find the minimum possible diameter.

Input Format

The first line contains two space separated integers n and k. Each of the next n-1 lines contains two space separated integers, describing the current tree edge. It's guaranteed that the given graph is a tree.

Constraints

0 < n <= 1e5
0 < k < n

Function

findMinimumDiameter(n: int, k: int, edges: int[][]) → int

Examples

Example 1

n = 4k = 0edges = [[1, 2], [2, 3], [4, 3]]return = 3
:3

Example 2

n = 4k = 1edges = [[2, 3], [4, 3], [1, 4]]return = 2
:o

Constraints

  • 1 <= n <= 10^5
  • 0 <= k < n
  • edges.length == n - 1
  • Vertices are numbered from 1 to n, and edges forms a tree.

More Google problems

drafts saved locally
public int findMinimumDiameter(int n, int k, int[][] edges) {
  // write your code here
}
n4
k0
edges[[1, 2], [2, 3], [4, 3]]
expected3
checking account