Erect the Fence

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cmp(p1, p2, p3):
            x1, y1 = p1
            x2, y2 = p2            
            x3, y3 = p3

            return (y3-y2)*(x2-x1) - (y2-y1)*(x3-x2)

        points = sorted(trees)

        lower = []
        upper = []
        for point in points:
            while len(lower) >= 2 and cmp(lower[-2], lower[-1], point) > 0:
                lower.pop()
            while len(upper) >= 2 and cmp(upper[-2], upper[-1], point) < 0:
                upper.pop()

            lower.append(tuple(point))
            upper.append(tuple(point))
        
        return list(set(lower+upper))

Identifying Problem Isomorphism

“Erect the Fence” can be mapped to “Convex Hull”.

“Erect the Fence” asks you to construct a fence around a set of points, i.e., to identify the minimal convex polygon that contains all the points. This is equivalent to the computational geometry problem known as the “Convex Hull” problem.

Both problems deal with the idea of determining the smallest polygon that can encompass a given set of points. Therefore, the two problems can be viewed as conceptually similar. “Erect the Fence” is more complex because it’s embedded in a real-world context and could have more varied inputs.

10 Prerequisite LeetCode Problems

“587. Erect the Fence” is a geometric problem that involves the concept of the Convex Hull. Here are ten simpler problems to prepare for it:

  1. “149. Max Points on a Line”: This is a problem about dealing with geometric concepts and points in a plane.

  2. “447. Number of Boomerangs”: This problem involves distance computations between points in a 2D space.

  3. “593. Valid Square”: This problem provides a basic understanding of geometric properties and computations.

  4. “223. Rectangle Area”: This problem involves geometric computations in a 2D space.

  5. “356. Line Reflection”: This problem deals with geometric transformations and point symmetry.

  6. “836. Rectangle Overlap”: This problem involves determining overlapping regions between rectangles.

  7. “939. Minimum Area Rectangle”: This problem requires understanding of geometric properties and computations.

  8. “973. K Closest Points to Origin”: This problem involves sorting and computing distances in a 2D space.

  9. “1037. Valid Boomerang”: This problem involves understanding of geometric properties in a 2D space.

  10. “1232. Check If It Is a Straight Line”: This problem involves geometric computations in 2D space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import itertools

