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

|

936 Discussions

|

  • 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;
}

  • mo7ali47
     + 0 comments

    Don't know if this is optimized or not but this is my solution in C++

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

  • patrickgao2020
     + 0 comments

    Here is my Python solution!

    def flatlandSpaceStations(n, c):
    c = sorted(c)
    distances = []
    if n == 1:
        return 0
    if len(c) == 1:
        return max(c[0], n - c[0] - 1)
    for city in range(len(c)):
        print(city)
        if city == 0:
            distances.append(c[city])
        elif city == len(c) - 1:
            distances.append(n - c[city] - 1)
            break
        distances.append(abs(c[city] - c[city + 1]) // 2)
    return max(distances)

  • keniblank
     + 1 comment

    Managed to write this in python, it works but is not optimised:

    def flatlandSpaceStations(n, c):
    max_distance = 0

    for i in range(n):
        new_dist = []
        for j in c:
            new_dist.append(abs(i - j))
        max_distance = max(min(new_dist), max_distance)

    return max_distance

  • keniblank
     + 0 comments

    SAD:

    No rust option T_T