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

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