flatland_space_stations.py

# Source: https://www.hackerrank.com/challenges/flatland-space-stations/problem
# video: https://youtu.be/zCCz59gT9Rs

def flatlandSpaceStations(n, c):
    # c = cities with space stations is NOT ordered
    c.sort() # O(clogc)
    # consider very first city
    max_dist = c[0]
    
    # going left to right, assume midpoint distance for max
    for i in range(1, len(c)): # O(c)
        last_city = c[i-1]
        curr_city = c[i]
        mid_city_dist = (curr_city - last_city) // 2 # floor division
        max_dist = max(max_dist, mid_city_dist)
    
    # consider very last city
    last_city_dist = n - c[-1] - 1
    max_dist = max(max_dist, last_city_dist)
    return max_dist # Time complexity: O(clogc) + O(c) = O(clogc)