Erect the Fence II - Practice Coding Problems

Erect the Fence II - Problem

You are given a 2D integer array trees where trees[i] = [xi, yi] represents the location of the ith 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⁻⁵ of the actual answer will be accepted.

Input & Output

Example 1 — Square Formation

$ Input: trees = [[1,1],[2,2],[2,0],[0,2]]

› Output: [1.0,1.0,1.414213]

💡 Note: The smallest circle that encloses all four trees has center at (1,1) with radius approximately √2 ≈ 1.414213. This circle passes through points (2,2), (2,0), and (0,2).

Example 2 — Single Point

$ Input: trees = [[1,2]]

› Output: [1.0,2.0,0.0]

💡 Note: With only one tree, the smallest circle is centered at that tree's location with radius 0.

Example 3 — Two Points

$ Input: trees = [[0,0],[3,4]]

› Output: [1.5,2.0,2.5]

💡 Note: For two points, the smallest circle has them as diameter endpoints. Center is midpoint (1.5,2.0) and radius is half the distance: √(9+16)/2 = 2.5.

Constraints

1 ≤ trees.length ≤ 3000
trees[i].length == 2
-1000 ≤ xi, yi ≤ 1000
All the given positions are unique

Visualization

Tap to expand

Understanding the Visualization

Input Trees

Given 2D coordinates of trees in the garden

Find Circle

Calculate center and radius of smallest enclosing circle

Output Result

Return [center_x, center_y, radius] as array

Key Takeaway

🎯 Key Insight: The smallest enclosing circle is uniquely determined by at most 3 points on its boundary

Asked in

G Google 15 f Facebook 8

The key insight is that the smallest enclosing circle is determined by at most 3 boundary points. The optimal approach is Welzl's algorithm which uses recursion with randomization to achieve expected linear time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Centers	O(n³)	O(1)	Try every possible circle center and find minimum radius
Welzl's Algorithm	O(n)	O(n)	Recursive algorithm with expected linear time complexity

Brute Force - Try All Centers — Algorithm Steps

Step 1: Generate candidate center points
Step 2: For each center, find minimum radius to cover all trees
Step 3: Return center with smallest radius

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Points

Given tree locations as 2D points

Try Centers

For each pair, try midpoint as circle center

Find Radius

Calculate minimum radius to enclose all points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

double* solution(int** trees, int treesSize, int* returnSize) {
    *returnSize = 3;
    double* result = (double*)malloc(3 * sizeof(double));
    
    if (treesSize == 1) {
        result[0] = (double)trees[0][0];
        result[1] = (double)trees[0][1];
        result[2] = 0.0;
        return result;
    }
    
    double minRadius = 1e9;
    double bestCenterX = 0.0, bestCenterY = 0.0;
    
    // Try circle through each pair of points
    for (int i = 0; i < treesSize; i++) {
        for (int j = i + 1; j < treesSize; j++) {
            // Circle with diameter as line segment between trees[i] and trees[j]
            double cx = (trees[i][0] + trees[j][0]) / 2.0;
            double cy = (trees[i][1] + trees[j][1]) / 2.0;
            
            // Find max distance from this center to any tree
            double maxDist = 0.0;
            for (int k = 0; k < treesSize; k++) {
                double dx = trees[k][0] - cx;
                double dy = trees[k][1] - cy;
                double dist = sqrt(dx*dx + dy*dy);
                if (dist > maxDist) {
                    maxDist = dist;
                }
            }
            
            if (maxDist < minRadius) {
                minRadius = maxDist;
                bestCenterX = cx;
                bestCenterY = cy;
            }
        }
    }
    
    result[0] = bestCenterX;
    result[1] = bestCenterY;
    result[2] = minRadius;
    return result;
}

int main() {
    // Simple parsing for demonstration
    int trees[4][2] = {{1,1}, {2,2}, {2,0}, {0,2}};
    int* treePtrs[4];
    for (int i = 0; i < 4; i++) {
        treePtrs[i] = trees[i];
    }
    
    int returnSize;
    double* result = solution(treePtrs, 4, &returnSize);
    
    printf("[%.6f,%.6f,%.6f]\n", result[0], result[1], result[2]);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops to try all possible centers and check all points

⚠ Quadratic Growth

Space Complexity

O(1)

Only storing current best circle parameters

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

324 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Centers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler