Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Go

Solution: Erect the Fence

Explore how to solve the Erect the Fence problem by computing the convex hull of a set of points representing tree locations. Understand the use of the Monotone Chain algorithm to form the smallest convex polygon that encloses all the points, ensuring an efficient fence perimeter. This lesson covers sorting points, checking orientation with cross products, building upper and lower hulls, and combining them to identify the boundary trees.

We'll cover the following...

Statement

You are given an array of points, trees, where trees[i] = [xᵢ, yᵢ] represents the location of a tree on a 2D plane. Your goal is to enclose all the trees using the shortest possible length of rope, forming a fence around the garden. A garden is considered well-fenced if every tree lies inside or on the boundary of the fence (i.e., the fence forms the convex hullThis is the smallest convex shape, completely encloses a set of points. of all the points).

Return the coordinates of the trees that lie exactly on the fence perimeter. You can return the answer in any order.

Constraints:

  • 1≤1 \leq trees.length ≤300\leq 300

  • trees[i].length == 22

  • 0≤0 \leq xi, yi ≤100 ...