3
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Hint: sort the list of space stations. Then find the maximum distance between consecutive stations in the sorted list. \$\endgroup\$ – vnp Apr 23 at 21:18
  • \$\begingroup\$ Hey @vnp, I have tried an optimum solution with your suggestion, but I guess this doesn't work out for me. I don't know but Python is seeming a bit slow for my solution. I am adding one more attempt in my question please see \$\endgroup\$ – Alok Apr 23 at 22:13
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hey Maarten, thank you for the detailed explanation, but while testing this code max(min(abs(i - j) for j in c) for i in range(n)) gives the error: ValueError: min() arg is an empty sequence. I have tried using wrapping into list(). Always same result \$\endgroup\$ – Alok Apr 24 at 9:42
  • \$\begingroup\$ only if c is empty \$\endgroup\$ – Maarten Fabré Apr 24 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.