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.

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.

💪
Level Up Your
Algo Skills

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.

Python Solution

1from typing import List
2
3class Solution:
4    def outerTrees(self, points: List[List[int]]) -> List[List[int]]:
5        # Function to calculate the cross product of vectors AB and BC. 
6        # This helps determine the orientation of the triplet (A, B, C).
7        def cross_product(A_idx, B_idx, C_idx):
8            A, B, C = points[A_idx], points[B_idx], points[C_idx]
9            return (B[0] - A[0]) * (C[1] - B[1]) - (B[1] - A[1]) * (C[0] - B[0])
10
11        num_points = len(points)
12        # If there are less than 4 points, all of them constitute the convex hull.
13        if num_points < 4:
14            return points
15
16        # Sort points by their x-coordinate, and in case of a tie, by their y-coordinate.
17        points.sort()
18        # Initialize a visited array to track points that are part of the convex hull.
19        visited = [False] * num_points
20        # Initialize a stack to maintain the points forming the hull.
21        stack = [0]
22        # Construct the lower hull by moving left to right.
23        for i in range(1, num_points):
24            # While there are at least two points and the sequence forms a non-left turn, remove the middle point.
25            while len(stack) > 1 and cross_product(stack[-2], stack[-1], i) < 0:
26                visited[stack.pop()] = False
27            visited[i] = True
28            stack.append(i)
29      
30        # Remember the size of the stack to differentiate the lower and upper hull.
31        lower_hull_size = len(stack)
32        # Construct the upper hull by moving right to left.
33        for i in range(num_points - 2, -1, -1):
34            # Skip the point if it's already in the stack.
35            if visited[i]:
36                continue
37            # Similar to the lower hull construction but adding from the upper side.
38            while len(stack) > lower_hull_size and cross_product(stack[-2], stack[-1], i) < 0:
39                stack.pop()
40            stack.append(i)
41      
42        # Remove the last point because it's the same as the first one in the stack.
43        stack.pop()
44        # Construct and return the list of points that form the outer trees (convex hull).
45        return [points[i] for i in stack]
46

Java Solution

1import java.util.Arrays;
2
3public class Solution {
4    // Function to return the points that make up the convex hull of the set of points
5    public int[][] outerTrees(int[][] trees) {
6        int n = trees.length;
7        // If there are less than 4 points, all points are part of the convex hull.
8        if (n < 4) {
9            return trees;
10        }
11
12        // Sort the trees based on their x-coordinate.
13        Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
14      
15        boolean[] visited = new boolean[n]; // Track if a point is part of the convex hull.
16        int[] stack = new int[n + 10]; // Use an array as a stack to store indices of trees.
17        int count = 1; // Start with one point in the stack.
18
19        // Build lower hull
20        for (int i = 1; i < n; ++i) {
21            // Keep removing the top point from lower hull if it is a non-left turn with respect to the new point.
22            while (count > 1 && crossProduct(trees[stack[count - 1]], trees[stack[count - 2]], trees[i]) < 0) {
23                visited[stack[--count]] = false; // Mark as not part of the hull
24            }
25            visited[i] = true; // Mark as part of the hull
26            stack[count++] = i; // Push new point to the stack
27        }
28      
29        // Start adding upper hull points
30        int tempCount = count; // Remember size of lower hull
31        for (int i = n - 1; i >= 0; --i) {
32            if (visited[i]) {
33                continue; // Skip points already in the lower hull
34            }
35            // Keep removing the top point from the upper hull if it is a non-left turn.
36            while (count > tempCount && crossProduct(trees[stack[count - 1]], trees[stack[count - 2]], trees[i]) < 0) {
37                --count; // Remove the point from hull
38            }
39            stack[count++] = i; // Add new point to the stack
40        }
41      
42        // Construct the final set of points in the convex hull excluding the last duplicate point.
43        int[][] hull = new int[count - 1][2];
44        for (int i = 0; i < hull.length; ++i) {
45            hull[i] = trees[stack[i]];
46        }
47
48        return hull;
49    }
50
51    // Helper function to calculate cross product between vectors AB and BC.
52    private int crossProduct(int[] A, int[] B, int[] C) {
53        return (B[0] - A[0]) * (C[1] - B[1]) - (B[1] - A[1]) * (C[0] - B[0]);
54    }
55}
56

