HackerRank 'Flatland Space Station' Solution | MartinKysel.com
This is a two pass algorithm. First, measure the distance to the last station on the left. And on the second pass measure the distance to the nearest station on the right. Pick the minimum of both values. Remember that the first and last position are not necessarily stations.
https://github.com/mbobesic/algorithms-playground/blob/master/hacker_rank/FlatLandSpaceStation.java
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] stations = new boolean[n];
for (int i = 0; i < m; i++) {
int station = in.nextInt();
stations[station] = true;
}
int[] left = new int[n];
int[] right = new int[n];
if(!stations[0]){
left[0] = 10000000;
}
for (int i = 1; i < left.length; i++) {
if(stations[i]){
left[i]=0;
continue;
}
left[i]=left[i-1]+1;
}
if(!stations[n-1]){
right[n-1] = 10000000;
}
for(int i = right.length - 2; i>=0; i--){
if(stations[i]){
right[i]=0;
continue;
}
right[i]= right[i+1] +1;
}
int max = 0;
for(int i =0;i<n;i++){
int current = Math.min(left[i], right[i]);
if (current > max){
max = current;
}
}
if(max > n) max=n;
System.out.println(max);
}
Read full article from HackerRank 'Flatland Space Station' Solution | MartinKysel.com
Flatland is a country with cities, of which have space stations. Each city, , is numbered with a distinct index from to , and each city is connected to city by a bidirectional road that is in length.
For example, if and cities and have space stations, then Flatland looks like this:
For each city, determine its distance to the nearest space station and print the maximum of these distances.
Input Format
The first line consists of two space-separated integers, and .
The second line contains space-separated integers describing the respective indices of each city having a space-station. These values are unordered and unique.
The second line contains space-separated integers describing the respective indices of each city having a space-station. These values are unordered and unique.
Constraints
- It is guaranteed that there will be at least city with a space station, and no city has more than one.
Output Format
Print an integer denoting the maximum distance that an astronaut in a Flatland city would need to travel to reach the nearest space station.
Sample Input 0
5 2
0 4
Sample Output 0
2
Explanation 0
This sample corresponds to the example given in the problem statement above. The distance to the nearest space station for each city is listed below:
- has distance , as it contains a space station.
- has distance to the space station in .
- has distance to the space stations in and .
- has distance to the space station in .
- has distance , as it contains a space station.
We then take , and print as our answer.
Sample Input 1
6 6
0 1 2 4 3 5
Sample Output 1
0
Explanation 1
In this sample, so every city has space station and we print as our answer.
This is a two pass algorithm. First, measure the distance to the last station on the left. And on the second pass measure the distance to the nearest station on the right. Pick the minimum of both values. Remember that the first and last position are not necessarily stations.
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
boolean[] stations = new boolean[n];
for (int i = 0; i < m; i++) {
int station = in.nextInt();
stations[station] = true;
}
int[] left = new int[n];
int[] right = new int[n];
if(!stations[0]){
left[0] = 10000000;
}
for (int i = 1; i < left.length; i++) {
if(stations[i]){
left[i]=0;
continue;
}
left[i]=left[i-1]+1;
}
if(!stations[n-1]){
right[n-1] = 10000000;
}
for(int i = right.length - 2; i>=0; i--){
if(stations[i]){
right[i]=0;
continue;
}
right[i]= right[i+1] +1;
}
int max = 0;
for(int i =0;i<n;i++){
int current = Math.min(left[i], right[i]);
if (current > max){
max = current;
}
}
if(max > n) max=n;
System.out.println(max);
}
Read full article from HackerRank 'Flatland Space Station' Solution | MartinKysel.com
