587. Erect the Fence LeetCode Solution

Last updated: February 19, 2025

In this guide, you will get 587. Erect the Fence LeetCode Solution with the best time and space complexity. The solution to Erect the Fence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Erect the Fence solution in C++
Erect the Fence solution in Java
Erect the Fence solution in Python
Additional Resources

587. Erect the FenceLeetCode Solution image

Problem Statement of Erect the Fence

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.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

587. Erect the Fence LeetCode Solution in C++

// Monotone Chain
class Solution {
 public:
  vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
    vector<vector<int>> hull;

    ranges::sort(trees, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
    });

    // Build the lower hull: left-to-right scan.
    for (const vector<int>& tree : trees) {
      while (hull.size() > 1 &&
             cross(hull.back(), hull[hull.size() - 2], tree) > 0)
        hull.pop_back();
      hull.push_back(tree);
    }
    hull.pop_back();

    // Build the upper hull: right-to-left scan.
    for (int i = trees.size() - 1; i >= 0; --i) {
      while (hull.size() > 1 &&
             cross(hull.back(), hull[hull.size() - 2], trees[i]) > 0)
        hull.pop_back();
      hull.push_back(trees[i]);
    }

    // Remove the redundant elements from the stack.
    ranges::sort(hull, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
    });
    hull.erase(unique(hull.begin(), hull.end(),
                      [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] && a[1] == b[1];
    }),
               hull.end());
    return hull;
  }

 private:
  int cross(const vector<int>& p, const vector<int>& q, const vector<int>& r) {
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
  }
};
/* code provided by PROGIEZ */

587. Erect the Fence LeetCode Solution in Java

// Monotone Chain
class Solution {
  public int[][] outerTrees(int[][] trees) {
    Stack<int[]> hull = new Stack<>();

    Arrays.sort(trees,
                (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

    // Build the lower hull: left-to-right scan.
    for (int[] tree : trees) {
      while (hull.size() > 1 && cross(hull.peek(), hull.get(hull.size() - 2), tree) > 0)
        hull.pop();
      hull.push(tree);
    }
    hull.pop();

    // Build the upper hull: right-to-left scan.
    for (int i = trees.length - 1; i >= 0; --i) {
      while (hull.size() > 1 && cross(hull.peek(), hull.get(hull.size() - 2), trees[i]) > 0)
        hull.pop();
      hull.push(trees[i]);
    }

    // Remove the redundant elements from the stack.
    return new HashSet<>(hull).stream().toArray(int[][] ::new);
  }

  private int cross(int[] p, int[] q, int[] r) {
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
  }
}
// code provided by PROGIEZ

587. Erect the Fence LeetCode Solution in Python

class Solution:
  def outerTrees(self, trees: list[list[int]]) -> list[list[int]]:
    hull = []

    trees.sort(key=lambda x: (x[0], x[1]))

    def cross(p: list[int], q: list[int], r: list[int]) -> int:
      return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

    # Build the lower hull: left-to-right scan.
    for tree in trees:
      while len(hull) > 1 and cross(hull[-1], hull[-2], tree) > 0:
        hull.pop()
      hull.append(tuple(tree))
    hull.pop()

    # Build the upper hull: right-to-left scan.
    for tree in reversed(trees):
      while len(hull) > 1 and cross(hull[-1], hull[-2], tree) > 0:
        hull.pop()
      hull.append(tuple(tree))

    # Remove the redundant elements from the stack.
    return list(set(hull))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents