on
Solving Flatland Space Stations on HackerRank: Golang vs Python
Solving programming puzzles is a good way to get reminded of software engineering fundamentals like algorithms and data structures. For this reason, I try to pick up a programming puzzle on HackerRank or leetcode from time to time. Lately, I stumbled upon a problem named Flatland Space Stations on HackerRank: https://www.hackerrank.com/challenges/flatland-space-stations/problem. The puzzle is classified as easy, but it turned out to be tricky. As you know, HackerRank tests your solution with different input sizes/types because a good solution need also to have a reasonable running time and to work against corner cases. Working out an initial naive solution to the puzzle was easy, as expected. The solution worked for most of the inputs, but failed for the ones with large sizes (2 out of 20), so the feeling of glory was still not there. Finding the optimal solution was actually not easy, and this is the reason why I decided to share the story. Key learning: never underestimate a programming puzzle. Always be humble.
The problem overview:
To put it simple (more details are on HackerRank problem description):
You have a list of cities (a city is a number) which starts from 0 and increase by 1 until a certain maximum, for example: [0, 1, 2, 3, 4, 5]
Given another list of positive integers that denotes the cities that has a space station, for example [0, 5], you have to find out the maximum distance from any city to its nearest space station. In other words, the maximum of minimum distances.
Couple of details:
- the initial list of cities is not given as a list but rather as a number denoting the maximum. For the example above, n the number of cities is given as 6. Therefore we have to go from 0 to 5.
- The list size can go up to \(10^5\), or 100000.
The programming language choice:
I decided to use Python to solve this problem, simply because I have not written any Python in a while. I was aware that plain Python may not be the fastest when it comes to run time performance (a benchmark can be found here: https://sites.google.com/view/energy-efficiency-languages/results), but I thought that it would be good enough to solve this problem within the time bounds set by HackerRank:
HackerRank sets different limits for each language, because each language has different run time capabilities. For example, Python has an execution limit of 10 seconds while the C language has an execution limit 2 seconds.
The naive solution:
My initial approach was to go through all the cities calculating the distance from the current city to all the cities with a station and storing the minimum distance in a list. At the end, I go through the list of minimums to find the maximum.
# n is the cities, and is just an integer
# c is the list of cities with a station
def flatlandSpaceStations_old(n, c):
if n == len(c):
return 0
min_per_city = []
for i in range(n):
min_per_city.append(n)
for city_with_station in c:
if city_with_station == i:
min_per_city[i] = 0
break
else:
min_per_city[i] = min(min_per_city[i], abs(i - city_with_station))
return max(min_per_city)Although the solution above is not optimal and is using a brute force technique, it did work for most of the cases, except the cases 14 and 15 that have large input sizes:
- case 14: 99999 city, and 1000 city with stations.
- case 15: 99878 city, and 9000 city with stations.
The cases failed because the time limit was exceeded, and not because of a wrong result.
I tried the solution on my computer, and it took about 45 seconds for case 14 (4.5x more that the time limit) and about 5m19s for case 15 (32x more than the time limit). This is the output of the time command:
case 14:
real 0m45,086s
user 0m44,886s
sys 0m0,084s
case 15:
real 5m19,769s
user 5m18,379s
sys 0m0,788s
It looked like optimizations are needed. Assuming the size of the list with stations is k and the number of cities is n, the algorithm above has a complexity of \(O(k * n)\).
The optimized solution:
When thinking about the problem from a different angle, one could see that it is actually not necessary to go through the whole list of cities with stations. It is enough to find two cities only: the one before our current city and the one after it. This looked like a viable option to reduce the work of the initial algorithm, but it needs the list of cities of stations to be sorted. Python provides a built-in sort() function that uses the Timsort algorithm for its lists. The Timsort has complexity of \(O(n\log{}n)\) which is comparable to some of the fastest sort algorithm like quick sort. This would alleviate the burden of having also to implement the sort. Let’s take a look at the new implementation:
def flatlandSpaceStations(n, c):
if n == len(c):
return 0
min_per_city = []
c.sort()
total_cities_with_stations = len(c)
for i in range(n):
min_per_city.append(-1)
if i < c[0]:
min_per_city[i] = c[0] - i
continue
elif i > c[total_cities_with_stations - 1]:
min_per_city[i] = i - c[total_cities_with_stations - 1]
continue
for j in range(len(c)):
if i == c[j]:
min_per_city[i] = 0
break
if c[j] < i and j + 1 < len(c) and i < c[j+1]:
min_per_city[i] = min(abs(i - c[j+1]), abs(i - c[j]))
break
return max(min_per_city)When running the cases again, the new optimization did bring some improvements:
case 14:
real 0m12,035s
user 0m12,009s
sys 0m0,017s
case 15:
real 3m17,224s
user 3m12,022s
sys 0m0,719s
The case 14 got the ok from HackerRank (meaning that on their infrastructure it ran in less than 10s). The optimization was still not enough for case 15 as you can see. I decided to do another kind of optimization: switching the programming language.
Switching to Golang:
As we have seen before, just by switching from a language to another, one can reduce the running time because each language runs and compiles differently. I decided to rewrite the optimized solution above in Golang, and guess what ? It worked for all cases.
func flatlandSpaceStations(n int32, c []int32) int32 {
totalCities := len(c)
if int(n) == totalCities {
return 0
}
sort.SliceStable(c, func(i, j int) bool { return c[i] < c[j]})
minPerCity := make([]int32, n)
for i := 0; i < int(n); i++ {
minPerCity[i] = 0
if int32(i) < c[0] {
minPerCity[i] = c[0] - int32(i)
continue
} else if int32(i) > c[totalCities - 1] {
minPerCity[i] = int32(i) - c[totalCities - 1]
continue
}
for j, city_with_station := range c {
if city_with_station == int32(i) {
minPerCity[i] = 0
break
} else if int32(i) > city_with_station && j + 1 < totalCities && int32(i) < c[j+1] {
distance1 := int32(i) - city_with_station
distance2 := c[j+1] - int32(i)
if distance1 < distance2 {
minPerCity[i] = distance1
} else {
minPerCity[i] = distance2
}
break
}
}
}
var maxDistance int32
for _, distance := range minPerCity {
if distance > maxDistance {
maxDistance = distance
}
}
return maxDistance
}Community solutions in Python:
I skimmed through the community solutions posted in the discussions page, and I found out some solutions to the problem in the order of O(n):
Solution 1:
def flatlandSpaceStations(n, c):
if n < 2:
return 0
c.sort()
return max([((c[i+1] -c[i])//2) for i in range(len(c)-1)] + [c[0], n-1-c[-1]])Solution 2:
def flatlandSpaceStations(n, c):
maxd=[]
for i in range(n):
cityd = min([abs(c1-i) for c1 in c])
maxd.append(cityd)
return max(maxd)