I tried the below solution which seemed to pass all the test cases. This solution sorts the input array and has a time complexity of O(nlog(n)). The algorithm used is somewhat related to the two-pointer algorithm.

static int flatlandSpaceStations(int n, int[] c) {

    if(c.length == n)
        return 0;

    int maxDist = Integer.MIN_VALUE;

    if(c.length == 1){
        for(int i=0; i < n; i++){
            maxDist = Math.max(calculateDistance(i, c[0]), maxDist);
        }    
    }else{
        int left = 0;
        int right = 1;
        int leftDist = 0;
        int rightDist = 0;
        Arrays.sort(c);
        for(int i=0; i < n; i++){
            leftDist = calculateDistance(i, c[left]);
            rightDist = calculateDistance(i, c[right]);

            if(leftDist > rightDist){
                maxDist = Math.max(rightDist, maxDist);
                if(right < c.length -1){
                    left++;
                    right++;    
                }

            }else{
                maxDist = Math.max(leftDist, maxDist);
            }
        }
    }

    return maxDist;


}