C++ Solution

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
9        int numTrees = trees.size();
10        // If there are fewer than 4 points, they all must be part of the hull
11        if (numTrees < 4) return trees;
12
13        // Sort the trees by x-coordinate (and by y-coordinate if x is the same)
14        sort(trees.begin(), trees.end());
15
16        // Visited marker for each tree
17        vector<int> visited(numTrees, 0);
18
19        // Stack to store indices of trees that are part of the hull
20        vector<int> hullIndices(numTrees + 10);
21        int hullCount = 1;
22
23        // Lower hull construction
24        for (int i = 1; i < numTrees; ++i) {
25            // If current point is not to the right of the line formed by last two points in hull
26            // Then pop the last point from stack because it cannot be part of hull
27            while (hullCount > 1 && cross(trees[hullIndices[hullCount - 1]], trees[hullIndices[hullCount - 2]], trees[i]) < 0) {
28                visited[hullIndices[--hullCount]] = false;
29            }
30            visited[i] = true;  // Mark point as visited
31            hullIndices[hullCount++] = i;  // Push current tree to hull
32        }
33      
34        int lowerHullSize = hullCount;
35        // Construct the upper hull, excluding the first (leftmost) point
36        for (int i = numTrees - 1; i >= 0; --i) {
37            if (visited[i]) continue;
38            // Similar process as above for upper hull
39            while (hullCount > lowerHullSize && cross(trees[hullIndices[hullCount - 1]], trees[hullIndices[hullCount - 2]], trees[i]) < 0) {
40                --hullCount;
41            }
42            hullIndices[hullCount++] = i;
43        }
44
45        // Collect all hull points except the last one, since it is a duplicate of the first
46        vector<vector<int>> hullPoints;
47        for (int i = 0; i < hullCount - 1; ++i) {
48            hullPoints.push_back(trees[hullIndices[i]]);
49        }
50
51        return hullPoints;
52    }
53
54    // Helper function to calculate the cross product of vectors OA and OB
55    // returns negative if OAB makes a right turn,
56    // positive for a left turn, and 0 if the points are collinear.
57    int cross(const vector<int>& a, const vector<int>& b, const vector<int>& c) {
58        return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
59    }
60};
61

Typescript Solution

1// Imports not needed in TypeScript as no equivalent types used
2
3// Function for checking the cross product of vectors OA and OB
4// Returns negative if OAB makes a right turn,
5// positive for a left turn, and 0 if the points are collinear.
6function cross(a: number[], b: number[], c: number[]): number {
7    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]);
8}
9
10// Function to compute the trees on the outer boundary of a set of trees
11function outerTrees(trees: number[][]): number[][] {
12    const numTrees = trees.length;
13
14    // If there are fewer than 4 points, they all must be part of the hull
15    if (numTrees < 4) return trees;
16
17    // Sort the trees by x-coordinate (and by y-coordinate if x is the same)
18    trees.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
19
20    // Visited marker for each tree
21    const visited: boolean[] = new Array(numTrees).fill(false);
22
23    // Stack to store indices of trees that are part of the hull
24    const hullIndices: number[] = [];
25    let hullCount = -1;
26
27    // Lower hull construction
28    for (let i = 0; i < numTrees; ++i) {
29        // If current point is not to the right of the line formed by last two points in hull
30        // Then pop the last point from stack because it cannot be part of hull
31        while (hullCount > 0 && cross(trees[hullIndices[hullCount - 1]], trees[hullIndices[hullCount]], trees[i]) < 0) {
32            visited[hullIndices[hullCount--]] = false;
33        }
34        visited[i] = true;  // Mark point as visited
35        hullIndices[++hullCount] = i;  // Push current tree to hull
36    }
37
38    const lowerHullSize = hullCount;
39  
40    // Construct the upper hull, excluding the first (leftmost) point
41    for (let i = numTrees - 1; i >= 0; --i) {
42        if (visited[i]) continue;
43        // Similar process as above for upper hull
44        while (hullCount > lowerHullSize && cross(trees[hullIndices[hullCount - 1]], trees[hullIndices[hullCount]], trees[i]) < 0) {
45            hullCount--;
46        }
47        hullIndices[++hullCount] = i;
48    }
49
50    // Collect all hull points except the last one, since it is a duplicate of the first
51    const hullPoints = [];
52    for (let i = 0; i < hullCount; ++i) {
53        hullPoints.push(trees[hullIndices[i]]);
54    }
55
56    return hullPoints;
57}
58
59// Global variables are typically discouraged in TypeScript to prevent pollution of the global scope.
60// This implementation avoids using classes as per your instructions, but in a regular codebase,
61// organizing related functions and data within a class or module is considered good practice.
62

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).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