LeetCode 1924 - Erect the Fence II

LeetCode Problem 1924

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry

Solution

Here is a fully detailed technical solution guide for LeetCode 1924 - Erect the Fence II, following your formatting instructions:

Problem Understanding

The problem asks us to compute the minimum enclosing circle for a set of points in 2D space, where each point represents a tree. We are given a list of trees as coordinates trees[i] = [xi, yi]. Our goal is to find a circle (defined by a center (x, y) and radius r) such that all trees lie inside or on the circle and the circle's radius is minimal. The result should be returned as [x, y, r], and answers within 1e-5 of the correct answer are acceptable.

The constraints indicate that the number of trees n can be up to 3000 and the coordinates are in the range [0, 3000]. This implies that any solution with super-quadratic time complexity (like O(n^3)) might be too slow, so we should aim for a more efficient approach.

Edge cases include:

Only one tree: the circle center is the tree itself, radius 0.
Two trees: the circle is defined by the segment connecting them, radius half the distance.
Trees in a straight line: the circle’s center is the midpoint of the segment connecting the two farthest trees.

Understanding these helps avoid naive mistakes like assuming there are always three points defining the circle.

Approaches

The brute-force approach would involve checking all possible circles defined by one, two, or three points and validating whether all other points lie inside. For each combination:

For one point, radius is zero.
For two points, the circle is the midpoint as center, half the distance as radius.
For three points, compute the circle passing through all three points.

This approach is O(n^4) in the worst case, which is too slow for n = 3000.

The optimal approach uses Welzl’s algorithm, a randomized algorithm that efficiently finds the smallest enclosing circle. It recursively picks points and maintains a set of boundary points (R) that define the circle. At most three points can define the boundary of a minimal circle. Welzl’s algorithm has expected O(n) time complexity and works well in practice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1)	Check all combinations of 1-3 points to define circle
Optimal (Welzl)	O(n) expected	O(n)	Randomized recursion to maintain boundary points, very efficient for large n

Algorithm Walkthrough

Shuffle points randomly: Randomizing order ensures expected linear time for Welzl’s algorithm.
Define recursive function minCircle(points, R):

points are the remaining points to consider.
R is the set of boundary points (at most 3).

Base cases:

If points is empty or R contains 3 points, return the minimal circle through points in R.

Pick a point p from points:

Recursively compute the minimal circle without p.
If p is inside this circle, it is already included, return the circle.
Otherwise, p must be on the boundary; add it to R and recurse.

Helper functions:

Compute circle from 1, 2, or 3 points using geometric formulas.
Check if a point lies inside a circle using the distance squared.

Return the minimal circle found.

Why it works: The algorithm ensures that every point either lies inside the circle or is on the boundary. By maintaining at most three boundary points, we guarantee minimality, as three points uniquely define a circle.

Python Solution

from typing import List
import random
import math

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[float]:
        def dist(a, b):
            return math.hypot(a[0]-b[0], a[1]-b[1])

        def is_inside(circle, p):
            c, r = circle
            return dist(c, p) <= r + 1e-10

        def circle_from(points):
            if not points:
                return ((0,0), 0)
            if len(points) == 1:
                return (points[0], 0)
            if len(points) == 2:
                a, b = points
                center = ((a[0]+b[0])/2, (a[1]+b[1])/2)
                radius = dist(a,b)/2
                return (center, radius)
            # Three points
            A, B, C = points
            # Circumcircle formula
            D = 2*(A[0]*(B[1]-C[1]) + B[0]*(C[1]-A[1]) + C[0]*(A[1]-B[1]))
            if D == 0:
                # Collinear, return max distance circle
                max_dist = 0
                center = (0,0)
                for i in range(3):
                    for j in range(i+1,3):
                        d = dist(points[i], points[j])/2
                        if d > max_dist:
                            max_dist = d
                            center = ((points[i][0]+points[j][0])/2, (points[i][1]+points[j][1])/2)
                return (center, max_dist)
            Ux = ((A[0]**2 + A[1]**2)*(B[1]-C[1]) + (B[0]**2 + B[1]**2)*(C[1]-A[1]) + (C[0]**2 + C[1]**2)*(A[1]-B[1])) / D
            Uy = ((A[0]**2 + A[1]**2)*(C[0]-B[0]) + (B[0]**2 + B[1]**2)*(A[0]-C[0]) + (C[0]**2 + C[1]**2)*(B[0]-A[0])) / D
            center = (Ux, Uy)
            radius = dist(center, A)
            return (center, radius)

        def welzl(P, R):
            if not P or len(R) == 3:
                return circle_from(R)
            p = P.pop()
            circle = welzl(P, R)
            if is_inside(circle, p):
                P.append(p)
                return circle
            R.append(p)
            c = welzl(P, R)
            R.pop()
            P.append(p)
            return c

        points = trees[:]
        random.shuffle(points)
        center, radius = welzl(points, [])
        return [center[0], center[1], radius]

Implementation Explanation:

We define helper functions to calculate distances, check containment, and compute circles from 1-3 points. The welzl function implements the randomized recursion, maintaining a boundary of points R. Shuffling ensures expected linear time. The function returns the minimal circle that encloses all points.

Go Solution

package main
import (
    "math"
    "math/rand"
)

func dist(a, b [2]float64) float64 {
    dx := a[0]-b[0]
    dy := a[1]-b[1]
    return math.Hypot(dx, dy)
}

func circleFrom(points [][2]float64) ([2]float64, float64) {
    if len(points) == 0 {
        return [2]float64{0,0}, 0
    }
    if len(points) == 1 {
        return points[0], 0
    }
    if len(points) == 2 {
        a, b := points[0], points[1]
        center := [2]float64{(a[0]+b[0])/2, (a[1]+b[1])/2}
        radius := dist(a,b)/2
        return center, radius
    }
    A, B, C := points[0], points[1], points[2]
    D := 2*(A[0]*(B[1]-C[1]) + B[0]*(C[1]-A[1]) + C[0]*(A[1]-B[1]))
    if D == 0 {
        maxDist := 0.0
        var center [2]float64
        for i:=0;i<3;i++ {
            for j:=i+1;j<3;j++ {
                d := dist(points[i], points[j])/2
                if d > maxDist {
                    maxDist = d
                    center = [2]float64{(points[i][0]+points[j][0])/2, (points[i][1]+points[j][1])/2}
                }
            }
        }
        return center, maxDist
    }
    Ux := ((A[0]*A[0]+A[1]*A[1])*(B[1]-C[1]) + (B[0]*B[0]+B[1]*B[1])*(C[1]-A[1]) + (C[0]*C[0]+C[1]*C[1])*(A[1]-