LeetCode 587: Erect the Fence

Problem Restatement

We are given an array trees, where each tree is represented by a point:

[x, y]

We need to build the shortest fence that encloses all trees.

Return the coordinates of all trees that lie exactly on the fence perimeter.

This is a convex hull problem. The important detail is that trees on straight boundary edges must also be included, not only the corner points. The input length is at most 3000, and all points are unique. (leetcode.com, leetcode-in-java.github.io)

Input and Output

Example function shape:

def outerTrees(trees: list[list[int]]) -> list[list[int]]:
    ...

Examples

Example 1:

trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]

Output:

[[1,1],[2,0],[3,3],[2,4],[4,2]]

The point [2,2] is inside the fence, so it is not returned.

The other points lie on the boundary.

Example 2:

trees = [[1,2],[2,2],[4,2]]

Output:

[[1,2],[2,2],[4,2]]

All trees are on one straight line, so every tree lies on the fence perimeter.

First Thought: Try Every Polygon

One brute force idea is to try to build every possible polygon around the points and choose the one with minimum perimeter.

This is not practical.

The number of possible polygons grows extremely fast. We need to use the geometry of the outer boundary directly.

Key Insight

The fence is the convex hull of the given points.

A point is on the fence if it lies on the outer boundary of the smallest convex shape that contains all points.

We can build this boundary using the monotonic chain algorithm:

1. Sort all points by x, then by y.
2. Build the lower hull from left to right.
3. Build the upper hull from right to left.
4. Use cross products to decide whether the last point should stay on the boundary.

The cross product tells us the turn direction of three points.

For points a, b, and c, define:

cross(a, b, c) = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

If the value is negative, the three points make a clockwise turn.

For the convex hull in sorted order, a clockwise turn means the middle point is not on the outer boundary and should be removed.

For this problem, we remove only when the cross product is negative.

We do not remove when the cross product is zero, because zero means the points are collinear, and collinear boundary trees must be included.

Algorithm

1. If there are at most 2 trees, return all trees.
2. Sort the points by (x, y).
3. Build the lower hull:
   • For each point from left to right:
     • While the last two points and the current point make a clockwise turn, remove the last point.
     • Add the current point.
4. Build the upper hull:
   • For each point from right to left:
     • While the last two points and the current point make a clockwise turn, remove the last point.
     • Add the current point.
5. Combine lower and upper hull points.
6. Remove duplicates.
7. Return the result.

Correctness

Sorting the points lets us construct the boundary from left to right and then from right to left.

During lower hull construction, the algorithm maintains a chain that forms the lower outer boundary of the processed points. When the last two points of the chain and the new point make a clockwise turn, the middle point bends inward and cannot lie on the lower convex boundary. Removing it preserves the boundary invariant.

When the cross product is zero, the points are collinear. Since this problem requires all trees on the fence perimeter, the middle point must be kept if it lies on a boundary edge. Therefore, the algorithm removes only clockwise turns, not collinear points.

The same argument applies to the upper hull, built in the reverse direction.

After both passes, every outer boundary point appears in either the lower or upper hull. Interior points are removed when they create inward turns and therefore cannot remain on the boundary. Combining both hulls and removing duplicates gives exactly the trees located on the fence perimeter.

Complexity

Let:

n = len(trees)

The hull construction itself is linear after sorting.

Implementation

class Solution:
    def outerTrees(self, trees: list[list[int]]) -> list[list[int]]:
        if len(trees) <= 2:
            return trees

        points = sorted(map(tuple, trees))

        def cross(a: tuple[int, int], b: tuple[int, int], c: tuple[int, int]) -> int:
            return (
                (b[0] - a[0]) * (c[1] - a[1])
                - (b[1] - a[1]) * (c[0] - a[0])
            )

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

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

        hull = set(lower + upper)

        return [list(point) for point in hull]

Code Explanation

We handle tiny inputs immediately:

if len(trees) <= 2:
    return trees

With one or two points, every tree is on the fence.

Then we sort the points:

points = sorted(map(tuple, trees))

Tuples are convenient because they can be placed in a set later.

The cross product function is:

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

Its sign tells us the turn direction.

This builds the lower hull:

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

A negative cross product means the chain turns clockwise, so the last point is removed.

The upper hull is built the same way, but from right to left:

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

Finally, we combine both halves:

hull = set(lower + upper)

The same endpoint can appear in both hulls, so the set removes duplicates.

The result is converted back to lists:

return [list(point) for point in hull]

Why We Use < 0, Not <= 0

This detail is central to the problem.

In many convex hull problems, we remove points when:

cross(...) <= 0

That removes clockwise turns and collinear points.

But this problem asks for all trees exactly on the fence perimeter.

If three boundary trees are collinear, the middle one is still on the fence.

So we only remove when:

cross(...) < 0

That removes inward clockwise turns while keeping collinear boundary points.

Testing

def normalize(points):
    return sorted(map(tuple, points))

def run_tests():
    s = Solution()

    assert normalize(
        s.outerTrees([[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]])
    ) == normalize([[1,1],[2,0],[3,3],[2,4],[4,2]])

    assert normalize(
        s.outerTrees([[1,2],[2,2],[4,2]])
    ) == normalize([[1,2],[2,2],[4,2]])

    assert normalize(
        s.outerTrees([[0,0]])
    ) == normalize([[0,0]])

    assert normalize(
        s.outerTrees([[0,0],[1,1]])
    ) == normalize([[0,0],[1,1]])

    assert normalize(
        s.outerTrees([[0,0],[0,1],[1,0],[1,1],[0,2]])
    ) == normalize([[0,0],[1,0],[1,1],[0,2],[0,1]])

    print("all tests passed")

run_tests()

Test meaning: