Algorithm to place a mailbox to minimize the total distance that the residents travel to get their mail

We can use the deltas to determine direction. I'll explain what I mean. As it relates to choosing a mailbox location at one of the buildings' (that is, not in between two buildings):

Choose one of the buildings as a pivot (potential mailbox location). Partition the buildings according to their location in relation to the pivot. While partitioning, keep a record of the closest building on each side of the pivot, as well as (1) the total number of residents on each side of the pivot, and (2) f(side, pivot) representing the total sum of each buildings' distance from the pivot multiplied by the number of residents in that building.

Now we have:

L pivot R

To determine if an improvement can be made for our choice, try each of the closest buildings we recorded earlier:

If we were to move our choice one building to the left, how would the results change? Let's call the closest building on the left build_l, and the right, build_r. So the new results moving our choice one building to the left would be:

Left side:

  f(L, pivot)
- distance(build_l, pivot) * num_residents(build_l)

Right side:

  f(R, pivot) 
  // we saved this earlier
+ total_residents(R) * distance(pivot, build_l)
+ num_residents(pivot) * distance(pivot, build_l)

Perform a similar calculation for moving the choice one building to the right to see which yields a smaller total. Then pick the side with the building that yields an improvement and partition it recursively in similar quickselect fashion until an optimal result is found. For the other side we keep track of the total number of residents, and total result for f so far, which we can update with the new additions as we go.