Erect the Fence

Hard
1309.

Erect the Fence

Erect the Fence is a hard coding problem on arrays, math and geometry, asked in Amazon and Google interviews.

trees[i] = [xi, yi] is the position of a tree in a garden; no two trees share a position. You want to wrap the whole garden with the shortest possible fence — a rope pulled tight around all the trees.

Return every tree that lies on the fence, including trees that sit on a straight stretch between two corners. Return them sorted by x, breaking ties by y (both ascending).

Example 1

Input
trees = [[0,0],[4,0],[4,4],[0,4],[2,2],[2,0],[1,3]]
Output
[[0,0],[0,4],[2,0],[4,0],[4,4]]
Explanation
The fence is the square; (2,0) sits on its bottom side, while (2,2) and (1,3) are inside.

Example 2

Input
trees = [[1,2],[2,2],[4,2]]
Output
[[1,2],[2,2],[4,2]]
Explanation
All trees are on one line, so the 'fence' is that segment and every tree touches it.

Example 3

Input
trees = [[3,5]]
Output
[[3,5]]

Constraints

  • 1 <= trees.length <= 3000
  • trees[i].length == 2
  • 0 <= xi, yi <= 100
  • All the given positions are unique.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} trees
 * @return {number[][]}
 */
var outerTrees = function(trees) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Erect the Fence — Solution in Python, Java & C++

Erect the Fence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and math.

Erect the Fence is a hard coding problem on arrays, math and geometry, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Math, Geometry
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

trees[i] = [xi, yi] is the position of a tree in a garden; no two trees share a position. You want to wrap the whole garden with the shortest possible fence — a rope pulled tight around all the trees.

Return every tree that lies on the fence, including trees that sit on a straight stretch between two corners. Return them sorted by x, breaking ties by y (both ascending).

Example 1

Input: trees = [[0,0],[4,0],[4,4],[0,4],[2,2],[2,0],[1,3]]
Output: [[0,0],[0,4],[2,0],[4,0],[4,4]]
Explanation: The fence is the square; (2,0) sits on its bottom side, while (2,2) and (1,3) are inside.

Example 2

Input: trees = [[1,2],[2,2],[4,2]]
Output: [[1,2],[2,2],[4,2]]
Explanation: All trees are on one line, so the 'fence' is that segment and every tree touches it.

Example 3

Input: trees = [[3,5]]
Output: [[3,5]]

Constraints

  • 1 <= trees.length <= 3000
  • trees[i].length == 2
  • 0 <= xi, yi <= 100
  • All the given positions are unique.

Hints for Erect the Fence

  1. Hint 1

    The fence is the convex hull of the points.

  2. Hint 2

    Andrew's monotone chain builds the hull from points sorted by x: a lower chain left to right and an upper chain right to left, popping points that make a clockwise turn.

  3. Hint 3

    To keep trees on straight stretches, pop only on a strictly clockwise turn (cross product < 0) and keep collinear points; then merge the two chains without duplicates.

How to solve Erect the Fence

Compute the convex hull with Andrew's monotone chain, keeping collinear boundary points, and report each hull point once in sorted order.

Approach

  1. Sort the trees by x, then y.
  2. Lower chain: scan left to right; while the last two chain points and the new point make a clockwise turn (cross product < 0), pop. Then push the new point.
  3. Upper chain: do the same scanning right to left.
  4. Mark every point that ended up in either chain; output the marked points in sorted order (which also removes the duplicates the two chains share).

Why it works

For points sorted by x, the lower boundary of the hull turns only counter-clockwise; any point that forms a clockwise turn with its neighbours lies strictly above the segment joining them and cannot be on the lower boundary. Popping only on strictly clockwise turns keeps points that are exactly on a boundary segment, which the fence also touches. The upper chain is the same argument mirrored. Every hull boundary point is on the lower or upper boundary, so the union of the chains is exactly the set of trees on the fence; when all trees are collinear both chains contain all of them.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Popping on cross <= 0 (the textbook version) drops trees on straight sides — this problem wants them.
  • With collinear points kept, the two chains overlap heavily (all of them, if every tree is on one line); deduplicate by index rather than appending both chains.
  • The output order is defined (sorted by x then y), so sort or emit in sorted order.

