LeetCode 587: Erect the Fence Solution in Python – A Step-by-Step Guide

What Is LeetCode 587: Erect the Fence?

In LeetCode 587: Erect the Fence, you’re given a list of tuples trees where each tuple (x, y) represents the coordinates of a tree on a 2D plane. Your task is to return a list of coordinates representing the vertices of the smallest convex polygon (convex hull) that encloses all the trees, in counterclockwise order. A convex hull is the smallest convex shape that contains all points, where no interior angle exceeds 180°. For example, with trees = [(1,1), (2,2), (2,0), (2,4), (3,3), (4,2)], the result is [(1,1), (2,0), (4,2), (2,4)]. This problem builds on LeetCode 23: Merge k Sorted Lists for algorithmic thinking but dives into geometry with the convex hull concept.

Problem Statement

• Input: trees (List[Tuple[int, int]])—list of (x, y) coordinates of trees.
• Output: List[Tuple[int, int]]—vertices of convex hull in counterclockwise order.
• Rules: Enclose all trees; return smallest convex polygon; points may be collinear.

Constraints

• 1 <= trees.length <= 3000
• 0 <= x, y <= 10⁸
• All coordinates are distinct

Examples

• Input: trees = [(1,1),(2,2),(2,0),(2,4),(3,3),(4,2)]
• Output: [(1,1),(2,0),(4,2),(2,4)]
• Convex hull encloses all points.
• Input: trees = [(1,2),(2,2),(4,2)]
• Output: [(1,2),(4,2)]
• Collinear points, hull is a line segment.
• Input: trees = [(1,1)]
• Output: [(1,1)]
• Single point is its own hull.

Understanding the Problem: Building the Convex Hull

To solve LeetCode 587: Erect the Fence in Python, we need to find the convex hull of a set of 2D points, returning the vertices in counterclockwise order, handling up to 3000 points efficiently. A brute-force approach checking all possible polygons (O(n³)) is impractical. Instead, Graham’s scan algorithm computes the convex hull in O(n log n) time by sorting points and iteratively building the hull, leveraging geometric properties like cross products to ensure convexity. We’ll explore:

• Best Solution (Graham’s Scan for Convex Hull): O(n log n) time, O(n) space—fast and optimal.
• Alternative Solution (Brute-Force Convex Hull Checking): O(n³) time, O(1) space—thorough but slow.

Let’s dive into Graham’s scan with a friendly breakdown!

Best Solution: Graham’s Scan for Convex Hull

Why Graham’s Scan Wins

Graham’s scan is the best for LeetCode 587 because it computes the convex hull in O(n log n) time and O(n) space by sorting points by x-coordinate and then iteratively constructing the upper and lower hulls using a stack, efficiently determining convexity with cross products in a single pass after sorting. It’s like sketching a fence around trees, starting from the leftmost point and adjusting to keep the shape convex—all in a swift, geometric dance!

How It Works

Think of this as a hull-building architect:

• Step 1: Sort Points:
• Sort trees by x-coordinate, then y-coordinate for ties.
• Step 2: Build Lower Hull:
• Start with leftmost point, add points to stack.
• For each point, check if last three points make a clockwise turn (pop if so).
• Step 3: Build Upper Hull:
• Start from rightmost point, repeat process backwards.
• Step 4: Combine Hulls:
• Merge lower and upper hulls, remove duplicates (endpoints).
• Step 5: Return Result:
• List of hull vertices in counterclockwise order.
• Why It Works:
• Sorting ensures left-to-right progression.
• Cross product identifies non-convex turns.

It’s like a convex-hull crafting maestro!

Step-by-Step Example

Example: trees = [(1,1),(2,2),(2,0),(2,4),(3,3),(4,2)]

• Step 1: Sort: [(1,1), (2,0), (2,2), (2,4), (3,3), (4,2)].
• Step 2: Lower hull:
• Stack: [(1,1)].
• (2,0): Cross (1,1)-(2,0) counterclockwise, add → [(1,1), (2,0)].
• (2,2): Cross (1,1)-(2,0)-(2,2) clockwise, pop (2,0), add (2,2) → [(1,1), (2,2)].
• (2,4): Cross counterclockwise, pop (2,2), add (2,4) → [(1,1), (2,4)].
• (3,3): Cross clockwise, pop (2,4), add (3,3) → [(1,1), (3,3)].
• (4,2): Cross counterclockwise, add → [(1,1), (3,3), (4,2)].
• Lower: [(1,1), (4,2)].
• Step 3: Upper hull (reverse):
• Stack: [(4,2)].
• (3,3): Cross counterclockwise, add → [(4,2), (3,3)].
• (2,4): Cross counterclockwise, add → [(4,2), (3,3), (2,4)].
• (2,2): Cross clockwise, pop (2,4), add (2,2) → [(4,2), (3,3), (2,2)].
• (2,0): Cross clockwise, pop (2,2), add (2,0) → [(4,2), (3,3), (2,0)].
• (1,1): Cross clockwise, pop (2,0), add (1,1) → [(4,2), (3,3), (1,1)].
• Upper: [(4,2), (2,4), (1,1)].
• Step 4: Combine: [(1,1), (2,0), (4,2), (2,4)] (adjust for counterclockwise).
• Result: [(1,1), (2,0), (4,2), (2,4)].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

