Erect the Fence – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
You are given an array trees
where trees[i] = [xi, yi]
represents the location of a tree in the garden.
You are asked to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed.
Return the coordinates of trees that are exactly located on the fence perimeter.
Example 1:
Input: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] Output: [[1,1],[2,0],[3,3],[2,4],[4,2]]
Example 2:
Input: points = [[1,2],[2,2],[4,2]] Output: [[4,2],[2,2],[1,2]]
Constraints:
1 <= points.length <= 3000
points[i].length == 2
0 <= xi, yi <= 100
- All the given points are unique.
C++ Erect the Fence LeetCode Solution
class Solution {
public:
typedef int coord_t; // coordinate type
typedef long long coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross
// product. Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B) {
return (A.x - O.x) * (coord2_t)(B.y - O.y) -
(A.y - O.y) * (coord2_t)(B.x - O.x);
}
static bool cmp(Point &p1, Point &p2) {
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
static bool equ(Point &p1, Point &p2) { return p1.x == p2.x && p1.y == p2.y; }
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> outerTrees(vector<Point> &P) {
int n = P.size(), k = 0;
vector<Point> H(2 * n);
// Sort points lexicographically
sort(P.begin(), P.end(), cmp);
// Build lower hull
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
H[k++] = P[i];
}
// Build upper hull
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
H[k++] = P[i];
}
// Remove duplicates
H.resize(k);
sort(H.begin(), H.end(), cmp);
H.erase(unique(H.begin(), H.end(), equ), H.end());
return H;
}
};
Java Erect the Fence LeetCode Solution
public class Solution {
public List<Point> outerTrees(Point[] points) {
if (points.length <= 1)
return Arrays.asList(points);
sortByPolar(points, bottomLeft(points));
Stack<Point> stack = new Stack<>();
stack.push(points[0]);
stack.push(points[1]);
for (int i = 2; i < points.length; i++) {
Point top = stack.pop();
while (ccw(stack.peek(), top, points[i]) < 0)
top = stack.pop();
stack.push(top);
stack.push(points[i]);
}
return new ArrayList<>(stack);
}
private static Point bottomLeft(Point[] points) {
Point bottomLeft = points[0];
for (Point p : points)
if (p.y < bottomLeft.y || p.y == bottomLeft.y && p.x < bottomLeft.x)
bottomLeft = p;
return bottomLeft;
}
/**
* @return positive if counter-clockwise, negative if clockwise, 0 if collinear
*/
private static int ccw(Point a, Point b, Point c) {
return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}
/**
* @return distance square of |p - q|
*/
private static int dist(Point p, Point q) {
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}
private static void sortByPolar(Point[] points, Point r) {
Arrays.sort(points, (p, q) -> {
int compPolar = ccw(p, r, q);
int compDist = dist(p, r) - dist(q, r);
return compPolar == 0 ? compDist : compPolar;
});
// find collinear points in the end positions
Point p = points[0], q = points[points.length - 1];
int i = points.length - 2;
while (i >= 0 && ccw(p, q, points[i]) == 0)
i--;
// reverse sort order of collinear points in the end positions
for (int l = i + 1, h = points.length - 1; l < h; l++, h--) {
Point tmp = points[l];
points[l] = points[h];
points[h] = tmp;
}
}
}
Python 3 Erect the Fence LeetCode Solution
class Solution(object):
def outerTrees(self, points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""
# Sort the points lexicographically (tuples are compared lexicographically).
# Remove duplicates to detect the case we have just one unique point.
# points = sorted(set(points))
points = sorted(points, key=lambda p: (p.x, p.y))
# Boring case: no points or a single point, possibly repeated multiple times.
if len(points) <= 1:
return points
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
# return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
lower.pop()
lower.append(p)
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
upper.pop()
upper.append(p)
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted because it is repeated at the
# beginning of the other list.
# return lower[:-1] + upper[:-1]
return list(set(lower[:-1] + upper[:-1]))
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1