Erect the Fence

This page explains Java solution to problem Erect the Fence using Graham Scan algorithm.

Problem Statement

There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.

Example 1:

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

Example 2:

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

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class ErectTheFence {
    public int[][] outerTrees(int[][] points) {
        if(points.length <= 1) return points;

        final int[] p = bottomLeft(points);
        Arrays.sort(points, new Comparator<int[]>(){
            public int compare(int[] q, int[] r) {
                int pq_qr = crossProduct(p, q, r);
                int pr_rq = crossProduct(p, r, q);
                int diff = Integer.compare(pq_qr, pr_rq);
                if(diff == 0) return Integer.compare(distance(p, q), distance(p, r));
                else return diff;
            }
        });

        //When you come back to complete the loop, points which are closer to starting point should come first
        int i = points.length - 1;
        while(i >= 0 && crossProduct(p, points[i], points[points.length - 1]) == 0) i--;

        int lo = i + 1;
        int hi = points.length - 1;
        while(lo < hi) {
            int[] temp = points[lo];
            points[lo] = points[hi];
            points[hi] = temp;
            lo++;
            hi--;
        }

        Stack<int[]> st = new Stack<>();
        st.push(points[0]);
        st.push(points[1]);
        for(int j = 2; j < points.length; j++) {
            int[] top = st.pop();
            while(crossProduct(st.peek(), top, points[j]) > 0) top = st.pop();
            st.push(top);
            st.push(points[j]);
        }
        return st.toArray(new int[st.size()][]);
    }

    private int distance(int[] p, int[] q) {
        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
    }

    private int crossProduct(int[] p, int[] q, int[] r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    private int[] bottomLeft(int[][] points) {
        int[] res = points[0];
        for(int i = 1; i < points.length; i++) {
            if(res[1] > points[i][1]) {
                res = points[i];
            }
        }
        return res;
    }
}

Time Complexity

O(N * log N) Where
N is total number of tress points in an input array

Space Complexity

O(N) Where
N is total number of tress points in an input array