Erect the Fence: Convex Hull with Monotone Chain

LeetCode 587, Erect the Fence, asks you to find all the trees that sit on the perimeter of a fence that encloses every tree in a garden. Given an array trees where trees[i] = [xi, yi], return the coordinates of trees that lie exactly on the fence boundary. This is the classic Convex Hull problem dressed up in a garden metaphor.

The problem

You are given a set of 2D points representing tree positions. You need to find the smallest convex polygon that contains all the points. Any point that lies on the boundary of this polygon (including vertices and edges) is part of the answer.

Input:  trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[2,4],[3,3],[4,2]]

Point [2,2] is the only tree inside the fence. The other five trees form the convex hull boundary.

The approach

The key insight is that this is a convex hull computation, and the Monotone Chain algorithm (Andrew's algorithm) handles it cleanly. It works by sorting the points, then sweeping once left to right to build the lower hull, and once right to left to build the upper hull. The union of both hulls gives you every point on the convex boundary.

The algorithm in four steps:

1. Sort points by x-coordinate, breaking ties by y.
2. Build the lower hull: iterate left to right, maintaining a stack of hull candidates. Pop the top whenever the last three points make a clockwise turn (cross product < 0).
3. Build the upper hull: iterate right to left with the same pop logic.
4. Combine and deduplicate the two hulls.

The critical detail for this problem: you use strict < 0 for the cross product check, not <= 0. Using < 0 keeps collinear points on the hull, which is exactly what the problem requires. If you used <= 0, you would skip points that lie along a hull edge.

The solution

def outerTrees(trees):
    trees.sort(key=lambda p: (p[0], p[1]))

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    lower = []
    for p in trees:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
            lower.pop()
        lower.append(p)

    upper = []
    for p in reversed(trees):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
            upper.pop()
        upper.append(p)

    return list(set(map(tuple, lower + upper)))

The cross product function cross(o, a, b) computes (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]). A negative result means the turn from o to a to b is clockwise, which means point a is not on the convex boundary and should be removed.

Step-by-step walkthrough

Let's trace through trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] using the Monotone Chain algorithm.

Key observations:

• Sorting is essential. By processing points in x-order, the lower hull sweeps across the bottom and the upper hull sweeps across the top. Together they wrap the entire boundary.
• The cross product does the heavy lifting. Every decision to keep or pop a point comes down to one multiplication and one comparison. No trigonometry, no floating-point angles.
• Collinear points stay. Because you use strict < 0 instead of <= 0, three points in a straight line all remain on the hull. This matches the problem's requirement that fence posts on a straight edge count as part of the fence.
• Deduplication is necessary. Points like (1,1) and (4,2) appear in both the lower and upper hull. A set removes the duplicates.

Complexity analysis

Time: O(n log n). Sorting dominates. The two hull-building passes each do O(n) work because every point is pushed and popped at most once.

Space: O(n). The lower and upper hull arrays together hold at most 2n entries before deduplication.

The brute force checks every pair of points to see if all other points lie on one side. That is O(n^2) pairs with O(n) checks each, giving O(n^3). The Monotone Chain algorithm reduces this to the sorting bottleneck.

The building blocks

1. Cross product orientation test

The cross product of vectors OA and OB tells you the turn direction at three points O, A, B:

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

• Positive: counterclockwise turn (point is on the left side, keep it)
• Zero: collinear (points are in a straight line)
• Negative: clockwise turn (point is on the right side, pop it)

This is the same orientation test used in computational geometry for line segment intersection, polygon area calculation, and many other problems.

2. Monotone stack with geometric condition

The hull-building loop is a monotone stack where the "pop condition" is a geometric test instead of a numeric comparison:

while len(hull) >= 2 and cross(hull[-2], hull[-1], p) < 0:
    hull.pop()
hull.append(p)

This is structurally identical to the monotone stack in Largest Rectangle in Histogram. The stack maintains an invariant (increasing heights there, counterclockwise turns here), and you pop whenever a new element violates it.

Edge cases

Before submitting, verify your solution handles:

• All collinear points like [[1,1],[2,2],[3,3]]: every point lies on the hull. The cross product is always zero, so nothing gets popped. All points are returned.
• Single point [[0,0]]: the answer is just that point. The hull is trivially the point itself.
• Two points [[0,0],[1,1]]: both points form the hull. The fence is a line segment.
• Square corners like [[0,0],[0,1],[1,0],[1,1]]: all four points are hull vertices. No interior points.
• Duplicate points: the sorting and set-based deduplication handle duplicates gracefully.

From understanding to recall

You have seen how the Monotone Chain algorithm sorts points, sweeps in two directions, and uses the cross product to decide which points belong on the convex hull. The algorithm is elegant, but the details matter: the sort order, the strict < 0 check for keeping collinear points, and the deduplication step at the end.

Under interview pressure, people commonly write the cross product formula wrong (swapping the subtraction order), use <= 0 instead of < 0 (which drops collinear points), or forget to reverse the iteration for the upper hull. These are recall failures, not understanding failures.

Spaced repetition fixes this. You practice writing the cross product formula, the lower hull loop, and the upper hull loop at increasing intervals. After a few reps, the two-pass structure and the pop condition become automatic, and you can focus on explaining the geometry rather than debugging off-by-one errors.

Related posts

• Max Points on a Line - Another geometry problem using slope calculations and point relationships
• Rectangle Area - Geometric computation with coordinate math
• Largest Rectangle in Histogram - Stack-based geometric problem that also uses a monotone approach

CodeBricks breaks the convex hull pattern into its reusable pieces and drills them individually. You type the cross product formula and the hull-building loop from scratch each time, building the muscle memory so that when you see Erect the Fence in an interview, the code flows without hesitation.