from typing import List, Tuple

class Solution:
    def outerTrees(self, trees: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
        # Step 1: Sort points by x, then y
        points = sorted(trees)
        if len(points) <= 1:
            return points

        # Step 2: Cross product helper to determine turn direction
        def cross(p1, p2, p3):
            return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

        # Step 3: Build lower hull
        lower = []
        for p in points:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
                lower.pop()
            lower.append(p)

        # Step 4: Build upper hull
        upper = []
        for p in reversed(points):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
                upper.pop()
            upper.append(p)

        # Step 5: Combine hulls, remove duplicates
        return list(set(lower[:-1] + upper[:-1]))

• Line 6-8: Sort points, handle base case (0 or 1 point).
• Lines 11-12: Cross product: Positive = counterclockwise, negative = clockwise, zero = collinear.
• Lines 15-19: Lower hull:
• Add point, pop if clockwise turn detected.
• Lines 22-26: Upper hull:
• Same process in reverse order.
• Line 29: Combine, exclude duplicate endpoints, convert to list.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(n)—stack storage.

It’s like a fence-building genius!

Alternative Solution: Brute-Force Convex Hull Checking

Why an Alternative Approach?

The brute-force convex hull checking approach tests all possible triangles to determine if a point lies outside, building the hull by checking convexity, running in O(n³) time and O(1) space (excluding output). It’s thorough but impractical for large sets, making it a baseline for small inputs or understanding.

How It Works

Picture this as a hull-checking explorer:

• Step 1: Initialize hull with all points.
• Step 2: For each triplet, check if other points lie outside.
• Step 3: Keep points forming convex boundary.
• Step 4: Return hull vertices.

It’s like a trial-and-error fence maker!

Step-by-Step Example

Example: trees = [(1,1),(2,2),(2,0)]

• Step 1: Consider all points.
• Step 2: Check triangles:
• (1,1)-(2,2)-(2,0): All points on or inside, keep.
• Step 3: Result: [(1,1), (2,2), (2,0)] (simplified example).
• Result: [(1,1), (2,2), (2,0)].

Code for Brute-Force Approach

from typing import List, Tuple

class Solution:
    def outerTrees(self, trees: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
        def cross(p1, p2, p):
            return (p2[0] - p1[0]) * (p[1] - p1[1]) - (p2[1] - p1[1]) * (p[0] - p1[0])

        n = len(trees)
        hull = set()
        for i in range(n):
            for j in range(i + 1, n):
                p1, p2 = trees[i], trees[j]
                valid = True
                for k in range(n):
                    if k != i and k != j:
                        if cross(p1, p2, trees[k]) < 0:
                            valid = False
                            break
                if valid:
                    hull.add(p1)
                    hull.add(p2)
        return list(hull)

• Line 7-17: Check each pair as potential hull edge, verify no points outside.
• Line 19: Return unique hull points.
• Time Complexity: O(n³)—triplet checks.
• Space Complexity: O(1)—minimal space (excluding output).

It’s a brute-force hull builder!

Comparing the Two Solutions

• Graham’s Scan (Best):
• Pros: O(n log n), O(n), fast and elegant.
• Cons: Requires sorting logic.
• Brute-Force (Alternative):
• Pros: O(n³), O(1), thorough.
• Cons: Impractical for large n.

Graham’s scan wins for efficiency!

Additional Examples and Edge Cases

• Single point: Itself.
• Collinear points: Line segment.
• Square: Four vertices.

Graham’s scan handles them all!

Complexity Recap

• Graham’s Scan: Time O(n log n), Space O(n).
• Brute-Force: Time O(n³), Space O(1).

Graham’s scan’s the speed champ!

Key Takeaways

• Graham’s Scan: Geometry finesse—learn at Python Basics!
• Brute-Force: Exhaustive check.
• Fences: Hulls are fun.
• Python: Scan or brute, your pick!

Final Thoughts: Erect That Fence!

LeetCode 587: Erect the Fence in Python is a geometric challenge. Graham’s scan for convex hull is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 23: Merge k Sorted Lists or LeetCode 146: LRU Cache for algorithmic variety. Ready to fence? Head to Solve LeetCode 587 on LeetCode and enclose those trees today!