Abstract / Summary

Given tree house coordinates, find the smallest perimeter fence enclosing all houses without cutting any trees.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Geometry
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation provides a method to return all points that lie on the boundary of the smallest fence enclosing a set of trees. It computes a convex hull using the Gift Wrapping (Jarvis March) algorithm and then augments the hull with any points that are colinear with hull edges, ensuring that every tree touching the fence is included.

Core Data Representation

A small point structure stores the integer coordinates of each tree. The input, a vector of integer pairs, is transformed into a vector of point objects so that geometric calculations can be performed directly on the coordinates.

struct point
{
    int x, y;
};

vector<point> all;
for (auto t : trees)
    all.push_back({ t[0], t[1] });

Selecting the Starting Vertex

The algorithm begins by locating the left-most tree, which serves as the initial hull vertex. When multiple trees share the same minimal x-coordinate, the code selects the later one in the scan, effectively treating equal x values as part of the colinear handling later on.

int leftmost = 0;
for (int i = 1; i < all.size(); i++)
    if (all[leftmost].x >= all[i].x)   // “equal” => including colinear
        leftmost = i;

Gift Wrapping Loop (Hull Construction)

Starting from the left-most point, the method iteratively chooses the next hull vertex by scanning all points and selecting the one that makes the most counter-clockwise turn relative to the current edge. The orientation test is performed by the dot function, which returns a signed area value. A negative result indicates that the candidate point lies to the right of the current direction, prompting an update of the next vertex.

vector<int> hull;
int current = leftmost;
do
{
    hull.push_back(current);

    int next = current + 1;
    next %= trees.size();

    for (int i = 0; i < trees.size(); i++)
        if (dot(all[current], all[i], all[next]) < 0)
            next = i;

    current = next;
} while (current != leftmost);

The loop terminates when the algorithm returns to the starting vertex, guaranteeing a closed polygon.

Incorporating Colinear Edge Points

After the minimal hull is obtained, a second pass walks each hull edge and checks every tree to see whether it lies exactly on that edge. The orientation test dot == 0 identifies colinear points, which are then appended to the hull list. This step ensures that trees lying on the fence but not selected as extreme vertices are still reported.

auto hsize = hull.size();
for (int j = 0; j < hsize; j++)
{
    for (int i = 0; i < all.size(); i++)
    {
        auto prev = j - 1;
        if (j == 0)
            prev = hsize - 1;

        if (dot(all[hull[prev]], all[i], all[hull[j]]) == 0)
            hull.push_back(i);
    }
}

Duplicate Elimination

Because colinear points may be added multiple times, the hull index list is sorted and then deduplicated using the standard unique algorithm. This step yields a clean set of unique indices representing all boundary trees.

sort(hull.begin(), hull.end());
auto last = unique(hull.begin(), hull.end());
hull.erase(last, hull.end());

Building the Result Vector

Finally, the unique indices are translated back into the required output format-pairs of integer coordinates-by iterating over the cleaned hull list.

vector<vector<int>> result;
for (auto h : hull)
    result.push_back({ all[h].x, all[h].y });
return result;

Edge Cases Addressed

When the input contains fewer than three trees, the method returns the original set directly, recognizing that a convex hull is undefined for such small collections. The left-most selection logic treats equal x-coordinates as a tie, allowing the later point to become the start, which dovetails with the later colinear inclusion pass. The colinear detection (dot == 0) captures points that lie exactly on hull edges, ensuring that trees forming a straight line or lying on a side of the polygon are not omitted. Duplicate tree coordinates are naturally collapsed during the final sorting and unique step, preventing redundant entries in the output.

Performance Optimizations Observed

The algorithm operates entirely with integer arithmetic, avoiding floating-point overhead and preserving exact orientation results. By reusing the all vector for both the initial conversion and subsequent geometric checks, the code minimizes additional memory allocations. The outer Gift Wrapping loop iterates only as many times as there are hull vertices, and each iteration scans the full point set, which is optimal for the chosen algorithmic approach. The secondary colinear pass leverages the already computed hull size to bound its outer loop, and the final deduplication uses sort followed by unique, both of which are highly tuned standard library operations. These choices collectively keep the runtime efficient for typical input sizes while maintaining clarity.

Imagine a big grassy field filled with many tall trees. Your goal is to build a long wooden fence that goes all the way around all of those trees so that every single tree is safely inside the enclosure. To do this, think about finding the tree that is furthest to the left side of the field. This special tree is definitely going to be part of your fence.

From that first tree, you look around at all the other trees and pick the one that makes your fence move in a nice wide turn. By always picking the next tree that keeps your fence stretching out as far as possible, you eventually travel in a big circle around everything. This creates a shape that connects all the trees on the very outside edge of the group.

Sometimes, a few trees might be standing in a perfectly straight line on the edge of your fence. Because you want to make sure every tree is touched by the fence, you check for those extra trees hiding on the flat parts of the lines. Once you have a list of every single spot where a tree touches the fence, you tidy up the list by removing any trees you accidentally counted twice. By the time you finish, every tree is either inside the fence or touching the wood, and you have a perfect boundary for the whole forest.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python					TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python				Go
	LeetcodeHelp	C++		Java		Python
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fpdjsns	C++
	JoshCrozier		JS
	linouk23					Python
	ruoru				Rust
	suxrobGM							C#
	vli02								C
	vthwang			Java
	wisdompeak	C++
	yuanliu666						Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
JoshCrozier	JavaScript
linouk23	Python
ruoru	Rust
suxrobGM	C#
vli02	C
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality