Skip to main content
Talentd

Erect the Fence - Solution & Explanation

HardArrayMathGeometry18 min readAsked at: Amazon, Google, Meesho
Practice this problem

Problem Statement

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 <= 3000
  • trees[i].length == 2
  • 0 <= xi, yi <= 100
  • All the given positions are unique.

Approach Overview

Problem 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 1: Monotone Chain Algorithm (Convex Hull)

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n log n) due to sorting. Space complexity is O(n) for storing the hull points.

Try this approach in the editor →

Approach 2: Gift Wrapping Algorithm (Jarvis March)

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Erect the Fence -(GOOGLE) : Explanation ➕ Live Coding • codestorywithMIK • 9,321 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Erect the Fence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Erect the Fence II

Next

Sort the Students by Their Kth Score