Erect the Fence

Hard

#0559Time: O(N * H), where N is the total number of trees and H is the number of trees on the fence. For each of the H hull points, we iterate through all N points to find the next one. In the worst case, H can be equal to N, leading to a time complexity of O(N^2).Space: O(N) to store the hull points. In the worst case, all N points are on the hull.

Patterns

Math Geometry

Data structures

Array

Prompt

You are given an array trees where trees[i] = [x_i, y_i] 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 <= 3000
trees[i].length == 2
0 <= x_i, y_i <= 100
All the given positions are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach, also known as the Gift Wrapping algorithm, simulates wrapping a string around the set of points. It starts from an extreme point (e.g., the leftmost one) and iteratively finds the next point on the hull by selecting the one that creates the most "counter-clockwise" turn. This process continues until the hull wraps back to the starting point.

Algorithm

Find the point with the smallest x-coordinate (leftmost point). If there's a tie, pick the one with the smallest y-coordinate. This point is guaranteed to be on the convex hull and will be our starting point.
Start with the leftmost point as the current point p.
Repeatedly find the next point q on the hull. The point q is chosen such that for any other point r, the triplet (p, q, r) forms a counter-clockwise turn or is collinear. This means q is the most counter-clockwise point with respect to p.
To handle collinear points, if multiple points are equally counter-clockwise (i.e., they are collinear with p), the one farthest from p is chosen as the next vertex q.
After finding q, all points that lie on the line segment pq are also part of the hull and must be added.
Add the new point(s) to the hull and set p = q.
Repeat the process until the hull is closed, i.e., when the next point to be added is the starting point.

Walkthrough

The Jarvis's March algorithm is one of the simplest ways to compute the convex hull. It builds the hull one point at a time.

Here's a step-by-step breakdown:

Find a starting point: We must begin with a point that is guaranteed to be on the hull. The point with the minimum x-coordinate (the leftmost point) is a perfect candidate. In case of a tie, the one with the minimum y-coordinate is chosen.
Iterative Wrapping: From the current hull point p, we search for the next hull point q. We iterate through all other points r and find the one that has the smallest polar angle with respect to p. This is equivalent to finding the point r that makes the most counter-clockwise turn from the vector extending from p. The orientation can be determined using the cross product of vectors (p, q) and (p, r).
Handling Collinearity: A crucial part of the algorithm is handling points that are collinear. When we find the next point q, we must also include any points that lie on the line segment between the current point p and q. These points are part of the fence.
Termination: We add the newly found point(s) to our hull and repeat the process from the new point. The algorithm terminates when we wrap around and select our original starting point as the next point.

