Maximum distance between space stations HackerRank

Question

I am just working on Flatland Space Stations problem, and it is not seeming to be a tough question, but my algorithm lags in some aspects, since it solves majority of the test cases but fails for some. Which is causing me not to move forward.

The cause of the failure is timeout only, no wrong output.

My Algo:

1. To loop through the number of cities
2. Loop through the cities which has the space stations
3. Store the minimum distance in the array or dict for that particular city
4. Find out the maximum distance stores in the array of difference between n cities

I have written two codes based upon the following Algo:

1. With the use of Dictionary: Time out for three cases

def flatlandSpaceStations(n, c):
    # n is the number of cities
    # c is the array of space station exists in the city(s)
    cityDiff = {}
    maxDiff = 0
    if n == len(c):
        return 0
    else:
        for i in range(n):
            lst = []
            for j in c:
                lst.append(abs(i-j))
                cityDiff[i] = min(lst)

    for key, value in cityDiff.items():
        if value > maxDiff: maxDiff = value

    return maxDiff

2. Using lists in Python: Failed two cases in Timeout only

def flatlandSpaceStations(n, c):
    # n is the number of cities
    # c is the array of space station exists in the city(s)
    maxDiff = []
    if n == len(c):
        return 0
    else:
        for i in range(n):
            minDis = []
            for j in c:
                minDis.append(abs(i-j))
            maxDiff.append(min(minDis))
    return max(maxDiff)

I want to find some optimum solution, which I can understand. The above programs have a very bad time complexity I know, but this is only solution I can think of right now. Any help would be appreciated.

As per vnp's suggestion, I have made another attempt, and made the solution optimized, but it is not working out for the Two test cases due to timeout issue.

Solution \$O(n^2)\$:

def flatlandSpaceStations(n, c):
    # n is the number of cities
    # c is the array of space station exists in the city(s)
    maxDiff = []
    if n == len(c):
        return 0
    else:
        for i in range(n):
            minVal = float('inf')
            for j in c:
                if abs(i-j) < minVal: minVal = abs(i-j)
            maxDiff.append(minVal)
    return max(maxDiff)

I am attaching one of the two time out failure test case here for more insight.

TEST CASE

Answer 1

builting min

minVal = float('inf')
for j in c:
    if abs(i-j) < minVal: minVal = abs(i-j)

can be rewritten using min: min(abs(i-j) for j in c).

Apart from that, placing the code on the same line as the check looks very unreadable to me.

There is also no need to keep the values in a list,

for i in range(n):
    lst = []
    for j in c:
        lst.append(abs(i-j))
        cityDiff[i] = min(lst)

can be

max(min(abs(i - j) for j in c) for i in range(n))

variable names

i and j are useful variable names as counters. Here you use them as citie and space station. The same goes for c, which are the space stations.Then call em like that:

max(
    min(abs(space_station - city) for space_station in space_stations)
    for city in range(n)
)

space stations

A first improvement I would suggest if the city you want to check is a space station or not. In your naive algorithm you do m x n checks. This will reduce it by m x m. If you use a set for the space stations, this inclusion check will be quick.

space_station_set = set(space_stations)
max(
    min(abs(space_station - city) for space_station in space_stations)
    for city in range(n) if city not in space_station_set 
)

sorting space stations

If you sort the space stations, you can use this fact.

space_stations = [1, 4, 7]
space_stations_sorted = (
    [float("-inf")] + sorted(space_stations) + [float("inf")]
)
space_station_pairs = (
    (space_stations_sorted[i], space_stations_sorted[i + 1])
    for i in range(len(space_stations) + 1)
)

This will generate pairs of adjacent space stations. I added the infs to take care of the edges

list(space_station_pairs)

[(-inf, 1), (1, 4), (4, 7), (7, inf)]

Then you loop through the cities like this:

one, two = next(space_station_pairs)
distance_max = float("-inf")
for city in range(n):
    if city == two:
        one, two = next(space_station_pairs)
        continue
    distance = min((city-one), (two-city))
    distance_max = max(distance, distance_max)

This way you only loop once through the cities and twice through the space stations, so you reduced the complexity to O(n).

looping only over the space stations:

The furthest city will always be either in the middle between 2 space stations or at the edges of the map. You can use this fact to

space_stations_sorted = sorted(space_stations)
distance_max = max(
    (two - one) // 2 for one, two in pairwise(space_stations_sorted)
)
distance_max_total = max(
    distance_max, space_stations_sorted[0], n - space_stations_sorted[-1] - 1
)

this loops only once over the space stations, and leaves the cities untouched.