Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

587. Erect the Fence - Leetcode Solution

Code Implementation

from typing import List

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(o, a, b):
            return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
        
        trees.sort()
        n = len(trees)
        if n <= 1:
            return trees

        lower = []
        for tree in trees:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], tree) < 0:
                lower.pop()
            lower.append(tree)
        
        upper = []
        for tree in reversed(trees):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], tree) < 0:
                upper.pop()
            upper.append(tree)
        
        # Remove last point of each half because it's repeated
        result = lower[:-1] + upper[:-1]
        # Remove duplicates (colinear points may be added multiple times)
        return list(map(list, set(map(tuple, result))))
      
class Solution {
public:
    vector> outerTrees(vector>& trees) {
        auto cross = [](vector& o, vector& a, vector& b) {
            return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
        };
        sort(trees.begin(), trees.end());
        int n = trees.size();
        if (n <= 1) return trees;

        vector> lower, upper;
        for (auto& tree : trees) {
            while (lower.size() >= 2 && cross(lower[lower.size()-2], lower[lower.size()-1], tree) < 0)
                lower.pop_back();
            lower.push_back(tree);
        }
        for (int i = n - 1; i >= 0; --i) {
            while (upper.size() >= 2 && cross(upper[upper.size()-2], upper[upper.size()-1], trees[i]) < 0)
                upper.pop_back();
            upper.push_back(trees[i]);
        }
        lower.pop_back();
        upper.pop_back();
        lower.insert(lower.end(), upper.begin(), upper.end());
        // Remove duplicates
        sort(lower.begin(), lower.end());
        lower.erase(unique(lower.begin(), lower.end()), lower.end());
        return lower;
    }
};
      
