Watch 10 video solutions for Erect the Fence, a hard level problem involving Array, Math, Geometry. This walkthrough by codestorywithMIK has 8,400 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.
Fence the entire garden using the minimum length of rope, as it is expensive. The garden is well-fenced only if all the trees are enclosed.
Return the coordinates of trees that are exactly located on the fence perimeter. You may return the answer in any order.
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]] Explanation: 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]] Explanation: The fence forms a line that passes through all the trees.
Constraints:
1 <= trees.length <= 3000trees[i].length == 20 <= xi, yi <= 100Problem Overview: You are given coordinates of trees on a 2D plane. Build the fence that encloses all trees while including every tree that lies on the boundary. This is a classic convex hull problem from geometry, where the goal is to find the outermost points forming the smallest enclosing polygon.
Approach 1: Monotone Chain Algorithm (Convex Hull) (O(n log n) time, O(n) space)
This approach sorts the points by x coordinate (and y as a tie-breaker), then constructs the lower and upper hulls using a stack-like structure. For each new point, compute the orientation (cross product) of the last two hull points and the current point. If the turn is clockwise, remove the last point because it cannot be part of the convex boundary. Repeat until the hull remains convex. After building both halves, combine them and include collinear points on edges so every boundary tree is returned. Sorting dominates the runtime, giving O(n log n) time and O(n) space.
The key insight is the orientation test: the cross product determines whether three points make a left turn, right turn, or lie on the same line. This method works well with unordered input arrays and is one of the most practical convex hull algorithms. It relies on simple operations on an array of points and geometric calculations from math.
Approach 2: Gift Wrapping Algorithm (Jarvis March) (O(nh) time, O(h) space)
Jarvis March builds the convex hull by repeatedly selecting the next boundary point. Start from the leftmost point, which is guaranteed to be on the hull. Then scan all other points to find the one that forms the most counterclockwise turn relative to the current hull edge. This process “wraps” around the set of points like pulling a string around nails until it returns to the starting point.
The runtime is O(nh), where n is the number of points and h is the number of points on the hull. Each hull vertex requires scanning all points to find the next one. Space usage is O(h) for storing the boundary points. This approach is intuitive and useful when the hull size is small relative to the input size.
Recommended for interviews: The Monotone Chain convex hull algorithm is usually the expected answer. Interviewers want to see that you understand sorting points and using cross products to maintain convexity. Implementing Jarvis March shows conceptual understanding of convex hulls, but Monotone Chain demonstrates stronger algorithmic efficiency and is easier to reason about for large datasets.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Monotone Chain (Convex Hull) | O(n log n) | O(n) | General case for convex hull problems when points are unsorted |
| Gift Wrapping (Jarvis March) | O(nh) | O(h) | When the number of hull points is small compared to total points |