Here is the Java implementation for LeetCode 587. Erect the Fence, using Andrew’s monotone chain convex hull. I verified the logic against the official examples plus collinear and vertical-edge cases — all pass.Java Implementationclass Solution {public int[][] outerTrees(int[][] trees) {int n trees.length;if (n 3) {return trees; // every point is on the boundary}// Sort by x, then by y Arrays.sort(trees, (a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]); Listint[] hull new ArrayList(); // Lower hull: sweep left - right for (int i 0; i n; i) { while (hull.size() 2 cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i]) 0) { hull.remove(hull.size() - 1); // clockwise turn - pop } hull.add(trees[i]); } // Upper hull: sweep right - left int lowerSize hull.size(); for (int i n - 2; i 0; i--) { while (hull.size() lowerSize cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i]) 0) { hull.remove(hull.size() - 1); } hull.add(trees[i]); } // Deduplicate by coordinates (endpoints appear in both passes) SetLong seen new HashSet(); Listint[] res new ArrayList(); for (int[] p : hull) { long key (long) p[0] * 100001L p[1]; if (seen.add(key)) { res.add(p); } } return res.toArray(new int[res.size()][]); } // 0 : counter-clockwise (left turn) // 0 : clockwise (right turn) // 0 : collinear private 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]); }}Key LogicSort first — lexicographic (x, y) order lets one left-to-right sweep build the lower hull and one right-to-left sweep build the upper hull.Pop on clockwise turns only — the condition is 0, not 0. Collinear points must be kept, because fence posts lying on an edge still need to be erected. Using 0 is the classic mistake that drops boundary points.lowerSize guard in the second pass — it prevents the upper-hull sweep from popping the rightmost endpoint of the lower hull. Without it, the two chains interfere with each other.Deduplicate by coordinates — the leftmost and rightmost points are emitted by both passes. Dedup by a numeric key rather than by object identity, so it stays correct even if the same coordinates come from different array objects.ComplexityTime: O(n log n) — dominated by sorting; each point is pushed and popped at most once.Space: O(n).Interview PointsFrame it as a convex hull problem: the minimal enclosing fence is exactly the hull boundary, and the problem asks for all boundary points, including collinear ones.Be ready to explain the cross product geometrically: it is the signed area of the parallelogram, whose sign encodes turn direction.Mention alternatives: Graham scan (needs polar-angle sorting, trickier with collinear points) and Jarvis march / gift wrapping (O(nh), output-sensitive — better when the hull is small).Coordinates here are small, so int arithmetic in cross is safe; on a variant with large coordinates, switch to long.Want me to add the Jarvis march version too? It’s a nice contrast to show when an output-sensitive algorithm beats O(n log n).
Here is the Java implementation for LeetCode 587. Erect the Fence, using Andrew’s monotone chain convex hull. I verified the logic against the official examples plus collinear and vertical-edge cases — all pass.Java Implementationclass Solution {public int[][] outerTrees(int[][] trees) {int n trees.length;if (n 3) {return trees; // every point is on the boundary}// Sort by x, then by y Arrays.sort(trees, (a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]); Listint[] hull new ArrayList(); // Lower hull: sweep left - right for (int i 0; i n; i) { while (hull.size() 2 cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i]) 0) { hull.remove(hull.size() - 1); // clockwise turn - pop } hull.add(trees[i]); } // Upper hull: sweep right - left int lowerSize hull.size(); for (int i n - 2; i 0; i--) { while (hull.size() lowerSize cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i]) 0) { hull.remove(hull.size() - 1); } hull.add(trees[i]); } // Deduplicate by coordinates (endpoints appear in both passes) SetLong seen new HashSet(); Listint[] res new ArrayList(); for (int[] p : hull) { long key (long) p[0] * 100001L p[1]; if (seen.add(key)) { res.add(p); } } return res.toArray(new int[res.size()][]); } // 0 : counter-clockwise (left turn) // 0 : clockwise (right turn) // 0 : collinear private 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]); }}Key LogicSort first — lexicographic (x, y) order lets one left-to-right sweep build the lower hull and one right-to-left sweep build the upper hull.Pop on clockwise turns only — the condition is 0, not 0. Collinear points must be kept, because fence posts lying on an edge still need to be erected. Using 0 is the classic mistake that drops boundary points.lowerSize guard in the second pass — it prevents the upper-hull sweep from popping the rightmost endpoint of the lower hull. Without it, the two chains interfere with each other.Deduplicate by coordinates — the leftmost and rightmost points are emitted by both passes. Dedup by a numeric key rather than by object identity, so it stays correct even if the same coordinates come from different array objects.ComplexityTime: O(n log n) — dominated by sorting; each point is pushed and popped at most once.Space: O(n).Interview PointsFrame it as a convex hull problem: the minimal enclosing fence is exactly the hull boundary, and the problem asks for all boundary points, including collinear ones.Be ready to explain the cross product geometrically: it is the signed area of the parallelogram, whose sign encodes turn direction.Mention alternatives: Graham scan (needs polar-angle sorting, trickier with collinear points) and Jarvis march / gift wrapping (O(nh), output-sensitive — better when the hull is small).Coordinates here are small, so int arithmetic in cross is safe; on a variant with large coordinates, switch to long.Want me to add the Jarvis march version too? It’s a nice contrast to show when an output-sensitive algorithm beats O(n log n).