class Solution {
    public int[][] outerTrees(int[][] trees) {
        Arrays.sort(trees, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int n = trees.length;
        if (n <= 1) return trees;

        List<int[]> lower = new ArrayList<>();
        for (int[] tree : trees) {
            while (lower.size() >= 2 && cross(lower.get(lower.size()-2), lower.get(lower.size()-1), tree) < 0)
                lower.remove(lower.size()-1);
            lower.add(tree);
        }
        List<int[]> upper = new ArrayList<>();
        for (int i = n - 1; i >= 0; --i) {
            while (upper.size() >= 2 && cross(upper.get(upper.size()-2), upper.get(upper.size()-1), trees[i]) < 0)
                upper.remove(upper.size()-1);
            upper.add(trees[i]);
        }
        lower.remove(lower.size()-1);
        upper.remove(upper.size()-1);
        lower.addAll(upper);
        // Remove duplicates
        Set<String> seen = new HashSet<>();
        List<int[]> res = new ArrayList<>();
        for (int[] p : lower) {
            String key = p[0] + "," + p[1];
            if (seen.add(key)) res.add(p);
        }
        return res.toArray(new int[res.size()][]);
    }
    private int cross(int[] o, int[] a, int[] b) {
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    }
}
      
/**
 * @param {number[][]} trees
 * @return {number[][]}
 */
var outerTrees = function(trees) {
    trees.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    const cross = (o, a, b) => (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    const n = trees.length;
    if (n <= 1) return trees;

    const lower = [];
    for (const tree of trees) {
        while (lower.length >= 2 && cross(lower[lower.length-2], lower[lower.length-1], tree) < 0)
            lower.pop();
        lower.push(tree);
    }
    const upper = [];
    for (let i = n - 1; i >= 0; --i) {
        while (upper.length >= 2 && cross(upper[upper.length-2], upper[upper.length-1], trees[i]) < 0)
            upper.pop();
        upper.push(trees[i]);
    }
    lower.pop();
    upper.pop();
    const result = lower.concat(upper);
    // Remove duplicates
    const seen = new Set();
    const ans = [];
    for (const p of result) {
        const key = p[0] + ',' + p[1];
        if (!seen.has(key)) {
            seen.add(key);
            ans.push(p);
        }
    }
    return ans;
};

Problem Description

The "Erect the Fence" problem asks you to find the minimum perimeter fence that can enclose all given trees in a 2D garden. Each tree is represented by its coordinates in the form [x, y]. The fence must be a convex polygon (convex hull) that touches or passes through as many trees as possible, including all trees on the boundary. If multiple valid answers exist, you can return any of them. The solution should not reuse elements, and it must include all points that are on the boundary, even if they are collinear.

Thought Process

At first glance, you might consider generating all possible polygons and checking which one has the smallest perimeter while still enclosing all the points. However, this brute-force approach is computationally infeasible for even moderate numbers of trees. Instead, the problem is a classic application of computational geometry: specifically, finding the convex hull of a set of points. The convex hull is the smallest convex polygon that contains all the points. This reduces our task to a well-known geometric algorithm. The challenge includes:
  • Handling collinear points (points that lie on the same straight line as part of the hull boundary).
  • Ensuring no duplicate points are included in the result.
  • Efficiently computing the hull, as brute-force is too slow.
The optimized approach uses an algorithm like Graham's scan or Andrew's monotone chain, which efficiently constructs the convex hull in O(N log N) time.

Solution Approach

The solution uses Andrew's monotone chain algorithm, which is efficient and easy to implement for finding the convex hull in 2D.
  1. Sort the Points: First, sort the list of trees by their x-coordinate (and by y if x is equal). This helps us process points from left to right.
  2. Build the Lower Hull: Start from the leftmost point and move right, maintaining a stack of points that form the lower part of the hull. For each new point, check if adding it would create a right turn (using the cross product). If so, remove the last point from the hull, as it cannot be part of the convex boundary.
  3. Build the Upper Hull: Repeat the process in reverse (from rightmost to leftmost) to construct the upper part of the hull.
  4. Combine Hulls: Concatenate the lower and upper hulls. The last point of each list is omitted to avoid duplication, as the upper and lower hulls meet at the endpoints.
  5. Remove Duplicates: Since collinear points may be included more than once, use a set or similar structure to remove duplicates.
  6. Return the Result: The result is a list of points representing the convex hull, which is the minimum fence enclosing all the trees.
The cross product is used to determine the orientation (left turn, right turn, or collinear) of three consecutive points. This is crucial for maintaining the convexity of the hull.

Example Walkthrough

Let's consider the input trees = [[1,1], [2,2], [2,0], [2,4], [3,3], [4,2]].
  1. Sort: The sorted order is [[1,1], [2,0], [2,2], [2,4], [3,3], [4,2]].
  2. Lower Hull:
    • Add [1,1].
    • Add [2,0].
    • Check [2,2]: Adding creates a left turn, so keep it.
    • Check [2,4]: Adding creates a left turn, so keep it.
    • Check [3,3]: Adding creates a right turn, so pop [2,4].
    • Continue until all points are processed.
  3. Upper Hull:
    • Process in reverse: [4,2], [3,3], [2,4], [2,2], [2,0], [1,1].
    • Similar logic applies, maintaining only points needed for the hull.
  4. Combine and Remove Duplicates: The final hull is [[1,1], [2,0], [4,2], [3,3], [2,4]] (order may vary).
Each step ensures only the necessary boundary points are kept, and collinear points on the hull are included.

Time and Space Complexity

  • Brute-force: O(N!) — Generating all possible polygons is not feasible.
  • Optimized (Monotone Chain):
    • Time Complexity: O(N log N), dominated by the sorting step. Each point is added and removed from the hull at most once.
    • Space Complexity: O(N), for storing the hull and temporary structures.
The optimized approach is efficient and practical for all reasonable input sizes.

Summary

The "Erect the Fence" problem is a classic convex hull challenge in computational geometry. By recognizing the need for a convex hull and using Andrew's monotone chain algorithm, we efficiently find the minimal fence enclosing all trees. The key insights are sorting, using the cross product for orientation, and careful handling of collinear points. The approach is both elegant and efficient, making it well-suited for real-world applications involving geometric boundaries.