# HackerRank 'Flatland Space Station' Solution

Martin Kysel · August 4, 2016

##### Short Problem Definition:

For each city, determine its distance to the nearest space station and print the maximum of these distances.

Flatland Space Station

##### Complexity:

time complexity is `O(N)`

space complexity is `O(N)`

##### Execution:

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.

##### Solution:
``````# RUST

use std::io;
use std::cmp;

fn get_numbers() -> Vec<u32> {
let mut line = String::new();
line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()
}

fn find_distance(c: Vec<u32>, n: usize) -> u32 {
//println!("{:?}", c);
let mut solution = 0;
let mut distances = vec![n as u32; n];

let mut last_seen = 0;
let mut seen_one = false;
for i in 0..n {
if c[i] == 1 {
seen_one = true;
last_seen = 0;
} else {
last_seen += 1;
}
if seen_one {
distances[i] = last_seen;
}
}
//println!("{:?}", distances);

let mut last_seen = 0;
let mut seen_one = false;
for i in (0..n).rev() {
if c[i] == 1 {
seen_one = true;
last_seen = 0;
} else {
last_seen += 1;
}
solution = cmp::max(solution,
match seen_one {
true => cmp::min(last_seen, distances[i]),
false => distances[i],
}
);
//println!("{} {} {}", i, last_seen, solution);
}

solution
}

fn main() {
let line = get_numbers();
let n = line as usize;
let c = get_numbers();
let mut v = vec![0; n];
for station in c {
v[station as usize] = 1;
}
println!("{}", find_distance(v, n));
}

``````