#587

Hard

LeetCode Problem Workspace

Erect the Fence

Find the perimeter fence of a garden by determining the outermost trees in a set of given tree coordinates.

Problem Statement

You are given a list of trees, where each tree is represented by its coordinates on a 2D plane. Your goal is to determine which trees are located on the perimeter of the garden and, therefore, must be part of the fence. The fence should enclose all the trees with the minimum rope length, forming a closed polygon around the outermost trees.

Return the coordinates of the trees that lie exactly on the perimeter of the fence. These trees are the critical ones for constructing the garden's fence. You may return the trees in any order, as long as they are part of the fence. This problem requires efficient algorithms for geometric processing and computational geometry to handle larger inputs.

Examples

Example 1

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]

Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]

All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

Example 2

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

Output: [[4,2],[2,2],[1,2]]

The fence forms a line that passes through all the trees.

Constraints

1 <= trees.length <= 3000
trees[i].length == 2
0 <= xi, yi <= 100
All the given positions are unique.

Solution Approach

Convex Hull Algorithm

One common approach for this problem is to use the convex hull algorithm. The convex hull is the smallest convex boundary that can enclose all the points in a 2D plane. By applying algorithms like Graham's scan or Andrew's monotone chain, we can efficiently determine which trees lie on the outer boundary.

Sorting and Geometry

The problem requires sorting the tree coordinates to process them in a geometric order. Once sorted, we can use geometric principles to identify the trees that are part of the outer boundary, ensuring we get the minimum number of trees necessary to enclose the garden.

Efficient Search and Optimization

Given the problem constraints, optimizing both the space and time complexity is crucial. By employing efficient sorting methods and reducing unnecessary calculations, we can handle the problem's upper bounds while maintaining performance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the specific convex hull algorithm used. For example, Graham's scan has a time complexity of O(n log n) due to the sorting step, while Andrew's monotone chain also operates within O(n log n). The space complexity is O(n) for storing the list of tree coordinates and the results on the convex hull.

What Interviewers Usually Probe

Is the candidate familiar with computational geometry algorithms like the convex hull?
Does the candidate understand how to optimize sorting and search operations within large data sets?
Can the candidate handle boundary cases like collinear points or large numbers of trees?

Common Pitfalls or Variants

Common pitfalls

Incorrectly identifying trees that are inside the boundary instead of on the fence perimeter.
Forgetting to handle edge cases, such as when all points are collinear.
Inefficient implementation that doesn't scale well with larger inputs.

Follow-up variants

The problem could be generalized to work with 3D coordinates, requiring a more complex geometric approach.
The problem could ask for a dynamic solution where the trees are updated over time.
Additional constraints might be introduced, such as limiting the number of trees that can be on the fence.

FAQ

What algorithm can I use to solve the Erect the Fence problem?

The convex hull algorithm is commonly used for problems like Erect the Fence. Both Graham's scan and Andrew's monotone chain are efficient methods for finding the outer boundary of a set of points.

How do I handle edge cases in the Erect the Fence problem?

Edge cases such as collinear points or trees at the same coordinates can be tricky. Make sure to handle them by applying geometric principles carefully, such as checking if points are on the boundary or inside the convex hull.

What is the time complexity of solving the Erect the Fence problem?

The time complexity of this problem is typically O(n log n), as the convex hull algorithms usually involve sorting the points before processing them.

Can this problem be solved with brute force?

While a brute force solution might involve checking all combinations of points to form the boundary, it would be inefficient and time-consuming. Using the convex hull algorithm is a much more efficient approach.

Why is the convex hull approach ideal for this problem?

The convex hull approach is ideal because it efficiently identifies the outermost points that form the minimum enclosing boundary for a set of points, which is exactly what is needed to solve the Erect the Fence problem.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(i, j, k):
            a, b, c = trees[i], trees[j], trees[k]
            return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])

        n = len(trees)
        if n < 4:
            return trees
        trees.sort()
        vis = [False] * n
        stk = [0]
        for i in range(1, n):
            while len(stk) > 1 and cross(stk[-2], stk[-1], i) < 0:
                vis[stk.pop()] = False
            vis[i] = True
            stk.append(i)
        m = len(stk)
        for i in range(n - 2, -1, -1):
            if vis[i]:
                continue
            while len(stk) > m and cross(stk[-2], stk[-1], i) < 0:
                stk.pop()
            stk.append(i)
        stk.pop()
        return [trees[i] for i in stk]

Continue Practicing

#391 perfect rectangle #812 largest triangle area #335 self crossing