Scale Engineer

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
MathGeometry
Data structures
Array

Prompt

You are given an array trees where trees[i] = [xi, yi] 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 <= xi, yi <= 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:

  1. 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.
  2. 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).
  3. 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.
  4. 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.
class Solution {    // Returns a value indicating the orientation of the triplet (p, q, r)    // > 0: Counter-clockwise (left turn)    // < 0: Clockwise (right turn)    // = 0: Collinear    private int orientation(int[] p, int[] q, int[] r) {        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);    }     // Returns the squared Euclidean distance between two points    private int distanceSq(int[] p, int[] q) {        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);    }     public int[][] outerTrees(int[][] trees) {        if (trees.length <= 3) {            return trees;        }         Set<int[]> hull = new HashSet<>();         // Find the leftmost point        int startIdx = 0;        for (int i = 1; i < trees.length; i++) {            if (trees[i][0] < trees[startIdx][0]) {                startIdx = i;            }        }         int currentIdx = startIdx;        do {            int nextIdx = (currentIdx + 1) % trees.length;            // Find the next point on the hull            for (int i = 0; i < trees.length; i++) {                int orient = orientation(trees[currentIdx], trees[nextIdx], trees[i]);                if (orient > 0) { // trees[i] is more counter-clockwise                    nextIdx = i;                } else if (orient == 0) { // Collinear case                    // If trees[i] is farther from currentIdx, it's a better candidate                    if (distanceSq(trees[currentIdx], trees[i]) > distanceSq(trees[currentIdx], trees[nextIdx])) {                        nextIdx = i;                    }                }            }             // Add all points on the segment from currentIdx to nextIdx            for (int i = 0; i < trees.length; i++) {                if (orientation(trees[currentIdx], trees[nextIdx], trees[i]) == 0) {                    hull.add(trees[i]);                }            }            currentIdx = nextIdx;        } while (currentIdx != startIdx);         return hull.toArray(new int[hull.size()][]);    }}

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.

Solutions

class Solution {public  int[][] outerTrees(int[][] trees) {    int n = trees.length;    if (n < 4) {      return trees;    }    Arrays.sort(        trees, (a, b)->{ return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]; });    boolean[] vis = new boolean[n];    int[] stk = new int[n + 10];    int cnt = 1;    for (int i = 1; i < n; ++i) {      while (cnt > 1 &&             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0) {        vis[stk[--cnt]] = false;      }      vis[i] = true;      stk[cnt++] = i;    }    int m = cnt;    for (int i = n - 1; i >= 0; --i) {      if (vis[i]) {        continue;      }      while (cnt > m &&             cross(trees[stk[cnt - 1]], trees[stk[cnt - 2]], trees[i]) < 0) {        --cnt;      }      stk[cnt++] = i;    }    int[][] ans = new int[cnt - 1][2];    for (int i = 0; i < ans.length; ++i) {      ans[i] = trees[stk[i]];    }    return ans;  }private  int cross(int[] a, int[] b, int[] c) {    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);  }}

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 →

Next problem