Erect the Fence — LeetCode 587 Python Solution
HardGeometryArrayMath
- Problem
- #587
- Pattern
- Math and Number Theory
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden. Fence the entire garden using the minimum length of rope, as it is expensive.
Example
- Input
- trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
- Output
- [[1,1],[2,0],[4,2],[3,3],[2,4]]
- Explanation
- All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.
Python solution
Python
class Solution:
def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
def cross(i, j, k):
a, b, c = trees[i], trees[j], trees[k]
return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
n = len(trees)
if n < 4:
return trees
trees.sort()
vis = [False] * n
stk = [0]
for i in range(1, n):
while len(stk) > 1 and cross(stk[-2], stk[-1], i) < 0:
vis[stk.pop()] = False
vis[i] = True
stk.append(i)
m = len(stk)
for i in range(n - 2, -1, -1):
if vis[i]:
continue
while len(stk) > m and cross(stk[-2], stk[-1], i) < 0:
stk.pop()
stk.append(i)
stk.pop()
return [trees[i] for i in stk]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) or O(1) |
| Space | O(1) auxiliary |
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 587. Erect the Fence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math and Geometry.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 587. Erect the Fence?
- LeetCode 587. Erect the Fence is rated Hard on LeetCode.
- What topics does LeetCode 587. Erect the Fence cover?
- LeetCode 587. Erect the Fence is tagged Geometry, Array and Math on LeetCode.