Is Erect the Fence II easy or hard?

Erect the Fence II is rated Hard because it requires knowledge of computational geometry and a randomized algorithm. Implementing the circumcircle calculations and maintaining the boundary conditions correctly makes the problem challenging.

Erect the Fence II Python/Java solution

Most implementations follow Welzl’s algorithm. The code shuffles the points, iterates through them, and recursively constructs the minimum circle when a point lies outside the current boundary. This pattern translates cleanly to Python, Java, C++, and Go.

How to solve Erect the Fence II in O(n)?

Shuffle the input points and apply Welzl’s randomized incremental algorithm. Maintain the smallest circle for processed points, and if a new point lies outside it, recompute the circle using that point and up to two boundary points. This yields expected O(n) time.

What is the best approach for Erect the Fence II?

The best approach is Randomized Welzl’s Algorithm for the minimum enclosing circle problem. It incrementally processes points and maintains a boundary set of at most three points that define the circle. The expected time complexity is O(n) with O(n) auxiliary space.

Is Erect the Fence II asked at Google/Amazon/Meta?

Minimum enclosing circle and computational geometry problems appear in interviews at companies like Google and Meta, especially for roles requiring strong algorithmic reasoning. The problem tests geometry, randomized algorithms, and numerical stability.

What data structure is used in Erect the Fence II?

The solution mainly uses arrays to store points and a small boundary set of up to three points. The core logic relies on geometric computations such as distances, midpoints, and circumcircle calculations rather than complex data structures.

What is the time complexity of Erect the Fence II?

The optimal solution using Welzl’s algorithm runs in expected O(n) time because each point is processed once after random shuffling. Brute force approaches that check circles formed by pairs and triples can take O(n^3) to O(n^4) time.

Description Hints 2 Video 28:52

1924. Erect the Fence II

Hard49.4% acceptance1 companyPremium elsewhere, free here

You are given a 2D integer array trees where trees[i] = [x_i, y_i] represents the location of the i^th tree in the garden.

You are asked to fence the entire garden using the minimum length of rope possible. The garden is well-fenced only if all the trees are enclosed and the rope used forms a perfect circle. A tree is considered enclosed if it is inside or on the border of the circle.

More formally, you must form a circle using the rope with a center (x, y) and radius r where all trees lie inside or on the circle and r is minimum.

Return the center and radius of the circle as a length 3 array [x, y, r]. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [2.00000,2.00000,2.00000]
Explanation: The fence will have center = (2, 2) and radius = 2

Example 2:

Input: trees = [[1,2],[2,2],[4,2]]
Output: [2.50000,2.00000,1.50000]
Explanation: The fence will have center = (2.5, 2) and radius = 1.5

Constraints:

1 <= trees.length <= 3000
trees[i].length == 2
0 <= x_i, y_i <= 3000

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

First, we need to note that this is a classic problem given n points you need to find the minimum enclosing circle to bind them

Hint 2

Second, we need to apply a well known algorithm called welzls algorithm to help us find the minimum enclosing circle