LeetCode 587: Erect the Fence Solution
Master LeetCode problem 587 (Erect the Fence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
Problem Explanation
Explanation
To solve this problem, we can use the Graham Scan algorithm to find the convex hull of the trees. The convex hull is the smallest convex polygon that encloses all the trees. The algorithm works by first finding the tree with the lowest y-coordinate (and the leftmost if there are ties) to be the starting point. Then we sort the other trees based on the angle they make with the starting tree. After sorting, we iterate through the trees and keep removing any tree that makes a clockwise turn with the last two trees in the convex hull until we have found the entire convex hull.
The trees remaining after the convex hull is found will be on the fence perimeter.
Time Complexity: O(n log n) where n is the number of trees. Space Complexity: O(n) for storing the convex hull.
Solution Code
class Solution {
public int[][] outerTrees(int[][] trees) {
Arrays.sort(trees, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
Stack<int[]> stack = new Stack<>();
for (int[] tree : trees) {
while (stack.size() >= 2 && orientation(stack.get(stack.size() - 2), stack.get(stack.size() - 1), tree) > 0) {
stack.pop();
}
stack.push(tree);
}
for (int i = trees.length - 2; i >= 0; i--) {
while (stack.size() >= 2 && orientation(stack.get(stack.size() - 2), stack.get(stack.size() - 1), trees[i]) > 0) {
stack.pop();
}
stack.push(trees[i]);
}
HashSet<int[]> unique = new HashSet<>(stack);
return unique.toArray(new int[unique.size()][]);
}
private int orientation(int[] p, int[] q, int[] r) {
return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 587 (Erect the Fence)?
This page provides optimized solutions for LeetCode problem 587 (Erect the Fence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 587 (Erect the Fence)?
The time complexity for LeetCode 587 (Erect the Fence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 587 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 587 in Java, C++, or Python.