LeetCode 587 - Erect the Fence

This problem is asking us to find the convex hull of a set of points on a 2D plane. The input trees is a list of coordinates where each coordinate [xi, yi] represents the location of a tree in the garden.

leetcodehardarraymathgeometry

LeetCode Problem 587

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry

Solution

Problem Understanding

This problem is asking us to find the convex hull of a set of points on a 2D plane. The input trees is a list of coordinates where each coordinate [xi, yi] represents the location of a tree in the garden. Our goal is to enclose all trees with a fence using the minimum perimeter, which means we want to identify all trees that lie exactly on the boundary of the convex hull. The output should be a list of coordinates representing the trees on this boundary.

The problem guarantees that the coordinates are unique and range from 0 to 100, and the total number of trees can be up to 3000. This size is large enough that naive brute-force approaches will be inefficient, so we need an algorithm that scales better. Key edge cases include trees forming a straight line (where all trees are on the boundary), clusters where some points lie strictly inside the convex hull, and multiple points on the same edge of the hull.

The important points to understand are that any tree inside the hull will not be part of the output, and points that are collinear with hull edges should be included on the fence.

Approaches

A brute-force approach would consider every pair of points and determine if all other points lie on the same side of the line formed by that pair. If they do, both endpoints of the line segment are part of the hull. While this approach is correct, it is extremely slow because it requires checking all pairs and all points, resulting in O(n³) complexity. For n up to 3000, this would be unacceptably slow.

The key insight for a better solution is that this is a classical computational geometry problem, specifically computing the convex hull of a point set. We can use the Jarvis March (Gift Wrapping) algorithm, modified to include collinear points along the edges. This works because we can "wrap" around the set of points in order of increasing polar angle, and any points collinear with the current hull edge are guaranteed to lie on the boundary. This reduces complexity to O(nh), where h is the number of hull points, and is practical for n ≤ 3000.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n) Check every pair of points to see if they form a hull edge
Optimal O(nh) O(n) Jarvis March with collinear point inclusion for convex hull

Algorithm Walkthrough

  1. Find the leftmost point: Start with the point that has the smallest x-coordinate (breaking ties with the smallest y-coordinate). This is guaranteed to be on the hull.
  2. Initialize the hull set: Create a set to store all points on the convex hull.
  3. Iterate over points: For the current hull point, find the next point such that all other points are on the same side of the line formed. This is done using a cross product to determine orientation.
  4. Handle collinear points: If other points are collinear with the current line segment, include them in the hull set. This ensures points along edges are not missed.
  5. Move to the next point: Continue wrapping around the point set until returning to the starting point. This completes the convex hull.
  6. Return the hull points: Convert the set of hull points into a list and return.

Why it works: Jarvis March guarantees that each selected point forms an edge of the convex hull because the cross product ensures all other points lie to the right or are collinear. Including collinear points ensures the output satisfies the problem requirement of including trees exactly on the fence.

Python Solution

from typing import List

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        if len(trees) <= 3:
            return trees
        
        # Cross product of OA x OB
        def cross(o, a, b):
            return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
        
        # Find the leftmost point
        start = min(trees, key=lambda x: (x[0], x[1]))
        hull = set()
        point_on_hull = start
        
        while True:
            hull.add(tuple(point_on_hull))
            next_point = trees[0]
            for candidate in trees:
                if candidate == point_on_hull:
                    continue
                orientation = cross(point_on_hull, next_point, candidate)
                if orientation < 0 or (orientation == 0 and 
                    (candidate[0]-point_on_hull[0])**2 + (candidate[1]-point_on_hull[1])**2 >
                    (next_point[0]-point_on_hull[0])**2 + (next_point[1]-point_on_hull[1])**2):
                    next_point = candidate
            point_on_hull = next_point
            if tuple(point_on_hull) == tuple(start):
                break
        
        return [list(p) for p in hull]

This Python solution starts by finding the leftmost point, then iteratively adds points to the hull using the cross product. It ensures collinear points along edges are included by comparing distances when the cross product is zero. Finally, it returns all hull points as a list.

Go Solution

package main

func outerTrees(trees [][]int) [][]int {
    if len(trees) <= 3 {
        return trees
    }

    cross := func(o, a, b []int) int {
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    }

    start := trees[0]
    for _, t := range trees {
        if t[0] < start[0] || (t[0] == start[0] && t[1] < start[1]) {
            start = t
        }
    }

    hullMap := make(map[[2]int]bool)
    pointOnHull := start

    for {
        hullMap[[2]int{pointOnHull[0], pointOnHull[1]}] = true
        nextPoint := trees[0]
        for _, candidate := range trees {
            if candidate[0] == pointOnHull[0] && candidate[1] == pointOnHull[1] {
                continue
            }
            orientation := cross(pointOnHull, nextPoint, candidate)
            if orientation < 0 || (orientation == 0 &&
                (candidate[0]-pointOnHull[0])*(candidate[0]-pointOnHull[0])+(candidate[1]-pointOnHull[1])*(candidate[1]-pointOnHull[1]) >
                (nextPoint[0]-pointOnHull[0])*(nextPoint[0]-pointOnHull[0])+(nextPoint[1]-pointOnHull[1])*(nextPoint[1]-pointOnHull[1])) {
                nextPoint = candidate
            }
        }
        pointOnHull = nextPoint
        if pointOnHull[0] == start[0] && pointOnHull[1] == start[1] {
            break
        }
    }

    result := make([][]int, 0, len(hullMap))
    for k := range hullMap {
        result = append(result, []int{k[0], k[1]})
    }
    return result
}

The Go implementation mirrors Python logic but uses a map to store points on the hull. It handles slices and integer arithmetic carefully, avoiding nil vs empty pitfalls.

Worked Examples

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

Start with leftmost [1,1].

Step through points using cross product:

  • [1,1] -> [2,0] edge confirmed.
  • Collinear check ensures [2,0] included.
  • Continue wrapping: [2,4], [3,3], [4,2] added.

Final hull set: {[1,1],[2,0],[4,2],[3,3],[2,4]}

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

All points are collinear. Start [1,2].

Next points: [2,2], [4,2] included via distance comparison.

Hull set: {[1,2],[2,2],[4,2]}

Complexity Analysis

Measure Complexity Explanation
Time O(nh) Jarvis March iterates over all points for each hull point; h is number of points on hull
Space O(n) Storing hull points in a set or map, up to n points

The algorithm is efficient for n ≤ 3000 because h is usually much smaller than n, and even in the worst case (all points on hull), O(n²) is feasible.

Test Cases

# test cases
assert sorted(Solution().outerTrees([[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]])) == sorted([[1,1],[