Problem statement

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

Solution 1

What we actually need to find is convex hull of given points. There are different ways how to do it: the simplest is Jarvis Algorithm with O(mn) complexity, where n is total number of points and m is number of points in convex hull. I prefer Graham scan, which use the idea of angle sweep. We need to choose the most left point as starting point. Then we need to sort points with respect to its angle, and if we have the same angle, then we need to sort points by (-p[1], p[0]) - in this way we can be sure that we traverse points in correct order, also we need to make sure that for the first points if they have the same angle, we need to sort them in increasing order by distance and for the last one in the decreasing order by distance. I did not found elegant way to code this, so what I do is just check last points and look for points lying on the same line and then sort them in correct way. Then we keep stack with points and check orientation of triangle, using cross function and if orientation is negative, then we pop the point ans[-2]. Please go to wikipedia for more details.

Note, that in this problem our convex hull contains point on border, if we do not need it we need to use cross(*ans[-3:]) <= 0 instead and points.sort(key=lambda p: (atan2(p[1]-start[1], p[0]-start[0]), p[0])), I am not 100 sure though, I did not test it a lot.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

class Solution:
    def outerTrees(self, points):
        def cross(p1, p2, p3):
            return (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])

        start = min(points)
        points.pop(points.index(start))
        points.sort(key=lambda p: (atan2(p[1]-start[1], p[0]-start[0]), -p[1], p[0]))
        
        last = len(points) - 1
        while last > 0 and cross(start, points[-1], points[last - 1]) == 0:
            last -= 1
            
        points[last:] = sorted(points[last:], key = lambda p: (-p[0]))

        ans = [start]
        for p in points:
            ans.append(p)
            while len(ans) > 2 and cross(*ans[-3:]) < 0:
                ans.pop(-2)
        return ans

Solution 2

When I solved this problem, I was not fully satisfied, because of atan2 function: given problem constraints, all absolute values <= 100 it will work fine. But if we have bigger coordinates, it can wrong incorrectly, because 3 points can lie almost on the same line and we can not be sure if it is convex or concave. To compare points we need to first check the quater it is inside and then if they are in the same quater, check p1[1]/p1[0] > p2[1]/p2[0], which can be written without divisions. Function compare will compare points, usch that angle lies in (-180, 180) without rounding errors.

Now, we use the similar logic as in solution 1, but we need to normalize points, that is subtract start from all of them, then perfrom sort and in the end add start back.

Complexity

It is still O(n log n) for time and O(n) for space.

Code

class Solution:
    def outerTrees(self, points):
        def quater(p):
            x, y = p
            if x >= 0 and y >= 0: return 2
            if x < 0 and y >= 0: return 1
            if x < 0 and y < 0: return 4
            if x >= 0 and y < 0: return 3

        def compare(p1, p2):
            if quater(p1) == quater(p2):
                t1 = p1[1]*p2[0] - p2[1]*p1[0]
                return  1 - 2*int((-p1[1], p1[0]) < (-p2[1], p2[0])) if t1 == 0 else 1 if t1 > 0 else -1
            else:
                return 1 if quater(p1) < quater(p2) else -1
        
        def cross(p1, p2, p3):
            return (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])

        start = min(points)
        points.pop(points.index(start))
        points = [[x - start[0], y - start[1]] for x, y in points]
        points.sort(key = cmp_to_key(compare))
        
        last = len(points) - 1
        while last > 0 and cross([0, 0], points[-1], points[last - 1]) == 0:
            last -= 1
            
        points[last:] = sorted(points[last:], key = lambda p: (-p[0]))

        ans = [[0, 0]]
        for p in points:
            ans.append(p)
            while len(ans) > 2 and cross(*ans[-3:]) < 0:
                ans.pop(-2)
        
        return [[x + start[0], y + start[1]] for x, y in ans]