Erect the fence

Link: https://leetcode.com/problems/erect-the-fence/

Solution:

DSA: convex hull, monotone chain, math, stack

Intuition
The core intuition is that the determinant of 3 points is positive if the 3rd point creates a left turn, and negative if it creates a right turn.

We can use this property to our advantage if we split up the fence into a top and a bottom! For the top, we want each point to be turning right, and for the bottom, each point to be turning left. This can be enforced mathematically by taking the determinant of 3 points.

The idea is to sort the points from left to right and keep a stack for both lower and upper segments. These stacks will be monotonic in the sense that the top 3 points on the stack MUST have a positive determinant or negative determinant for upper and lower stack respectively.

At the end of the left to right point traversal, the upper and lower stacks will contain all the vertices of the fence. Combine them in a set to eliminate duplicates (see image above)

Implementation

def fence(trees):
	def det(p1, p2, p3):
		x1, y1 = p1
		x2, y2 = p2
		x3, y3 = p3
		determinant = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)
		return determinant
		
	trees.sort()
	upper = []
	lower = []
	for tree in trees:
		#remove points that cause negative determinant
		#only positive is permitted for upper hull
		while len(upper) >= 2 and det(upper[-2], upper[-1], tree) < 0: 
			upper.pop()
			
		#remove points that cause positive determinant
		#only negative is permitted for lower hull
		while len(lower) >= 2 and det(lower[-2], lower[-1], tree) > 0:
			lower.pop()
		upper.append(tree)
		lower.append(tree)
		
	return list(set(lower+upper)) #there will be duplicates, see image above

Visual

review
hard