[Java] Find minimum highest calculated value in ordered collection

I was searching from some problems online and found a video that poses an interesting one.

We handle Apartment objects that look like this:

Apartment:{

  "gym": false,

  "school": true,

  "store": false

} 

The values true/false indicate that the specific facility is present (true) or not (false) at that apartment. If a facility is present at an apartment, the travel distance from the apartment to the facility is 0.

If a facility is not present at an apartment, it might be present at a farther apartment. In that case, the travel distance is equal to the number of apartments you must cross to reach that facility.

An array of Apartments is given in input as well as a collection of facilities that are relevant for us, for example:

["gym","school"]

The goal of the exercise is to find which apartment minimizes the maximum travel distance to any relevant facility (return its index in the input array).

If an apartment has two facilities at distances N and M, the maximum travel distance is the max(N,M), NOT the sum.

If multiple apartments satisfy the requirement, return any of them.

I also added an additional requirement, if NO apartment satisfies the requirements (eg a relevant facility is NOT present at any apartment), return -1.

 

Assuming we have N apartments and M facilities, the first approach that comes to mind is to calculate for each apartment and set of facilities (NxM) the shortest distance to all relevant facilities. By scanning the full list of apartments and facilities (NxM) once for each given apartment (N), we get our result in O(N² x M) time.

Consider this input (missing facilities are set to false):

apartments:[

0: {"gym":true},

1: {"gym":true,

"school":true},

2: {"store":true},

] 

facilities:["gym","school","store"]

We have the following results:

0: gym=0, school=1, store=2, max distance is 2

1: gym=0, school=0, store=1, max distance is 1

2: gym=1, school=1, store=0, max distance is 1

We have two best apartment, 1 and 2 since for both the max distance is 1.

We can notice that to answer this question we MUST do at least NxM work since we need to look at all given apartments and relevant facilities before we can formulate the final result, therefore there could be a way of finding a solution in about O(NxM) time. By using additional O(NxM) space we can achieve that.

We create an NxM matrix tracking for each apartment the minimum distance from each relevant facility. We initialize this to Integer.MAX_INT.

Since our apartments are given in input as an array, we know they have a strict ordering in place. A facility that is missing at a specific index, might be found at a previous or next index, therefore the distance of the missing facility for a particular place is equal to the best distance from an adjacent place + 1.

After the first pass on our sample input the matrix would look like this (g=gym, k=school, s=store):

   G    K      S

0  0    MAX    MAX

1  0    0      MAX

2  1    1      0

In order for this information to be complete however, we must scan our apartments twice since a missing facility might be present AFTER our apartment OR the best distance might be found walking left to right or right to left.

In our first pass we basically set all 0-distances and can perform a partial calculation for items that are AFTER one that has a 0-distance.

At the end of this processing, the only apartment for which we have full knowledge is the last, since it has no successor and we processed all predecessors. We can therefore initialize our partial result saying this is the best apartment, and calculate the maximum distance it has from any relevant facility.

We now walk backwards from the second to last apartment and try to update our knowledge based on the new information we have. For each best value we have calculated, we compare it to the distance coming from the next item in the array + 1. This means we update our knowledge if:

- we didn't know where the facility was and have now found one that was AFTER us

- we knew about a facility but have now found that AFTER us there is a closer one

After this second pass, our matrix looks like this:

   G    K      S

0  0    1      2

1  0    0      1

2  1    1      0

And each step, when we finished processing all relevant facilities for an apartment, we can calculate what is the maximum distance we would travel from there and compare this value with our current best to update it if we find a better apartment that has a lower maximum distance.

In our example, we start with best = 2, maximum distance = 1

After finishing processing apartment 1 we see its maximum distance is 1, which is not better than our current, so we move on.

After finishing processing apartment 0 we see its maximum distance is 2, which is not better than our current, so we move on.

We can finally return apartment 2 as the answer. Notice that there are multiple apartments which fit the optimal solution, but as specified in the requirements, we simply need to return any of those.

You can check my implementation of apartmentWithMinimumFarthestDistanceFromFacilities on my Gist alongside some test cases in ApartmentWithMinimumFarthestDistanceFromFacilitiesJTests. It also uses additional classes to represent the Apartment and the Facility.