We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Erect the Fence

Difficulty: Hard

Problem Description

You are given an array trees where trees[i] = [x_i, y_i] represents the location of a tree in the garden. Fence the entire garden using the minimum length of rope, as it is expensive. The garden is well-fenced only if all the trees are enclosed. Return the coordinates of trees that are exactly located on the fence perimeter. You may return the answer in any order.

Key Insights

  • The problem can be solved using the concept of the Convex Hull, which is the smallest convex polygon that can enclose a set of points.
  • The Andrew's monotone chain algorithm is an efficient way to compute the Convex Hull in O(n log n) time.
  • The algorithm sorts the points and constructs the hull by iterating through the sorted points twice (once for the lower hull and once for the upper hull).
  • Points that are collinear with the hull can be included in the final result.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) for storing the points on the Convex Hull.

Solution

To solve the problem, we utilize the Andrew's monotone chain algorithm, which operates in the following manner:

  1. Sort the points based on their x-coordinates (and y-coordinates in case of a tie).
  2. Construct the lower hull by iterating through the sorted points and maintaining a stack of points that are part of the hull.
  3. Repeat the process in reverse to construct the upper hull.
  4. Combine the points from both the lower and upper hull, ensuring that no points are repeated, as they may be collinear.

This approach efficiently finds the perimeter points that define the fence.

Code Solutions

def outerTrees(trees):
    # Function to determine the orientation of the triplet (p, q, r)
    def orientation(p, q, r):
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])

    # Sort the points lexicographically
    trees = sorted(trees)
    
    # Build the lower hull
    lower = []
    for p in trees:
        while len(lower) >= 2 and orientation(lower[-2], lower[-1], p) < 0:
            lower.pop()
        lower.append(p)

    # Build the upper hull
    upper = []
    for p in reversed(trees):
        while len(upper) >= 2 and orientation(upper[-2], upper[-1], p) < 0:
            upper.pop()
        upper.append(p)

    # Remove the last point of each half because it's repeated at the beginning of the other half
    return list(set(lower + upper))
← Back to All Questions