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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Erect the Fence

Number: 587

Difficulty: Hard

Paid? No

Companies: Amazon, Google

Problem Description

Given the positions of trees in a garden, determine the minimum rope needed to enclose all the trees. In other words, return all the tree coordinates that lie on the perimeter of the fence. Note that if trees lie along an edge (i.e. are collinear), they should all be included.

Key Insights

  • The problem is essentially about computing the convex hull but requires including all collinear points on the boundary.
  • A common approach is to use the Gift Wrapping (Jarvis March) algorithm which “wraps” the set of points.
  • While selecting the next hull point, handle collinear cases by checking points that lie on the line between the current point and the candidate.
  • An orientation function (using cross product) is the key to comparing turns and detecting collinearity.

Space and Time Complexity

Time Complexity: O(nh) in worst-case (where n is the number of trees and h is the number of hull points) – often similar to O(n^2) in worst-case scenarios. Space Complexity: O(n) for storing the result and helper data structures.

Solution

We can solve this problem with the Jarvis March algorithm. The algorithm works as follows:

  1. Identify the leftmost point as the starting point.
  2. Set the current point and iterate to find the next candidate such that for every other point, the triplet (current, candidate, other) forms a clockwise turn. If points are collinear (zero cross-product), pick the furthest one as the candidate.
  3. After determining a candidate, iterate through all points again to collect every tree that is collinear with the edge from the current point to the candidate. This ensures that all collinear boundary points are included.
  4. Repeat until the starting point is reached.

The orientation is determined via the cross product. A positive result indicates a counterclockwise (left) turn, a negative indicates a clockwise (right) turn, and zero indicates collinearity.

This approach uses simple loops and geometric calculations to methodically “wrap” the set of points, ensuring every point on the boundary is included.

Code Solutions

# Python solution using Jarvis March (Gift Wrapping) algorithm

def outerTrees(trees):
    # Function to calculate the orientation of triplet (p, q, r)
    # Returns:
    #   positive value if counterclockwise,
    #   negative if clockwise,
    #   0 if collinear.
    def orientation(p, q, r):
        return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
    
    # Handle edge cases: if few trees, all are on the fence.
    if len(trees) <= 3:
        return trees
    
    # Find the leftmost tree (smallest x; if tie, smallest y)
    start = min(trees, key=lambda p: (p[0], p[1]))
    hull = []
    cur = start

    while True:
        # Candidate for next point in hull
        candidate = trees[0]
        # To ensure candidate is not the current point
        if candidate == cur:
            candidate = trees[1]
        # Traverse through all trees to find the most clockwise point
        for tree in trees:
            if tree == cur:
                continue
            cross = orientation(cur, candidate, tree)
            # If tree is more clockwise, update candidate.
            if cross < 0:
                candidate = tree
            # If collinear, choose the tree further away
            elif cross == 0:
                # Check if tree is farther from cur than candidate
                if (tree[0] - cur[0]) ** 2 + (tree[1] - cur[1]) ** 2 > (candidate[0] - cur[0]) ** 2 + (candidate[1] - cur[1]) ** 2:
                    candidate = tree
        
        # Add all trees that are collinear with the current edge.
        for tree in trees:
            if tree not in hull and orientation(cur, candidate, tree) == 0:
                hull.append(tree)
        
        cur = candidate  # Move to next point
        if cur == start:
            break

    return hull

# Example usage:
trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
print(outerTrees(trees))
← Back to All Questions