class Solution(object):
    def outerTrees(self, points):	
        def ccw(A, B, C):
            return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])

        if len(points) <= 1:
            return points

        hull = []
        points.sort()
        for i in itertools.chain(range(len(points)), reversed(range(len(points)-1))):
            while len(hull) >= 2 and ccw(hull[-2], hull[-1], points[i]) < 0:
                hull.pop()
            hull.append(points[i])
        hull.pop()

        for i in range(1, (len(hull)+1)//2):
            if hull[i] != hull[-1]:
                break
            hull.pop()
        return hull

Problem Classification

Domain Classification: This problem belongs to the “Geometry” and “Optimization” domains. It involves the computation of geometrical properties and structures, and requires finding an optimal solution (minimum length of rope).

What components:

  1. Input: An array ’trees’ where ’trees[i] = [xi, yi]’ represents the location of a tree in the garden.

  2. Output: The output is a list of coordinates of trees that are exactly located on the fence perimeter.

  3. Conditions: The goal is to enclose all trees using the minimum length of rope. All the trees must be enclosed to ensure the garden is well-fenced.

Problem Classification:

The problem can be classified as a “Computational Geometry” problem because it involves the use of geometry and mathematical concepts to solve a problem related to positioning and space. This kind of problem often includes computations based on points, lines, and polygons.

It’s also a “Optimization” problem as we are aiming to minimize the length of the rope used to fence the garden.

Lastly, the problem has elements of “Search” as we need to find and return the coordinates of trees exactly on the fence perimeter.

Language Agnostic Coding Drills

  1. Understand the Problem Statement: The problem is to find all points that form the convex hull of a set of 2D points. The convex hull is the smallest convex polygon that contains all the points.

  2. Break Down the Problem: The solution uses the Andrew’s monotone chain convex hull algorithm.

    1. Sort: We need to sort the points based on their x and y coordinates.

    2. Convex Hull Algorithm: We perform the algorithm on the sorted points and store the resultant points on the convex hull in the list.

    3. Remove duplicate points: As the algorithm is performed twice (forward and backward), we might have some duplicate points. We need to remove them.

    4. Return Result: Finally, return the points on the convex hull.

  3. Drills Breakdown:

    1. Sorting of points: Understand how to sort a list of 2D points. Points are sorted by their x-coordinate, and in case of a tie, by their y-coordinate.

    2. Understanding of Convex Hull Algorithm: Learn how the Convex Hull Algorithm works, especially the Andrew’s monotone chain algorithm used in this solution. You need to understand the ccw function which calculates the cross product of the vectors formed by three points. If the cross product is less than zero, it means the points form a right turn which is not possible in convex hull.

    3. Itertools Usage: Understand how itertools.chain is used to iterate over the sorted points twice - once in the forward direction and once in the reverse.

    4. Points Removal: Understand how to remove duplicate points from the convex hull. As we perform the algorithm twice, it can lead to duplicate points on the hull which need to be removed.

    5. Function Creation: Know how to wrap the algorithm in a function, taking care of the edge cases like if the points are less than or equal to 1, return the points as they are the convex hull.

  4. Solution Approach: With the understanding of the drills, you can follow this approach to solve the problem.

    1. If the points are less than or equal to 1, return the points.

    2. Sort the points.

    3. Perform the convex hull algorithm on the sorted points and store the points on the convex hull in a list.

    4. Remove duplicate points from the hull.

    5. Return the points on the hull.

Each drill is designed to tackle a part of the problem. Once you have a grasp of each drill, you can then integrate them into a single solution.

Targeted Drills in Python

  1. Sorting of points:
1
2
3
4
5
6

# Suppose we have the following list of points
points = [[4,2], [1,2], [1,1], [2,2], [2,1]]

# We can sort them using the sort function in Python
points.sort()
print(points)  # prints: [[1,1], [1,2], [2,1], [2,2], [4,2]]
  1. Understanding of Convex Hull Algorithm: Here, we will focus on the ccw function used to determine the cross product.
1
2
3
4
5

def ccw(A, B, C):
    return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])

# Example usage
print(ccw([1, 1], [2, 2], [3, 3]))  # prints: 0
  1. Itertools Usage: Here, we demonstrate how to use itertools.chain.
1
2
3
4
5
6
7

import itertools

# Suppose we have the following list of points
points = [[1,1], [1,2], [2,1], [2,2], [4,2]]

for i in itertools.chain(range(len(points)), reversed(range(len(points)-1))):
    print(points[i])
  1. Points Removal: This drill involves understanding how to remove duplicate points from a list. In the context of the problem, we would be removing points from the convex hull.
1
2
3
4
5
6
7

# Suppose we have the following list with duplicate points
points = [[1,1], [1,2], [1,1], [2,2], [4,2], [2,2]]

# We can remove duplicates by converting the list to a set
# Note: This method assumes the points are hashable (i.e., they are tuples or similar immutable type)
unique_points = list(set(tuple(point) for point in points))
print(unique_points)  # prints: [(1, 2), (4, 2), (2, 2), (1, 1)]
  1. Function Creation: This drill involves creating a function that wraps the entire process. A skeleton function is provided here as writing the entire function would combine the separate drills.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import itertools

def outerTrees(points):
    def ccw(A, B, C):
        pass  # To be implemented

    if len(points) <= 1:
        return points

    points.sort()

    hull = []
    for i in itertools.chain(range(len(points)), reversed(range(len(points)-1))):
        pass  # To be implemented

    return hull

# The function can be called with a list of points
print(outerTrees([[4,2], [1,2], [1,1], [2,2], [2,1]]))

In the actual problem, the points removal step would be integrated within the Convex Hull Algorithm (specifically, when adding points to the hull list). The drills provide a way to focus on these individual aspects before they are combined to solve the full problem.