1class Solution {2    // Returns a value indicating the orientation of the triplet (p, q, r)3    // > 0: Counter-clockwise (left turn)4    // < 0: Clockwise (right turn)5    // = 0: Collinear6    private int orientation(int[] p, int[] q, int[] r) {7        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);8    }9 10    // Returns the squared Euclidean distance between two points11    private int distanceSq(int[] p, int[] q) {12        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);13    }14 15    public int[][] outerTrees(int[][] trees) {16        if (trees.length <= 3) {17            return trees;18        }19 20        Set<int[]> hull = new HashSet<>();21 22        // Find the leftmost point23        int startIdx = 0;24        for (int i = 1; i < trees.length; i++) {25            if (trees[i][0] < trees[startIdx][0]) {26                startIdx = i;27            }28        }29 30        int currentIdx = startIdx;31        do {32            int nextIdx = (currentIdx + 1) % trees.length;33            // Find the next point on the hull34            for (int i = 0; i < trees.length; i++) {35                int orient = orientation(trees[currentIdx], trees[nextIdx], trees[i]);36                if (orient > 0) { // trees[i] is more counter-clockwise37                    nextIdx = i;38                } else if (orient == 0) { // Collinear case39                    // If trees[i] is farther from currentIdx, it's a better candidate40                    if (distanceSq(trees[currentIdx], trees[i]) > distanceSq(trees[currentIdx], trees[nextIdx])) {41                        nextIdx = i;42                    }43                }44            }45 46            // Add all points on the segment from currentIdx to nextIdx47            for (int i = 0; i < trees.length; i++) {48                if (orientation(trees[currentIdx], trees[nextIdx], trees[i]) == 0) {49                    hull.add(trees[i]);50                }51            }52            currentIdx = nextIdx;53        } while (currentIdx != startIdx);54 55        return hull.toArray(new int[hull.size()][]);56    }57}

Complexity

Time

O(N * H), where N is the total number of trees and H is the number of trees on the fence. For each of the H hull points, we iterate through all N points to find the next one. In the worst case, H can be equal to N, leading to a time complexity of O(N^2).

Space

O(N) to store the hull points. In the worst case, all N points are on the hull.

Trade-offs

Pros

Conceptually simple and easy to understand the high-level idea.
It's an output-sensitive algorithm, meaning its performance depends on the number of hull points (H). It's efficient if H is small.

Cons

The worst-case time complexity of O(N^2) makes it unsuitable for large datasets.
The implementation can be tricky, especially the logic to correctly handle collinear points to ensure all boundary points are included without errors.

This is a more efficient algorithm that builds the convex hull by constructing the upper and lower hulls separately. It first sorts all points by their x-coordinates (and y-coordinates for ties). Then, it iterates through the sorted points to build the lower hull, and then iterates in reverse to build the upper hull. This method is generally preferred for its efficiency and simpler implementation regarding collinear points.

Algorithm

If there are 3 or fewer points, they all form the hull. Return them.
Sort the input trees array lexicographically: first by x-coordinate, and then by y-coordinate for ties.
Initialize an empty list, hull, to store the vertices of the hull.
Build the Lower Hull: Iterate through the sorted points from left to right. For each point p, check if adding it to the hull would create a clockwise turn. A clockwise turn indicates that the last point added to the hull is not part of the lower hull and should be removed. We repeatedly pop from the hull as long as a clockwise turn is formed. Then, add the current point p.
Build the Upper Hull: Iterate through the sorted points from right to left. Apply the same logic as for the lower hull: pop from the hull if a clockwise turn is formed, then add the current point.
The first and last points of the sorted array are processed twice (once for each hull), but the final result should not contain duplicates. Using a Set to store the combined hull points handles this automatically.
Convert the set of hull points back to an array and return it.

Walkthrough

The Monotone Chain algorithm, also known as Andrew's algorithm, is an efficient method for finding the convex hull of a set of points. Its main advantage is that it avoids explicit angle calculations and relies on the cross product to check orientation, which is less prone to floating-point errors and is computationally faster.

The algorithm works as follows:

Sort: The first step is to sort all the points based on their x-coordinates. If two points have the same x-coordinate, they are sorted by their y-coordinate. This gives us an ordered sequence of points from left to right.
Build Hulls: The algorithm then constructs the convex hull in two parts: the lower hull and the upper hull.
- Lower Hull: We iterate through the sorted points and build the lower hull. We use a list or stack to maintain the current lower hull vertices. For each point, we check if adding it maintains a counter-clockwise chain. If adding the new point creates a clockwise turn, it means the previous point is concave and not part of the hull, so we pop it. We continue this until a counter-clockwise turn is restored. Collinear points are kept, as the condition for popping is a strictly clockwise turn.
- Upper Hull: We do a similar pass, but this time from right to left (iterating through the sorted points in reverse), to construct the upper hull.
Combine: The final convex hull is the union of the lower and upper hulls. The start and end points of the sorted list are part of both hulls, so we need to remove duplicates when combining them. A HashSet is an easy way to achieve this.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.HashSet;4import java.util.List;5import java.util.Set;6 7class Solution {8    // Helper function to calculate the cross product (orientation)9    // > 0 for counter-clockwise turn (left)10    // < 0 for clockwise turn (right)11    // = 0 for collinear points12    private int crossProduct(int[] p1, int[] p2, int[] p3) {13        return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);14    }15 16    public int[][] outerTrees(int[][] trees) {17        if (trees.length <= 3) {18            return trees;19        }20 21        // Sort points lexicographically22        Arrays.sort(trees, (p1, p2) -> {23            if (p1[0] != p2[0]) {24                return p1[0] - p2[0];25            }26            return p1[1] - p2[1];27        });28 29        List<int[]> lowerHull = new ArrayList<>();30        // Build lower hull31        for (int[] point : trees) {32            while (lowerHull.size() >= 2 && crossProduct(lowerHull.get(lowerHull.size() - 2), lowerHull.get(lowerHull.size() - 1), point) < 0) {33                lowerHull.remove(lowerHull.size() - 1);34            }35            lowerHull.add(point);36        }37 38        List<int[]> upperHull = new ArrayList<>();39        // Build upper hull40        for (int i = trees.length - 1; i >= 0; i--) {41            int[] point = trees[i];42            while (upperHull.size() >= 2 && crossProduct(upperHull.get(upperHull.size() - 2), upperHull.get(upperHull.size() - 1), point) < 0) {43                upperHull.remove(upperHull.size() - 1);44            }45            upperHull.add(point);46        }47 48        // Combine hulls and remove duplicates49        Set<int[]> hull = new HashSet<>(lowerHull);50        hull.addAll(upperHull);51 52        return hull.toArray(new int[hull.size()][]);53    }54}

Complexity

Time

O(N log N), which is dominated by the initial sorting of the points. The two passes to build the upper and lower hulls each take O(N) time because each point is pushed onto and popped from the list at most once.

Space

O(N) to store the hull points. The lists for the lower and upper hulls can grow up to size N.

Trade-offs

Pros

Efficient with a reliable O(N log N) time complexity.
Robust and generally easier to implement correctly than other hull algorithms like Graham Scan, especially when handling collinear points.
Avoids trigonometric functions and floating-point arithmetic, making it fast and precise.

Cons

The O(N log N) complexity is dominated by sorting, which might be suboptimal if the points have some pre-existing order or special distribution where a linear-time hull algorithm could apply (though this is rare).

Solutions

Solution

1class Solution {2public3  int[][] outerTrees(int[][] trees) {4    int n = trees.length;5    if (n < 4) {6      return trees;7    }8    Arrays.sort(9        trees, (a, b)->{ return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]; });10    boolean[] vis = new boolean[n];11    int[] stk = new int[n + 10];12    int cnt = 1;13    for (int i = 1; i < n; ++i) {14      while (cnt > 1 &&15             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0) {16        vis[stk[--cnt]] = false;17      }18      vis[i] = true;19      stk[cnt++] = i;20    }21    int m = cnt;22    for (int i = n - 1; i >= 0; --i) {23      if (vis[i]) {24        continue;25      }26      while (cnt > m &&27             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0) {28        --cnt;29      }30      stk[cnt++] = i;31    }32    int[][] ans = new int[cnt - 1][2];33    for (int i = 0; i < ans.length; ++i) {34      ans[i] = trees[stk[i]];35    }36    return ans;37  }38private39  int cross(int[] a, int[] b, int[] c) {40    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);41  }42}

