Erect the Fence - Practice Coding Problems

Erect the Fence - Problem

You are tasked with fencing a garden containing various trees using the minimum length of rope possible. Given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden, you need to find the convex hull - the smallest perimeter that encloses all trees.

The fence should form a convex polygon that contains or touches every tree. Trees that lie exactly on the fence perimeter are part of the solution.

Goal: Return the coordinates of all trees that are located exactly on the fence perimeter.

Input: Array of 2D coordinates representing tree positions

Output: Array of coordinates that form the convex hull boundary

Note: You may return the coordinates in any order.

Input & Output

example_1.py — Basic Square Garden

$ Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]

› Output: [[1,1],[2,0],[3,3],[4,2],[2,4]]

💡 Note: The fence forms a pentagon that encloses all trees. The points [1,1], [2,0], [4,2], [3,3], and [2,4] form the convex hull boundary.

example_2.py — Collinear Points

$ Input: trees = [[1,2],[2,2],[4,2]]

› Output: [[4,2],[2,2],[1,2]]

💡 Note: All three points lie on the same horizontal line, so they all must be included in the fence perimeter since they form the convex hull.

example_3.py — Single Point

$ Input: trees = [[0,0]]

› Output: [[0,0]]

💡 Note: With only one tree, the fence is just that single point - trivial convex hull case.

Constraints

1 ≤ trees.length ≤ 3000
trees[i].length == 2
0 ≤ x_i, y_i ≤ 100
All the given positions are unique.

Visualization

Tap to expand

Understanding the Visualization

Identify Start Point

Find the bottom-most point (lowest y-coordinate, leftmost if tie) as our anchor point

Sort by Polar Angle

Sort all other points by the angle they make with the start point, creating a radial sweep

Graham Scan

Process points in order, using a stack to maintain only the convex boundary points

Handle Collinear Points

Include all points that lie exactly on the boundary edges of the convex hull

Key Takeaway

🎯 Key Insight: The convex hull is like a rubber band stretched around all points - Graham's scan efficiently finds this boundary using polar angle sorting and cross products to detect turns.

Asked in

G Google 45 a Amazon 32 f Meta 28 ⊞ Microsoft 22

The optimal solution uses Graham's Scan algorithm which sorts points by polar angle and uses a stack to build the convex hull in O(n log n) time. The key insight is using cross products to determine if three consecutive points make a left turn (convex) or right turn (concave), allowing us to eliminate interior points efficiently.

Common Approaches

Approach	Time	Space	Notes
✓ Graham Scan Algorithm	O(n log n)	O(n)	Sort points by angle, then use stack to maintain convex hull with two-pointer technique
Brute Force (Check All Combinations)	O(2^n * n^3)	O(n)	Check every possible subset of points to see if they form a valid convex hull

Graham Scan Algorithm — Algorithm Steps

Find the bottommost point (lowest y-coordinate, leftmost if tie)
Sort all other points by polar angle with respect to the start point
Use a stack to process points in order
For each point, pop from stack while making right turns (concave)
Add current point to stack
Handle collinear points on the hull boundary

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Start Point

Identify the bottom-most (and leftmost in case of tie) point as the starting point

Sort by Angle

Sort all other points by polar angle with respect to the start point

Graham Scan

Use a stack to process points, removing those that create right turns (concave angles)

Handle Collinear

Add back any collinear points that lie on the hull boundary

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int x, y;
} Point;

long long cross(Point O, Point A, Point B) {
    return (long long)(A.x - O.x) * (B.y - O.y) - (long long)(A.y - O.y) * (B.x - O.x);
}

long long distance(Point p1, Point p2) {
    long long dx = p1.x - p2.x;
    long long dy = p1.y - p2.y;
    return dx * dx + dy * dy;
}

bool pointEqual(Point a, Point b) {
    return a.x == b.x && a.y == b.y;
}

Point start;

int compareByAngle(const void* a, const void* b) {
    Point* pa = (Point*)a;
    Point* pb = (Point*)b;
    
    if (pointEqual(*pa, start)) return -1;
    if (pointEqual(*pb, start)) return 1;
    
    long long crossProd = cross(start, *pa, *pb);
    if (crossProd == 0) {
        long long distA = distance(start, *pa);
        long long distB = distance(start, *pb);
        return (distA < distB) ? -1 : (distA > distB) ? 1 : 0;
    }
    return (crossProd > 0) ? -1 : 1;
}

int** outerTrees(int** trees, int treesSize, int* treesColSize, int* returnSize, int** returnColumnSizes) {
    if (treesSize <= 1) {
        *returnSize = treesSize;
        *returnColumnSizes = malloc(treesSize * sizeof(int));
        int** result = malloc(treesSize * sizeof(int*));
        
        for (int i = 0; i < treesSize; i++) {
            (*returnColumnSizes)[i] = 2;
            result[i] = malloc(2 * sizeof(int));
            result[i][0] = trees[i][0];
            result[i][1] = trees[i][1];
        }
        return result;
    }
    
    Point* points = malloc(treesSize * sizeof(Point));
    for (int i = 0; i < treesSize; i++) {
        points[i].x = trees[i][0];
        points[i].y = trees[i][1];
    }
    
    // Find bottom-most point
    start = points[0];
    for (int i = 1; i < treesSize; i++) {
        if (points[i].y < start.y || (points[i].y == start.y && points[i].x < start.x)) {
            start = points[i];
        }
    }
    
    // Sort by polar angle
    qsort(points, treesSize, sizeof(Point), compareByAngle);
    
    // Handle collinear points at the end
    int i = treesSize - 1;
    while (i > 0 && cross(start, points[i], points[treesSize - 1]) == 0) {
        i--;
    }
    
    // Reverse collinear points
    for (int left = i + 1, right = treesSize - 1; left < right; left++, right--) {
        Point temp = points[left];
        points[left] = points[right];
        points[right] = temp;
    }
    
    // Graham scan
    Point* hull = malloc(treesSize * sizeof(Point));
    int hullSize = 0;
    
    for (int j = 0; j < treesSize; j++) {
        while (hullSize >= 2 && cross(hull[hullSize - 2], hull[hullSize - 1], points[j]) < 0) {
            hullSize--;
        }
        hull[hullSize++] = points[j];
    }
    
    // Convert back to result format
    *returnSize = hullSize;
    *returnColumnSizes = malloc(hullSize * sizeof(int));
    int** result = malloc(hullSize * sizeof(int*));
    
    for (int j = 0; j < hullSize; j++) {
        (*returnColumnSizes)[j] = 2;
        result[j] = malloc(2 * sizeof(int));
        result[j][0] = hull[j].x;
        result[j][1] = hull[j].y;
    }
    
    free(points);
    free(hull);
    return result;
}

int main() {
    int trees[][2] = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
    int* treePtrs[6];
    for (int i = 0; i < 6; i++) treePtrs[i] = trees[i];
    
    int returnSize;
    int* returnColumnSizes;
    int** result = outerTrees(treePtrs, 6, NULL, &returnSize, &returnColumnSizes);
    
    printf("Hull points: ");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d] ", result[i][0], result[i][1]);
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n log n) for sorting points by polar angle, plus O(n) for the scanning phase

⚡ Linearithmic

Space Complexity

O(n)

O(n) space for the stack and sorted points array

⚡ Linearithmic Space

24.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Graham Scan Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler