Skip to content

587. Erect the Fence

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Monotone Chain
class Solution {
 public:
  vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
    vector<vector<int>> hull;

    sort(begin(trees), end(trees), [](const auto& a, const auto& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
    });

    // Build lower hull: left-to-right scan
    for (const auto& tree : trees) {
      while (hull.size() > 1 &&
             cross(hull.back(), hull[hull.size() - 2], tree) > 0)
        hull.pop_back();
      hull.push_back(tree);
    }
    hull.pop_back();

    // Build upper hull: right-to-left scan
    for (int i = trees.size() - 1; i >= 0; --i) {
      while (hull.size() > 1 &&
             cross(hull.back(), hull[hull.size() - 2], trees[i]) > 0)
        hull.pop_back();
      hull.push_back(trees[i]);
    }

    // Remove redundant elements from the stack
    sort(begin(hull), end(hull), [](const auto& a, const auto& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
    });
    hull.erase(
        unique(begin(hull), end(hull),
               [](const auto& a,
                  const auto& b) { return a[0] == b[0] && a[1] == b[1]; }),
        end(hull));
    return hull;
  }

 private:
  int cross(const vector<int>& p, const vector<int>& q, const vector<int>& r) {
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// Monotone Chain
class Solution {
  public int[][] outerTrees(int[][] trees) {
    Stack<int[]> hull = new Stack<>();

    Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

    // Build lower hull: left-to-right scan
    for (int[] tree : trees) {
      while (hull.size() > 1 && cross(hull.peek(), hull.get(hull.size() - 2), tree) > 0)
        hull.pop();
      hull.push(tree);
    }
    hull.pop();

    // Build upper hull: right-to-left scan
    for (int i = trees.length - 1; i >= 0; --i) {
      while (hull.size() > 1 && cross(hull.peek(), hull.get(hull.size() - 2), trees[i]) > 0)
        hull.pop();
      hull.push(trees[i]);
    }

    // Remove redundant elements from the stack
    HashSet<int[]> unique = new HashSet<>(hull);
    return unique.toArray(new int[unique.size()][]);
  }

  private int cross(int[] p, int[] q, int[] r) {
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
    hull = []

    trees.sort(key=lambda x: (x[0], x[1]))

    def cross(p: List[int], q: List[int], r: List[int]) -> int:
      return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

    # Build lower hull: left-to-right scan
    for tree in trees:
      while len(hull) > 1 and cross(hull[-1], hull[-2], tree) > 0:
        hull.pop()
      hull.append(tuple(tree))
    hull.pop()

    # Build upper hull: right-to-left scan
    for tree in reversed(trees):
      while len(hull) > 1 and cross(hull[-1], hull[-2], tree) > 0:
        hull.pop()
      hull.append(tuple(tree))

    # Remove redundant elements from the stack
    return list(set(hull))