Convex Hull

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.

Approach: Monotone Chain (Andrew’s Algorithm)

Algorithm

1. The fence perimeter is exactly the convex hull of the tree points
2. Sort the points by x, then by y
3. Build the lower hull: iterate left to right, adding points and removing the last point while the last three make a clockwise (negative cross product) turn
4. Build the upper hull: iterate right to left with the same rule
5. Concatenate the two hulls, drop the duplicated endpoints, and deduplicate points that appear in both halves

Time & Space Complexity

• Time Complexity: O(n log n) - dominated by the initial sort; the hull construction is O(n)
• Space Complexity: O(n) - the lower and upper hull lists

Java Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ErectTheFence {

    public static int[][] outerTrees(int[][] trees) {
        Arrays.sort(trees, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int n = trees.length;
        if (n <= 2) {
            return trees;
        }

        List<int[]> lower = new ArrayList<>();
        for (int[] p : trees) {
            while (lower.size() >= 2
                    && cross(lower.get(lower.size() - 2), lower.get(lower.size() - 1), p) < 0) {
                lower.remove(lower.size() - 1);
            }
            lower.add(p);
        }

        List<int[]> upper = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            int[] p = trees[i];
            while (upper.size() >= 2
                    && cross(upper.get(upper.size() - 2), upper.get(upper.size() - 1), p) < 0) {
                upper.remove(upper.size() - 1);
            }
            upper.add(p);
        }

        lower.remove(lower.size() - 1);
        upper.remove(upper.size() - 1);

        Set<String> seen = new HashSet<>();
        List<int[]> result = new ArrayList<>();
        for (int[] p : lower) {
            addUnique(result, seen, p);
        }
        for (int[] p : upper) {
            addUnique(result, seen, p);
        }
        return result.toArray(new int[result.size()][]);
    }

    private static int cross(int[] o, int[] a, int[] b) {
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    }

    private static void addUnique(List<int[]> result, Set<String> seen, int[] p) {
        String key = p[0] + "," + p[1];
        if (seen.add(key)) {
            result.add(p);
        }
    }

    // Test method
    public static void main(String[] args) {
        int[][] trees1 = {{1, 1}, {2, 2}, {2, 0}, {2, 4}, {3, 3}, {4, 2}};
        System.out.println(Arrays.deepToString(outerTrees(trees1)));
        // Expected: [[1,1],[2,0],[4,2],[3,3],[2,4]]

        int[][] trees2 = {{1, 2}, {2, 2}, {4, 2}};
        System.out.println(Arrays.deepToString(outerTrees(trees2)));
        // Expected: [[1,2],[2,2],[4,2]]
    }
}

Example Walkthrough

For trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]:

1. Sorted by x then y: [1,1], [2,0], [2,2], [2,4], [3,3], [4,2]
2. Lower hull (left to right, keeping counter-clockwise turns): [1,1], [2,0], [4,2]
3. Upper hull (right to left): [4,2], [3,3], [2,4], [1,1]
4. Merging and deduplicating gives [1,1], [2,0], [4,2], [3,3], [2,4]
5. The interior point [2,2] is correctly excluded

Key Points

1. Convex Hull: The minimum rope exactly traces the convex hull boundary
2. Cross Product Sign: A negative cross product means a clockwise turn, so the middle point is popped
3. Collinear Points: Using < 0 (not <= 0) keeps points lying on the hull edges, as required by the problem
4. Lower + Upper Hull: Two sweeps in opposite directions cover the full boundary
5. Deduplication: The two endpoints shared by the lower and upper hulls are removed once