We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Flatland Space Stations
  5. Discussions

Flatland Space Stations

Sort by

recency

|

943 Discussions

|

  • spriyamalar
     + 0 comments
    static int flatlandSpaceStations(int numofcities, int[] spacestationcities) {
    int maxdistance = 0;
    for(int i=0; i<numofcities;i++) {
        int mindistance = Integer.MAX_VALUE;
        boolean hasstation=false;
        for(int j=0;j<spacestationcities.length; j++) {
            if(i==spacestationcities[j]) {
                hasstation = true;
                break;
            }
            if(i != spacestationcities[j]) {
                if(Math.abs(i-spacestationcities[j]) < mindistance) {
                    mindistance = Math.abs(i-spacestationcities[j]);
                }
            }
        }
        if(mindistance > maxdistance && !hasstation) {
            maxdistance = mindistance;
        }
    }
    return maxdistance;
}

  • yashdeora98294
     + 0 comments

    Here is problem solution in Python, Java, C++, C and Javascript - https://programmingoneonone.com/hackerrank-flatland-space-stations-problem-solution.html

  • wendigo
     + 0 comments

    There is an error in the C stub for this. I am getting "Runtime error" in Test case 6 and 13 even if I immediately return 0 from the funciton.

  • shiaramoon
     + 0 comments
    from bisect import bisect

def flatlandSpaceStations(n, c):
    c.sort()
    max_dist = 0
    for city in range(n):
        indx = min(bisect(c, city), len(c) - 1)
        city_dist = min(abs(c[indx] - city), abs(c[max(indx - 1, 0)] - city))
        max_dist = max(max_dist, city_dist)
    return max_dist

  • alban_tyrex
     + 0 comments

    Here is my easy c++ solution, you can watch the explanation here : https://youtu.be/k2pd5_9mseI

    int flatlandSpaceStations(int n, vector<int> c) {
    sort(c.begin(), c.end());
    int result = c[0];
    for(int i = 1; i < c.size(); i++){
        result = max(result, (c[i] - c[i-1]) / 2 );
    }
    result = max(result, n - 1 - c[c.size() - 1]);
    return result;
}

    This algorithm is actually O(Nlog(N)) because of the sorting, we can make it O(N) by using a counting sort since we know what the maximum element of our array will be. you will have to replace the line 

        sort(c.begin(), c.end());

    with this 

        c = countingtSort(c, n);

    And add this sort function in your editor 

    vector<int> countingtSort(vector<int>c, int n) {
    vector<int> arr(n, 0), result;
    for(auto el: c) arr[el] = 1;
    for(int i = 0; i < n; i++) if(arr[i]) result.push_back(i);
    return result;
}