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 <= 3000trees[i].length == 20 <= xi, yi <= 100All the given positions are unique.
Hints for Erect the Fence
Hint 1
The fence is the convex hull of the points.
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.
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
- Sort the trees by x, then y.
- 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.
- Upper chain: do the same scanning right to left.
- 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