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.
The Monotone Chain Algorithm is an efficient algorithm for finding the convex hull of a set of 2D points. It constructs the hull in O(n log n) time. The idea is to sort the points, then construct the lower and upper hulls in O(n) time each. Points are rejected if they don't form a 'left turn', which can be determined using cross product.
This C code implements the Monotone Chain Algorithm for finding the convex hull. First, it sorts the points, then constructs the lower and upper hulls. Sorting ensures all points are processed in order, while stack logic applies to maintaining valid hull points by checking the turn direction using cross product.
Time complexity is O(n log n) due to sorting. Space complexity is O(n) for storing the hull points.
The Gift Wrapping Algorithm, also known as Jarvis March, is another method to find the convex hull. It builds the hull one vertex at a time, looking for the line tangent to the current edge and a point in the set of all remaining points. It's less efficient than Monotone Chain, operating in O(nh) time complexity, where h is the number of hull vertices.
This C implementation of the Gift Wrapping Algorithm iteratively chooses the most counterclockwise point until it returns to the start point. It determines orientation by calculating the cross product and compares relative angles.
Time complexity is O(nh) where n is the number of points and h is the number of points on the hull. Space complexity is O(h) for the hull array.
| Approach | Complexity |
|---|---|
| Monotone Chain Algorithm (Convex Hull) | Time complexity is O(n log n) due to sorting. Space complexity is O(n) for storing the hull points. |
| Gift Wrapping Algorithm (Jarvis March) | Time complexity is O(nh) where n is the number of points and h is the number of points on the hull. Space complexity is O(h) for the hull array. |
| Default Approach | — |
| 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 |
Erect the Fence -(GOOGLE) : Explanation ➕ Live Coding • codestorywithMIK • 8,400 views views
Watch 9 more video solutions →Practice Erect the Fence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor