Leetcode 587. Erect the Fence

Problem Explanation:

Given trees in a garden represented by (x, y) coordinates, we want to find the minimum length rope that can enclose ALL the trees. In simpler terms, we are looking for points those will form the convex hull because all trees inside the convex hull can be enclosed by the fence. So, the problem can be reduced to finding the points that will form the convex hull.

Let's walk through the first example from the problem description:

Given trees: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]], the points located exactly on the fence perimeter(or forming the convex hull) would be [[1,1],[2,0],[4,2],[3,3],[2,4]].

Solution Approach:

We will use a well known algorithm called Monotone Chain or Andrew's algorithm to solve this problem. It's a simple and elegant algorithm used to find the convex hull in O(n log n) time.

Changes made to the trees list in each step of the algorithm, using the trees from the problem's first example:

Step 1: Sort points according to their x-coordinate: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]

Step 2: Perform a left-to-right scan to build the lower hull: [[1,1],[2,0],[4,2]]

Step 3: Perform a right-to-left scan to build the upper hull: [[1,1],[2,0],[4,2],[3,3],[2,4]]

At the end of these steps, we have our convex hull, represented by the points on the fence perimeter exactly.

Python Solution

1
2python
3import operator
4
5class Solution:
6    def cross(self, o, a, b):
7        return (a[0]-o[0]) * (b[1]-o[1]) - (a[1] - o[1]) * (b[0] - o[0])
8    def outerTrees(self, points):
9        points.sort(key = operator.itemgetter(0, 1))
10        lower = []
11        for p in points:
12            while len(lower) >= 2 and self.cross(lower[-2], lower[-1], p) < 0:
13                lower.pop()
14            lower.append(tuple(p))
15        upper = []
16        for p in reversed(points):
17            while len(upper) >= 2 and self.cross(upper[-2], upper[-1], p) < 0:
18                upper.pop()
19            upper.append(tuple(p))
20        return list(map(list, set(lower + upper)))

The Python solution first sorts the points, then use the Monotone Chain algorithm to find the points on lower hull and then on upper hull. Finally, it combines both the hull's points and returns them.

Java Solution

1
2java
3public class Solution {
4    public int orientation(Point p, Point q, Point r) {
5        return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
6    }
7    public List<Point> outerTrees(Point[] points) {
8        Arrays.sort(points, new Comparator<Point>() {
9            public int compare(Point p, Point q) {
10                return p.x - q.x == 0 ? p.y - q.y : p.x - q.x;
11            }
12        });
13        Stack<Point> hull = new Stack<>();
14        for (int i = 0; i < points.length; i++) {
15            while (hull.size() >= 2 && orientation(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) > 0) {
16                hull.pop();
17            }
18            hull.push(points[i]);
19        }
20        for (int i = points.length - 1, t = hull.size() + 1; i >= 0; i--) {
21            while (hull.size() >= t && orientation(hull.get(hull.size() - 2), hull.get(hull.size() - 1), points[i]) > 0) {
22                hull.pop();
23            }
24            hull.push(points[i]);
25        }
26        List<Point> res = new ArrayList<>(new HashSet<>(hull));
27        Collections.sort(res, new Comparator<Point>() {
28            public int compare(Point p, Point q) {
29                return p.x - q.x == 0 ? p.y - q.y : p.x - q.x;
30            }
31        });
32        return res;
33    }
34}

The Java solution has a similar structure as the Python solution.

JavaScript Solution

1
2javascript
3var outerTrees = function(trees) {
4    trees.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
5    const cross = (o, a, b) => (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
6    const hull = [];
7    for (const tree of [...trees, ...trees.reverse()]) {
8        while (hull.length > 1 && cross(hull[hull.length - 2], hull[hull.length - 1], tree) < 0) {
9            hull.pop();
10        }
11        hull.push(tree);
12    }
13    return [...new Set(hull)];
14};

The Javascript solution is also similar to the previous two implementations.

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
6        sort(points.begin(), points.end(), [](const vector<int>& p, const vector<int>& q){
7            return p[0] < q[0] || (p[0] == q[0] && p[1] < q[1]);
8        });
9        vector<vector<int>> hull;
10        for (int i = 0; i < points.size(); ++i) {
11            while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) < 0) {
12                hull.pop_back();
13            }
14            hull.push_back(points[i]);
15        }
16        if (hull.size() == points.size()) return hull;
17        for (int i = points.size() - 1; i >= 0; --i) {
18            while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) < 0) {
19                hull.pop_back();
20            }
21            hull.push_back(points[i]);
22        }
23        sort(hull.begin(), hull.end());
24        hull.erase(unique(hull.begin(), hull.end()), hull.end());
25        return hull;
26    }
27
28    int cross(const vector<int>& o, const vector<int>& a, const vector<int>& b) {
29        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
30    }
31};

C# Solution

1
2csharp 
3public class Solution
4{
5    public int[][] OuterTrees(int[][] trees)
6    {
7        var hull = new List<int[]>();
8        Array.Sort(trees, (a, b) => a[0] - b[0] == 0 ? a[1] - b[1] : a[0] - b[0]);
9        for (int i = 0, j = 0, k; i < trees.Length; i = j, hull.Add(trees[i]))
10            for (j = i + 1, k = i; j < trees.Length; j++)
11                if ((trees[j][0] - trees[i][0]) * (trees[j][1] - trees[k][1]) - (trees[j][1] - trees[i][1]) * (trees[j][0] - trees[k][0]) < 0) k = j;
12        for (int i = trees.Length - 1, j = i - 1, k = i, t; i > 0; i = j, j--, hull.Add(trees[i]))
13            for (t = j; j > 0; j--)
14                if ((trees[j][0] - trees[i][0]) * (trees[j][1] - trees[k][1]) - (trees[j][1] - trees[i][1]) * (trees[j][0] - trees[k][0]) < 0) k = j;
15        return hull.Distinct().ToArray();
16    }
17}

This C# code follows the exact same steps, although removes unnecessary elements without creating temporary lists and without additional element moving inside it, but by loop condition instead.Every solution operates similarly, by identifying and joining the points that create the lower and upper hull, thereby creating an enclosure that contains all the trees.

In Python, the cross method is leveraged to calculate the cross product of three points, this helps us identify whether we have a left turn or right turn at a given point.

In Java, we use a stack to keep track of current hull points. We keep popping from the stack until a valid point is found.

JavaScript's solution employs an array instead of a stack to keep track of current points forming the convex hull. It also makes use of the spread and Set operators to prevent duplicates.

The C++ solution follows the same procedure as that of the Python. It uses push_back and pop_back methods to add and remove elements from vector. It also utilizes the erase and unique function to remove duplicates.

Lastly, the C# solution uses Distinct function to remove duplicates and stores points forming the convex hull in an array.

This problem introduces us to a common algorithm used in computational geometry - Convex Hull. This concept is very useful in many other computational and graphics problems. Regardless of the programming language, the algorithm's core logic remains the same. Whether you store the intermediary results in a list, stack, or array depends on the language's data structures and the style/preferences of the programmer.