Last updated on October 9th, 2024 at 05:41 pm

Here, We see Erect the Fence LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Erect the Fence LeetCode Solution

Problem Statement

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.

1. Erect the Fence LeetCode Solution C++

class Solution {
public:
    int Cross_Product_fun(vector<int> p,vector<int> q,vector<int> r){
        int ans = ((q[0]-p[0])*(r[1]-p[1]))-((q[1]-p[1])*(r[0]-p[0]));
        return ans;
    }
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        int sz = trees.size();
        if(sz<=3){
            return trees;
        }
        else{
            sort(trees.begin(),trees.end());
            vector<vector<int>> up_hull;
            vector<vector<int>> low_hull;
            up_hull.push_back(trees[0]);
            up_hull.push_back(trees[1]);
            for(int j=2;j<sz;j++){
                int n = up_hull.size();
                while(n>=2 && Cross_Product_fun(up_hull[n-2],up_hull[n-1],trees[j]) > 0){
                    up_hull.pop_back();
                    n--;
                }
                up_hull.push_back(trees[j]);
            }
            low_hull.push_back(trees[sz-1]);
            low_hull.push_back(trees[sz-2]);
            for(int j=sz-3;j>=0;j--){
                int m = low_hull.size();
                while(m>=2 && Cross_Product_fun(low_hull[m-2],low_hull[m-1],trees[j]) > 0){
                    low_hull.pop_back();
                    m--;
                }
                low_hull.push_back(trees[j]);
            }
            up_hull.insert(up_hull.end(),low_hull.begin(),low_hull.end());
            sort(up_hull.begin(),up_hull.end());
            up_hull.erase(unique(up_hull.begin(),up_hull.end()),up_hull.end());
            return up_hull;
        }
    }
};

2. Erect the Fence LeetCode Solution Java

class Solution {
    public int[][] outerTrees(int[][] trees) {
        Arrays.sort(trees, (p1, p2) -> {
            if (p1[0] == p2[0]) {
                return p2[1] - p1[1];
            }
            return p1[0] - p2[0];
        });
        Set<Point> res = new HashSet<>();
        res.add(new Point(trees[0]));
        int n = trees.length;
        int i = 0;
        while (i != n - 1) {
            double bestSlope = Integer.MIN_VALUE;
            int[] nextPoint = trees[i + 1];
            int jCandidate = i + 1;
            for (int j = i + 1; j < n; j++) {
                double slope = calculateSlope(trees[i], trees[j]);
                if (slope > bestSlope) {
                    bestSlope = slope;
                    nextPoint = trees[j];
                    jCandidate = j;
                }
            }
            i = jCandidate;
            res.add(new Point(nextPoint));
        }
        i = n - 1;
        while (i != 0) {
            double bestSlope = Integer.MIN_VALUE;
             int[] nextPoint = trees[i - 1];
            int jCandidate = i - 1;
            for (int j = i - 1; j >= 0; j--) {
                double slope = calculateSlope(trees[j], trees[i]);
                if (slope > bestSlope) {
                    bestSlope = slope;
                    nextPoint = trees[j];
                    jCandidate = j;
                }
            }
            i = jCandidate;
            res.add(new Point(nextPoint));
        }
        return res.stream().map(p -> new int[]{p.x, p.y}).toArray(int[][]::new);
    }
    private double calculateSlope(int[] p1, int[] p2) {
        if (p1[0] == p2[0]) { // 0 division
            return Integer.MIN_VALUE;
        }
        return (double) (p2[1] - p1[1]) / (double) (p2[0] - p1[0]);
    }
    private static class Point {
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public Point(int[] p) {
            this.x = p[0];
            this.y = p[1];
        }
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}

3. Erect the Fence Solution JavaScript

var outerTrees = function(trees) {
    trees.sort((a, b) => a[0] - b[0] == 0 ? a[1] - b[1] : a[0] - b[0])
    const cmpSlopes = ([x1, y1], [x2, y2], [x3, y3]) => (y3 - y1) * (x2 - x1) - (y2 - y1) * (x3 - x1)
    const higher = []
    const lower = []
    
    for (let point of trees) {
        while (higher.length > 1 && cmpSlopes(higher[higher.length - 2], higher[higher.length - 1], point) > 0) 
            higher.pop();
        while (lower.length > 1 && cmpSlopes(lower[lower.length - 2], lower[lower.length - 1], point) < 0) 
            lower.pop();
        higher.push(point);
        lower.push(point);
    }
    return [...new Set([...higher, ...lower])];
};

4. Erect the Fence Solution Python

class Solution(object):
    def outerTrees(self, trees):
        def ccw(A, B, C):
            return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])
        if len(trees) <= 1:
            return trees
        hull = []
        trees.sort()
        for i in itertools.chain(range(len(trees)), reversed(range(len(trees)-1))):
            while len(hull) >= 2 and ccw(hull[-2], hull[-1], trees[i]) < 0:
                hull.pop()
            hull.append(trees[i])
        hull.pop()
        for i in range(1, (len(hull)+1)//2):
            if hull[i] != hull[-1]:
                break
            hull.pop()
        return hull