Erect the Fence

Problem#

Given trees as 2D points, return the trees on the convex fence (perimeter of the convex hull), including any collinear trees lying on the hull edges.

Examples#

[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] → [[1,1],[2,0],[4,2],[3,3],[2,4]] (any order).

Constraints#

1 <= trees.length <= 3000.

Approach#

Andrew’s monotone chain. Sort lexicographically. Build the lower hull, then the upper. For “include collinear” we use cross < 0 (strict) on the right-turn rejection so points on a line are kept; then deduplicate.

Solution#

class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        sort(trees.begin(), trees.end());
        int n = trees.size();
        if (n <= 2) return trees;
        auto cross = [](vector<int>& O, vector<int>& A, vector<int>& B) {
            return (long long)(A[0] - O[0]) * (B[1] - O[1])
                 - (long long)(A[1] - O[1]) * (B[0] - O[0]);
        };
        vector<vector<int>> hull;
        // lower
        for (auto& p : trees) {
            while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), p) < 0) hull.pop_back();
            hull.push_back(p);
        }
        int lower = hull.size() + 1;
        // upper
        for (int i = n - 2; i >= 0; --i) {
            auto& p = trees[i];
            while ((int)hull.size() >= lower && cross(hull[hull.size()-2], hull.back(), p) < 0) hull.pop_back();
            hull.push_back(p);
        }
        hull.pop_back();
        sort(hull.begin(), hull.end());
        hull.erase(unique(hull.begin(), hull.end()), hull.end());
        return hull;
    }
};

import "sort"

func outerTrees(trees [][]int) [][]int {
    sort.Slice(trees, func(i, j int) bool {
        if trees[i][0] != trees[j][0] {
            return trees[i][0] < trees[j][0]
        }
        return trees[i][1] < trees[j][1]
    })
    n := len(trees)
    if n <= 2 {
        return trees
    }
    cross := func(O, A, B []int) int64 {
        return int64(A[0]-O[0])*int64(B[1]-O[1]) - int64(A[1]-O[1])*int64(B[0]-O[0])
    }
    hull := [][]int{}
    for _, p := range trees {
        for len(hull) >= 2 && cross(hull[len(hull)-2], hull[len(hull)-1], p) < 0 {
            hull = hull[:len(hull)-1]
        }
        hull = append(hull, p)
    }
    lower := len(hull) + 1
    for i := n - 2; i >= 0; i-- {
        p := trees[i]
        for len(hull) >= lower && cross(hull[len(hull)-2], hull[len(hull)-1], p) < 0 {
            hull = hull[:len(hull)-1]
        }
        hull = append(hull, p)
    }
    hull = hull[:len(hull)-1]
    sort.Slice(hull, func(i, j int) bool {
        if hull[i][0] != hull[j][0] {
            return hull[i][0] < hull[j][0]
        }
        return hull[i][1] < hull[j][1]
    })
    out := [][]int{}
    for i, p := range hull {
        if i > 0 && p[0] == hull[i-1][0] && p[1] == hull[i-1][1] {
            continue
        }
        out = append(out, p)
    }
    return out
}

from typing import List

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        trees.sort(key=lambda p: (p[0], p[1]))
        n = len(trees)
        if n <= 2:
            return trees

        def cross(O, A, B):
            return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

        hull = []
        for p in trees:
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) < 0:
                hull.pop()
            hull.append(p)
        lower = len(hull) + 1
        for i in range(n - 2, -1, -1):
            p = trees[i]
            while len(hull) >= lower and cross(hull[-2], hull[-1], p) < 0:
                hull.pop()
            hull.append(p)
        hull.pop()
        # dedupe
        seen = set()
        out = []
        for p in hull:
            key = (p[0], p[1])
            if key in seen:
                continue
            seen.add(key)
            out.append(p)
        return out

function outerTrees(trees) {
    trees.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    const n = trees.length;
    if (n <= 2) return trees;
    const cross = (O, A, B) =>
        (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
    const hull = [];
    for (const p of trees) {
        while (hull.length >= 2 && cross(hull[hull.length - 2], hull[hull.length - 1], p) < 0) {
            hull.pop();
        }
        hull.push(p);
    }
    const lower = hull.length + 1;
    for (let i = n - 2; i >= 0; i--) {
        const p = trees[i];
        while (hull.length >= lower && cross(hull[hull.length - 2], hull[hull.length - 1], p) < 0) {
            hull.pop();
        }
        hull.push(p);
    }
    hull.pop();
    const seen = new Set();
    const out = [];
    for (const p of hull) {
        const key = `${p[0]},${p[1]}`;
        if (seen.has(key)) continue;
        seen.add(key);
        out.push(p);
    }
    return out;
}

class Solution {
    private long cross(int[] O, int[] A, int[] B) {
        return (long)(A[0] - O[0]) * (B[1] - O[1]) - (long)(A[1] - O[1]) * (B[0] - O[0]);
    }

    public 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[]> hull = new ArrayList<>();
        for (int[] p : trees) {
            while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) < 0) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }
        int lower = hull.size() + 1;
        for (int i = n - 2; i >= 0; i--) {
            int[] p = trees[i];
            while (hull.size() >= lower && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) < 0) {
                hull.remove(hull.size() - 1);
            }
            hull.add(p);
        }
        hull.remove(hull.size() - 1);
        Set<String> seen = new HashSet<>();
        List<int[]> out = new ArrayList<>();
        for (int[] p : hull) {
            String key = p[0] + "," + p[1];
            if (seen.contains(key)) continue;
            seen.add(key);
            out.add(p);
        }
        return out.toArray(new int[0][]);
    }
}

function outerTrees(trees: number[][]): number[][] {
    trees.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    const n = trees.length;
    if (n <= 2) return trees;
    const cross = (O: number[], A: number[], B: number[]): number =>
        (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
    const hull: number[][] = [];
    for (const p of trees) {
        while (hull.length >= 2 && cross(hull[hull.length - 2], hull[hull.length - 1], p) < 0) {
            hull.pop();
        }
        hull.push(p);
    }
    const lower = hull.length + 1;
    for (let i = n - 2; i >= 0; i--) {
        const p = trees[i];
        while (hull.length >= lower && cross(hull[hull.length - 2], hull[hull.length - 1], p) < 0) {
            hull.pop();
        }
        hull.push(p);
    }
    hull.pop();
    const seen = new Set<string>();
    const out: number[][] = [];
    for (const p of hull) {
        const key = `${p[0]},${p[1]}`;
        if (seen.has(key)) continue;
        seen.add(key);
        out.push(p);
    }
    return out;
}

Editorial#

Strict < 0 keeps collinear points (those with cross product 0 stay on the hull) — the standard <= 0 would prune them. The two halves share endpoints; popping the last and dedup’ing at the end is simpler than tracking the lower-half size carefully.

Complexity#

Time: O(n log n).
Space: O(n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#