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 <= 100The key idea in #587 Erect the Fence is to compute the convex hull of a set of points. The fence must surround all trees on the boundary, including points that lie directly on the edges of the hull. A common approach is the Monotonic Chain (Andrew's Algorithm), which constructs the convex hull after sorting points by their coordinates.
First, sort all points lexicographically (by x, then y). Then build the lower and upper hulls using a stack-like structure. While constructing each hull, use a cross product to determine the orientation of three points and decide whether a turn is clockwise or counterclockwise. Unlike some convex hull problems, this question requires including collinear boundary points, so the orientation condition must be adjusted carefully.
Finally, combine the upper and lower hulls while avoiding duplicates. Sorting dominates the runtime, giving a time complexity of O(n log n) and space complexity of O(n).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Chain Convex Hull | O(n log n) | O(n) |
codestorywithMIK
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.
Time complexity is O(n log n) due to sorting. Space complexity is O(n) for storing the hull points.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class
This Java code sorts the points and iteratively constructs the hull using the Monotone Chain method by checking the direction of turning based on the cross product, removing last point if improper direction is found.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Convex hull problems like Erect the Fence are common in advanced coding interviews, including FAANG-style rounds. They test understanding of geometry, sorting, and careful edge-case handling such as collinear points.
The optimal approach is to compute the convex hull of the given points using the Monotonic Chain algorithm. This method sorts the points and constructs upper and lower hulls while checking orientation using cross products. It runs in O(n log n) time due to sorting.
The problem relies on computational geometry concepts, particularly convex hulls and cross product orientation tests. The cross product helps determine whether three points form a clockwise, counterclockwise, or collinear turn.
Unlike standard convex hull problems, this problem requires all boundary points to be included, even if they lie on the same line segment. This means the orientation check must allow collinear points to remain in the hull rather than removing them.
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.