##### Short Problem Definition:

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

##### Link

##### 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();

io::stdin().read_line(&mut line).ok().expect("Failed to read line");

line.split_whitespace().map(|s| s.parse::<u32>().unwrap()).collect()

}

fn find_distance(c: Vec<u32>, n: usize) -> u32 {

let mut solution = 0;

let mut distances = vec![n as u32; n];

// first pass

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;

}

}

// second pass

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],

}

);

}

solution

}

fn main() {

let line = get_numbers();

let n = line[0] 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));

}

[/rust]

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.