Erect the Fence solution and explanation
Google
9 more videos on this problem
Erect the Fence -(GOOGLE) : Explanation ➕ Live CodingcodestorywithMIK · 28:52 · 9K views
Erect the Fence | Leetcode 587 | Live coding session 🔥🔥🔥Coding Decoded · 16:10 · 4K views
Leetcode 587 - Convex Hull | Erect Fence | Advanced AlgorithmNideesh Terapalli · 12:19 · 4K views
LeetCode 587. Erect the FenceHappy Coding · 28:48 · 1K views
587. Erect the Fence || Leetcode || C++ || HindiCode with Sky · 14:53 · 1K views
Daily Leetcode #963: Nov 19, 2022 - 587. Erect the FenceProgramming Live with Larry · 31:48 · 1K views
Leetcode 587. Erect the Fence | HindiThinkCode · 27:31 · 1K views
【每日一题：小Fu讲解】LeetCode 587. Erect the Fence傅码爷 · 37:12 · 1K views
Erect the Fence | Convex Hull | Graham Scan | Detailed ExplanationTanishq Chaudhary · 18:19 · 1K views
587. Erect the Fence(in Hindi) || DSA || Leetcode Daily Challenge ||Leetcode Daily Challenge · 17:28 · 1K views
The problem
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 <= 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.
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def convex_hull(points):
points = sorted(points)
if len(points) <= 1:
return points
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
if __name__ == '__main__':
trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
result = convex_hull(trees)
print("Convex Hull:")
for point in result:
print(point)import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Point implements Comparable<Point> {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
public int compareTo(Point p) {
return this.x == p.x ? this.y - p.y : this.x - p.x;
}
}
public class Main {
public static int cross(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
public static List<Point> convexHull(Point[] points) {
Arrays.sort(points);
List<Point> hull = new ArrayList<>();
for (int i = 0; i < points.length; i++) {
while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) <= 0)
hull.remove(hull.size() - 1);
hull.add(points[i]);
}
for (int i = points.length - 2, t = hull.size() + 1; i >= 0; i--) {
while (hull.size() >= t && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) <= 0)
hull.remove(hull.size() - 1);
hull.add(points[i]);
}
return hull.subList(0, hull.size() - 1);
}
public static void main(String[] args) {
Point[] trees = {new Point(1, 1), new Point(2, 2), new Point(2, 0), new Point(2, 4), new Point(3, 3), new Point(4, 2)};
List<Point> result = convexHull(trees);
System.out.println("Convex Hull:");
for (Point p : result)
System.out.println("(" + p.x + ", " + p.y + ")");
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
int x, y;
bool operator<(const Point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
};
int cross(const Point &O, const Point &A, const Point &B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector<Point> convexHull(vector<Point> &points) {
sort(points.begin(), points.end());
int n = points.size(), k = 0;
vector<Point> hull(2 * n);
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
hull[k++] = points[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
hull[k++] = points[i];
}
hull.resize(k - 1);
return hull;
}
int main() {
vector<Point> trees = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
vector<Point> result = convexHull(trees);
cout << "Convex Hull:" << endl;
for (auto &p : result)
cout << "(" << p.x << ", " << p.y << ")" << endl;
return 0;
}function cross(o, a, b) {
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
}
function convexHull(points) {
points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
if (points.length <= 1) return points;
const lower = [];
for (let p of points) {
while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], p) <= 0)
lower.pop();
lower.push(p);
}
const upper = [];
for (let i = points.length - 1; i >= 0; i--) {
let p = points[i];
while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], p) <= 0)
upper.pop();
upper.push(p);
}
upper.pop();
lower.pop();
return lower.concat(upper);
}
let trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]];
console.log("Convex Hull:", convexHull(trees));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Point {
int x, y;
};
int compare(const void *vp1, const void *vp2) {
struct Point *p1 = (struct Point *)vp1;
struct Point *p2 = (struct Point *)vp2;
return (p1->x != p2->x) ? (p1->x - p2->x) : (p1->y - p2->y);
}
int cross(struct Point O, struct Point A, struct Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
void convexHull(struct Point *points, int n, struct Point *hull, int *hullSize) {
qsort(points, n, sizeof(struct Point), compare);
int k = 0;
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross(hull[k-2], hull[k-1], points[i]) <= 0) k--;
hull[k++] = points[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(hull[k-2], hull[k-1], points[i]) <= 0) k--;
hull[k++] = points[i];
}
*hullSize = k - 1;
}
int main() {
struct Point trees[] = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
int numTrees = sizeof(trees) / sizeof(trees[0]);
struct Point hull[8];
int hullSize = 0;
convexHull(trees, numTrees, hull, &hullSize);
printf("Convex Hull:\n");
for (int i = 0; i < hullSize; i++) {
printf("(%d, %d)\n", hull[i].x, hull[i].y);
}
return 0;
}using System;
using System.Collections.Generic;
class Point : IComparable<Point> {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int CompareTo(Point p) {
return x == p.x ? y - p.y : x - p.x;
}
}
class Program {
static int Cross(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
static List<Point> ConvexHull(Point[] points) {
Array.Sort(points);
List<Point> hull = new List<Point>();
for (int i = 0; i < points.Length; i++) {
while (hull.Count >= 2 && Cross(hull[hull.Count - 2], hull[hull.Count - 1], points[i]) <= 0)
hull.RemoveAt(hull.Count - 1);
hull.Add(points[i]);
}
for (int i = points.Length - 2, t = hull.Count + 1; i >= 0; i--) {
while (hull.Count >= t && Cross(hull[hull.Count - 2], hull[hull.Count - 1], points[i]) <= 0)
hull.RemoveAt(hull.Count - 1);
hull.Add(points[i]);
}
hull.RemoveAt(hull.Count - 1);
return hull;
}
static void Main(string[] args) {
Point[] trees = { new Point(1, 1), new Point(2, 2), new Point(2, 0), new Point(2, 4), new Point(3, 3), new Point(4, 2) };
List<Point> result = ConvexHull(trees);
Console.WriteLine("Convex Hull:");
foreach (var p in result)
Console.WriteLine($"({p.x}, {p.y})");
}
}This Python code implements the Monotone Chain Algorithm to find the convex hull. The sorted points are divided into lower and upper hulls, with each hull being pruned for points that would create a non-left turn.
Time complexity is O(n log n) due to sorting. The space complexity of O(n) arises from storing the convex hull points.
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.
def orientation(p, q, r):
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
def convex_hull(points):
if len(points) < 3:
return []
hull = []
leftmost = min(range(len(points)), key=lambda i: points[i])
p = leftmost
while True:
hull.append(points[p])
q = (p + 1) % len(points)
for i in range(len(points)):
if orientation(points[p], points[i], points[q]) == 2:
q = i
p = q
if p == leftmost:
break
return hull
if __name__ == '__main__':
trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
result = convex_hull(trees)
print("Convex Hull:")
for point in result:
print(point)import java.util.ArrayList;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static int orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
return val == 0 ? 0 : (val > 0 ? 1 : 2);
}
public static ArrayList<Point> convexHull(Point points[]) {
ArrayList<Point> hull = new ArrayList<Point>();
if (points.length < 3) return hull;
int l = 0;
for (int i = 1; i < points.length; i++)
if (points[i].x < points[l].x)
l = i;
int p = l, q;
do {
hull.add(points[p]);
q = (p + 1) % points.length;
for (int i = 0; i < points.length; i++)
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
p = q;
} while (p != l);
return hull;
}
public static void main(String[] args) {
Point points[] = {new Point(1, 1), new Point(2, 2), new Point(2, 0), new Point(2, 4), new Point(3, 3), new Point(4, 2)};
ArrayList<Point> hull = convexHull(points);
System.out.println("Convex Hull:");
for (Point temp : hull)
System.out.println("(" + temp.x + ", " + temp.y + ")");
}
}#include <iostream>
#include <vector>
using namespace std;
struct Point {
int x, y;
};
int orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
return val == 0 ? 0 : (val > 0 ? 1 : 2);
}
void convexHull(vector<Point>& points) {
if (points.size() < 3) return;
vector<Point> hull;
int l = 0;
for (int i = 1; i < points.size(); i++)
if (points[i].x < points[l].x)
l = i;
int p = l, q;
do {
hull.push_back(points[p]);
q = (p + 1) % points.size();
for (int i = 0; i < points.size(); i++)
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
p = q;
} while (p != l);
cout << "Convex Hull:" << endl;
for (auto& h : hull)
cout << "(" << h.x << ", " << h.y << ")" << endl;
}
int main() {
vector<Point> points = { {1, 1}, {2, 2}, {2, 0}, {2, 4}, {3, 3}, {4, 2} };
convexHull(points);
return 0;
}function orientation(p, q, r) {
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
}
function convexHull(points) {
if (points.length < 3) return [];
const hull = [];
let leftmost = 0;
for (let i = 1; i < points.length; i++)
if (points[i][0] < points[leftmost][0])
leftmost = i;
let p = leftmost;
do {
hull.push(points[p]);
let q = (p + 1) % points.length;
for (let i = 0; i < points.length; i++)
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
p = q;
} while (p !== leftmost);
return hull;
}
let trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]];
console.log("Convex Hull:", convexHull(trees));#include <stdio.h>
#include <stdbool.h>
struct Point {
int x, y;
};
int orientation(struct Point p, struct Point q, struct Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
return val == 0 ? 0 : (val > 0 ? 1 : 2);
}
void swap(struct Point* p1, struct Point* p2) {
struct Point temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void giftWrap(struct Point points[], int n) {
if (n < 3) return;
struct Point hull[n];
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
int p = l, q;
int hullSize = 0;
do {
hull[hullSize++] = points[p];
q = (p + 1) % n;
for (int i = 0; i < n; i++)
if (orientation(points[p], points[i], points[q]) == 2)
q = i;
p = q;
} while (p != l);
printf("Convex Hull:\n");
for (int i = 0; i < hullSize; i++)
printf("(%d, %d)\n", hull[i].x, hull[i].y);
}
int main() {
struct Point trees[] = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
int numTrees = sizeof(trees) / sizeof(trees[0]);
giftWrap(trees, numTrees);
return 0;
}using System;
using System.Collections.Generic;
class Point {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Program {
static int Orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
return (val == 0) ? 0 : (val > 0 ? 1 : 2);
}
static List<Point> ConvexHull(Point[] points) {
if (points.Length < 3) return new List<Point>();
List<Point> hull = new List<Point>();
int leftmost = 0;
for (int i = 1; i < points.Length; i++)
if (points[i].x < points[leftmost].x)
leftmost = i;
int p = leftmost, q;
do {
hull.Add(points[p]);
q = (p + 1) % points.Length;
for (int i = 0; i < points.Length; i++)
if (Orientation(points[p], points[i], points[q]) == 2)
q = i;
p = q;
} while (p != leftmost);
return hull;
}
static void Main(string[] args) {
Point[] trees = { new Point(1, 1), new Point(2, 2), new Point(2, 0), new Point(2, 4), new Point(3, 3), new Point(4, 2) };
List<Point> result = ConvexHull(trees);
Console.WriteLine("Convex Hull:");
foreach (var p in result)
Console.WriteLine($"({p.x}, {p.y})");
}
}This Python code implements the Gift Wrapping algorithm to construct the convex hull. It chooses leftmost points initially then iteratively selects the next most counterclockwise point using the orientation metric.
The time complexity is O(nh), and space complexity is O(h) due to the hull list.
Approach 3: Default Approach
func outerTrees(trees [][]int) [][]int {
n := len(trees)
if n < 4 {
return trees
}
sort.Slice(trees, func(i, j int) bool {
if trees[i][0] == trees[j][0] {
return trees[i][1] < trees[j][1]
}
return trees[i][0] < trees[j][0]
})
cross := func(i, j, k int) int {
a, b, c := trees[i], trees[j], trees[k]
return (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0])
}
vis := make([]bool, n)
stk := []int{0}
for i := 1; i < n; i++ {
for len(stk) > 1 && cross(stk[len(stk)-1], stk[len(stk)-2], i) < 0 {
vis[stk[len(stk)-1]] = false
stk = stk[:len(stk)-1]
}
vis[i] = true
stk = append(stk, i)
}
m := len(stk)
for i := n - 1; i >= 0; i-- {
if vis[i] {
continue
}
for len(stk) > m && cross(stk[len(stk)-1], stk[len(stk)-2], i) < 0 {
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
var ans [][]int
for i := 0; i < len(stk)-1; i++ {
ans = append(ans, trees[stk[i]])
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Monotone Chain Algorithm (Convex Hull) | Time complexity is O(n log n) due to sorting. The space complexity of O(n) arises from storing the convex hull points. |
| Gift Wrapping Algorithm (Jarvis March) | The time complexity is O(nh), and space complexity is O(h) due to the hull list. |
| Default Approach | – |
Complexity analysis
| 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 |
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.