{x}
blog image

Erect the Fence

You are given an array trees where trees[i] = [xi, yi] 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.

 

Example 1:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

Example 2:

Input: trees = [[1,2],[2,2],[4,2]]
Output: [[4,2],[2,2],[1,2]]
Explanation: The fence forms a line that passes through all the trees.

 

Constraints:

  • 1 <= trees.length <= 3000
  • trees[i].length == 2
  • 0 <= xi, yi <= 100
  • All the given positions are unique.

Solution Explanation for Erect the Fence

This problem asks to find the coordinates of trees forming the perimeter of the smallest convex hull enclosing all given trees. The solution uses the Gift Wrapping algorithm (also known as Jarvis March) enhanced with the Graham scan for efficiency.

Approach:

  1. Sorting: The input trees array is first sorted by x-coordinate, and then by y-coordinate for trees with the same x-coordinate. This ensures that we start with the leftmost point, a necessary condition for the Graham scan.

  2. Graham Scan (Modified): The core logic uses a variation of the Graham scan. It iterates through the sorted points twice:

    • Lower Hull: The first iteration constructs the lower hull of the convex hull. It maintains a stack (stk). For each point, it checks if the cross product of the last two points on the stack and the current point is negative. A negative cross product indicates a left turn (concave). If it's a left turn, the top point of the stack (forming a concave angle) is popped until we have only convex points remaining. The current point is then pushed onto the stack.

    • Upper Hull: The second iteration constructs the upper hull in a similar way, but it starts from the last point of the sorted array and iterates backward.

  3. Cross Product: The cross(i, j, k) function calculates the cross product of vectors (j-i) and (k-j). A negative cross product signifies a left turn, a positive cross product signifies a right turn, and zero signifies colinearity.

  4. Result: The final stack stk contains the indices of the trees forming the convex hull. The function returns the coordinates of these trees.

Time Complexity Analysis:

  • Sorting the trees array takes O(n log n) time, where n is the number of trees.
  • The Graham scan takes O(n) time in the average case and O(n^2) in the worst case (all points are collinear). However, with the initial sorting, the worst-case scenario is less likely.
  • Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity Analysis:

  • The algorithm uses a stack (stk) whose maximum size is at most n (in the worst case, all points form the convex hull).
  • The space used by vis is also O(n).
  • Therefore, the space complexity is O(n).

Code Explanation (Python Example):

The Python code efficiently implements the described algorithm. The cross function calculates the cross product. The main loop iterates through the sorted points twice to construct the lower and upper hulls, using the cross product to maintain convexity on the stack.

Code Explanation (Java, C++, Go Examples):

The Java, C++, and Go examples follow the same algorithmic approach. The core concepts of sorting, the Graham scan's modified approach using the cross product, and the stack-based hull construction remain consistent across all languages. Minor syntactic variations exist, but the underlying logic is identical.