587. Erect the Fence

Problem Description

In this problem, we are given the coordinates of various trees in a 2-dimensional garden. Each tree's position is specified as an array of two elements representing its x and y coordinates. The aim is to encircle all the trees with a rope, minimizing its length to reduce costs. The problem requires us to compute the trees that are on the boundary of the enclosed garden. These trees on the boundary will essentially contribute to the "fence" made by the rope.

The challenge here is akin to finding the convex hull of a set of points, where a convex hull is the smallest convex polygon that contains all the points. The desired result is a list of those tree coordinates that, when connected by a rope, will form the perimeter enclosing all the trees in the garden.

Intuition

To solve this problem, we employ a computational geometry algorithm known as Jarvis’s Algorithm (a.k.a. the Gift Wrapping algorithm), which is adapted slightly to find the convex hull. The idea is to start with the leftmost point (because it is guaranteed to be part of the convex hull), and select the most counterclockwise point relative to the current point, iterating over this process. The angle formed by three consecutive points is checked to determine the direction of rotation, hence if we are moving counterclockwise or not.

In implementation terms, we start by sorting the points to get the leftmost point and initialize a "stack" that will contain the indexes of points in the result hull. We go through the points, using a cross function to check if rotating from one point to another goes counterclockwise, which is determined by the sign of the cross product. We pop points from the stack when it turns out we are going clockwise indicating that the current point is creating a concave shape which we want to avoid.

The tricky part of this problem is that the garden may contain collinear points (points on the same line) along its perimeter. This means we may need to check not only the strictly convex boundary but also need to include the points making up the straight edges of the hull. To handle this, the algorithm continues to iterate over all points, making sure to check the points that are not in the strictly convex part as well. Points that have already been checked and are not part of the convex hull are not considered again using a vis array.

Through this Gift Wrapping approach, we gradually build up the convex hull by adding points that should be included in the fence's perimeter to the stack until there are no more points to consider counterclockwise to the last added point to the hull. At the end, we transform the stack of indexes into a list of the actual coordinates by referencing back to the original list of trees.

Learn more about Math patterns.

Solution Approach

The solution approach is built on the algorithm to find the convex hull of a set of points. In this situation, the points are the locations of trees. The solution uses the Jarvis Algorithm, also known as the Gift Wrapping algorithm, and is slightly adapted to include trees that are on the straight edges of the hull.

Here's a walk through the implementation using the provided Python code:

1. Sorting: First, the trees are sorted based on their x coordinates. This ensures the starting point for the Gift Wrapping algorithm is the leftmost tree, as mentioned earlier, which is guaranteed to be part of the hull.

   1trees.sort()

2. Helper Function: A helper function cross(a, b, c) computes the cross product between vectors AB and BC (where A, B, and C are points referenced by their indices in the trees list). This cross product helps determine if a point C is to the left (counterclockwise), on the line, or to the right (clockwise) of the line formed by A and B.

   1def cross(i, j, k):
   2    a, b, c = trees[i], trees[j], trees[k]
   3    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])

3. Building the Hull: The stack stk is initialized with the index 0 representing the leftmost point. A vis array keeps track of which points are already part of the hull.

   1stk = [0]
   2vis = [False] * n

4. First Pass (Lower Hull): The algorithm iterates over the points from left to right, and for every point, it retains only those that form a counterclockwise turn using the cross function. If a clockwise turn is detected, it pops points from stk until a counterclockwise turn is ensured.

   1for i in range(1, n):
   2    while len(stk) > 1 and cross(stk[-2], stk[-1], i) < 0:
   3        vis[stk.pop()] = False
   4    vis[i] = True
   5    stk.append(i)

5. Second Pass (Upper Hull): The second pass is done in the reversed order. It is crucial to include collinear points on the top edge. The stack stk is appended with points making a counterclockwise turn, and elements are popped if they make a clockwise turn.

   1m = len(stk)
   2for i in range(n - 2, -1, -1):
   3    if vis[i]:
   4        continue
   5    while len(stk) > m and cross(stk[-2], stk[-1], i) < 0:
   6        stk.pop()
   7    stk.append(i)

   The point added at the beginning of this pass (stk[-1] before entering the second pass) is duplicated, so it is removed.

   1stk.pop()

6. Result: The final step is to retrieve the points from the trees list using the indices stored in stk to get the actual coordinates of the trees that are on the fence's perimeter.

   1return [trees[i] for i in stk]

Data Structure Used: The main data structure used here is a stack implemented using a Python list (stk). A boolean list (vis) is used to keep track of visited tree indices.

Overall, the algorithm efficiently determines which trees form the outer boundary of the garden and returns their coordinates, thus satisfying the problem requirement to fence the garden using the minimum length of rope.

Example Walkthrough

Let's assume we have the following coordinates for trees in the garden: [(1,1), (2,2), (2,0), (2,4), (3,3), (4,2)].

1. Sorting Trees: First step is to sort these based on their x coordinates (if x is the same, then y). Sorted trees: [(1,1), (2,0), (2,2), (2,4), (3,3), (4,2)].

2. Helper Function cross: This function is used to determine turn direction between 3 points: counterclockwise, collinear, or clockwise.

3. Building the Hull (Initialization): We initialize the stack stk with the index 0, which is the leftmost point (1,1). We also prepare a visited points array vis with false for all points initially. stk = [0] and vis = [False, False, False, False, False, False].

4. First Pass (Lower Hull): We start iterating from the second point. After the first pass, the stack may be [0, 1, 4, 5]. This captures the points (1,1), (2,0), (3,3), and (4,2).

5. Second Pass (Upper Hull): On the reverse iteration to capture upper hull points, we include collinear points and ensure counterclockwise order. After processing, the stack could end up as [0, 1, 4, 5, 3]. The points now are (1,1), (2,0), (3,3), (4,2), and (2,4).

6. Remove Duplicate: We remove the duplicate point which in this example is (2,0), indexed at 1. The stack finally will be [0, 4, 5, 3].

7. Result: Using indices from stk, we generate actual coordinates of the hull: Output: [(1,1), (3,3), (4,2), (2,4)].

Data Structure Used: We utilized a simple list to represent the stack (stk) and another list to keep track of visited points (vis).

The result provides the coordinates that, when connected, form the fence's perimeter with the minimum needed rope while including all trees within the enclosed area.

Solution Implementation

Time and Space Complexity

The provided Python code is an implementation of the Jarvis March algorithm, also known as the Gift Wrapping algorithm, to find the convex hull of a set of points, with an extension to include points on the hull's boundaries (not just the extreme vertices). Here's the analysis of its time and space complexity:

Time complexity:

1. Sorting the points: The code begins by sorting the trees array, which has a time complexity of O(n log n) where n is the number of points.
2. Building the lower hull: The first for-loop along with the while-loop inside it constructs the lower part of the hull and it can potentially iterate through all points for every point, in the worst case. Hence, it has a time complexity of O(n).
3. Building the upper hull: The second for-loop constructs the upper hull and, similarly to the lower hull construction, has a worst-case time complexity of O(n).

The most time-consuming operation is sorting, which dictates the overall time complexity of the algorithm. Hence, the overall time complexity is O(n log n).

Space complexity:

1. Auxiliary space vis: An array to mark visited points with a space complexity of O(n).
2. Auxiliary space stk: A stack to store the indices of points in the hull with a worst-case space complexity of O(n) when all points are part of the hull.

The space consumption is mainly from the vis and stk arrays, and any additional constant space usage (variables like n and m). Therefore, the overall space complexity is O(n).

In conclusion, the time complexity of the code is O(n log n) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.