Reference solution

Python

from typing import List

def outerTrees(trees: List[List[int]]) -> List[List[int]]:
    pts = sorted([p[0], p[1]] for p in trees)
    n = len(pts)

    def cross(o, a, b):
        return (pts[a][0] - pts[o][0]) * (pts[b][1] - pts[o][1]) - (pts[a][1] - pts[o][1]) * (pts[b][0] - pts[o][0])

    on_hull = [False] * n
    for order in (range(n), range(n - 1, -1, -1)):
        chain = []
        for i in order:
            while len(chain) >= 2 and cross(chain[-2], chain[-1], i) < 0:
                chain.pop()
            chain.append(i)
        for i in chain:
            on_hull[i] = True
    return [pts[i] for i in range(n) if on_hull[i]]

Java

public static int[][] outerTrees(int[][] trees) {
    int n = trees.length;
    int[][] pts = new int[n][];
    for (int i = 0; i < n; i++) pts[i] = new int[] { trees[i][0], trees[i][1] };
    Arrays.sort(pts, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    boolean[] onHull = new boolean[n];
    for (int pass = 0; pass < 2; pass++) {
        int[] chain = new int[n];
        int size = 0;
        for (int t = 0; t < n; t++) {
            int i = pass == 0 ? t : n - 1 - t;
            while (size >= 2 && fenceCross(pts[chain[size - 2]], pts[chain[size - 1]], pts[i]) < 0) size--;
            chain[size++] = i;
        }
        for (int k = 0; k < size; k++) onHull[chain[k]] = true;
    }
    List<int[]> res = new ArrayList<>();
    for (int i = 0; i < n; i++) if (onHull[i]) res.add(pts[i]);
    return res.toArray(new int[0][]);
}

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

C++

vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
    vector<vector<int>> pts = trees;
    sort(pts.begin(), pts.end());
    int n = pts.size();
    auto cross = [&](int o, int a, int b) {
        return (pts[a][0] - pts[o][0]) * (pts[b][1] - pts[o][1]) - (pts[a][1] - pts[o][1]) * (pts[b][0] - pts[o][0]);
    };
    vector<bool> onHull(n, false);
    for (int pass = 0; pass < 2; pass++) {
        vector<int> chain;
        for (int t = 0; t < n; t++) {
            int i = pass == 0 ? t : n - 1 - t;
            while (chain.size() >= 2 && cross(chain[chain.size() - 2], chain.back(), i) < 0) chain.pop_back();
            chain.push_back(i);
        }
        for (int i : chain) onHull[i] = true;
    }
    vector<vector<int>> res;
    for (int i = 0; i < n; i++) if (onHull[i]) res.push_back(pts[i]);
    return res;
}

JavaScript

var outerTrees = function(trees) {
    var pts = trees.map(function(p) { return [p[0], p[1]]; });
    pts.sort(function(a, b) { return a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]; });
    var n = pts.length;
    var cross = function(o, a, b) {
        return (pts[a][0] - pts[o][0]) * (pts[b][1] - pts[o][1]) - (pts[a][1] - pts[o][1]) * (pts[b][0] - pts[o][0]);
    };
    var onHull = new Array(n).fill(false);
    var build = function(start, step) {
        var chain = [];
        for (var i = start; i >= 0 && i < n; i += step) {
            while (chain.length >= 2 && cross(chain[chain.length - 2], chain[chain.length - 1], i) < 0) chain.pop();
            chain.push(i);
        }
        for (var k = 0; k < chain.length; k++) onHull[chain[k]] = true;
    };
    build(0, 1);
    build(n - 1, -1);
    var res = [];
    for (var i = 0; i < n; i++) if (onHull[i]) res.push(pts[i]);
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays