Is Erect the Fence easy or hard?

LeetCode classifies Erect the Fence as a Hard problem because it requires understanding convex hull algorithms and geometric orientation checks. While the implementation is manageable once the concept is known, many candidates struggle with handling collinear points and maintaining hull correctness.

Erect the Fence Python/Java solution

Most implementations follow the Monotone Chain algorithm. Sort the points, iterate to build the lower hull, then iterate in reverse to build the upper hull while using cross products to remove non-convex turns. The same logic works across Python, Java, C++, and JavaScript with O(n log n) complexity.

How to solve Erect the Fence in O(n)?

Pure O(n) time is generally not achievable for arbitrary input because sorting the points requires O(n log n). If the points are already sorted, the Monotone Chain hull construction itself runs in O(n). Some cases with very small hull size can approach linear behavior using Jarvis March.

What is the best approach for Erect the Fence?

The Monotone Chain convex hull algorithm is the most practical solution. It sorts the points and constructs lower and upper hulls using cross product orientation checks. The approach runs in O(n log n) time due to sorting and uses O(n) extra space. It handles collinear boundary points correctly, which is required for this problem.

Is Erect the Fence asked at Google/Amazon/Meta?

Convex hull problems like Erect the Fence appear in interviews at companies such as Google, Amazon, and Meta, especially for roles involving algorithms or graphics-related systems. Interviewers use it to evaluate understanding of computational geometry, cross products, and boundary construction logic.

What data structure is used in Erect the Fence?

The implementation mainly uses arrays or lists to store points and a stack-like structure to maintain the current convex hull. During construction, points are pushed and popped while checking orientation with cross products to maintain the convex boundary.

What is the time complexity of Erect the Fence?

The optimal solution using the Monotone Chain convex hull algorithm runs in O(n log n) time because the points must be sorted first. Building the hull itself is linear. Alternative approaches like Jarvis March run in O(nh) time, where h is the number of points on the hull.

Description Solution Video 28:52

587. Erect the Fence

Hard53.4% acceptance3 companies

You are given an array trees where trees[i] = [x_i, y_i] 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 <= 3000
trees[i].length == 2
0 <= x_i, y_i <= 100
All the given positions are unique.

Asked at 3 companies

Meesho

Google Amazon

Topics

28:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

587. Erect the Fence

Asked at 3 companies

Topics

Similar problems