1class Solution {2public:3  vector<vector<int>> outerTrees(vector<vector<int>> &trees) {4    int n = trees.size();5    if (n < 4)6      return trees;7    sort(trees.begin(), trees.end());8    vector<int> vis(n);9    vector<int> stk(n + 10);10    int cnt = 1;11    for (int i = 1; i < n; ++i) {12      while (cnt > 1 &&13             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0)14        vis[stk[--cnt]] = false;15      vis[i] = true;16      stk[cnt++] = i;17    }18    int m = cnt;19    for (int i = n - 1; i >= 0; --i) {20      if (vis[i])21        continue;22      while (cnt > m &&23             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0)24        --cnt;25      stk[cnt++] = i;26    }27    vector<vector<int>> ans;28    for (int i = 0; i < cnt - 1; ++i)29      ans.push_back(trees[stk[i]]);30    return ans;31  }32  int cross(vector<int> &a, vector<int> &b, vector<int> &c) {33    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);34  }35};

1class Solution:2    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]: def cross(i, j, k): 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]) n = len(trees) if n < 4: return trees trees . sort() vis = [False] * n stk = [0] for i in range(1, n): while len(stk) > 1 and cross(stk[- 2], stk[- 1], i) < 0: vis[stk . pop()] = False vis[i] = True stk . append(i) m = len(stk) for i in range(n - 2, - 1, - 1): if vis[i]: continue while len(stk) > m and cross(stk[- 2], stk[- 1], i) < 0: stk . pop() stk . append(i) stk . pop() return [trees[i] for i in stk]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem