Flatland Space Stations

See the original problem on HackerRank.

Solutions

The problem can be solved linearly.

Assume \(arr[i]=1\) if the \(i^th\) city has a space station, \(0\) otherwise. Now calculate \(c[i]\) which denotes the distance to the nearest space station on the left. if \(arr[i]=1\), then \(c[i]=0\), otherwise \(c[i]=c[i-1]+1\).

Now calculate the distance to the nearest space station to the right using the same technique. The minimum of these values is the distance to the nearest space station. Among all these values, print the maximum one.

Here is an implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int n, m;
cin >> n >> m;
vector<int> c(n, numeric_limits<int>::max());
int currC;
while (m--)
{
    cin >> currC;
    c[currC] = 0;
}    
auto currCount = -1;
for (auto i=0u; i<n; ++i)
{
    if (c[i] == 0)
        currCount = 1;
    else if (currCount != -1)
    {
        c[i]=currCount++;
    }
}    
currCount = -1;
for (auto i=n-1; i>=0; --i)
{
    if (c[i] == 0)
        currCount = 1;
    else if (currCount != -1)
    {
        c[i]=min(currCount++, c[i]);
    }
}    
cout << *max_element(begin(c), end(c));

The following C++ solution makes use of the prefix sum pattern:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int n, m;
cin >> n >> m;
vector<int> c(n, numeric_limits<int>::max());
int currC;
while (m--)
{
    cin >> currC;
    c[currC] = 0;
}   
auto updateFn = [](int currVal, int r){
	return min(r, currVal<numeric_limits<int>::max() ? currVal + 1 : currVal);
};
partial_sum(begin(c), end(c), begin(c), updateFn);
partial_sum(rbegin(c), rend(c), rbegin(c), updateFn);
cout << *max_element(begin(c), end(c));
We've worked on this challenge in these gyms: modena 
comments powered by Disqus