[Java] Minimize travel distance to single array index

Given an array indicating how many people live at the specific index, return the index where to place a postbox that minimizes the total travel time to it for all people.

The following rules apply:

• people residing at the same place of the postbox have a total travel time of 0
• N people needing to take 1 step to reach the postbox have a total travel time of N
• multiple solutions could be acceptable

An obvious O(N^2) solution is to compute the total travel distance for each possible place and store it in a matrix O(N^2), then walk over it to compute the best solution.

A better solution requires some preprocessing and 2 extra O(N) arrays but runs in O(N) total time.

An even better solution uses only one extra array instead.

The idea with the two arrays is to track for each position the total number of steps that people BEFORE and AFTER it, respectively, would need to take to reach it. For example:

input = 1, 2, 3

walking left to right we have:
0: 0 - nobody walks right from here
1: 1 - only one person (input[0]) walks right from here
2: 1+1+2 - one person (input[0]) takes two steps and two people (input[1]) take one step

walking right to left we have instead:
2: 0 - nobody walks left from here
1: 3 - three people (input[2]) take one step
0: 3+3+2 - three people (input[2]) take two steps and two people (input[1]) take one step

The solution can then be found by walking both arrays at the same time, summing the total travel time at each specific index, and updating if necessary the minimum at each step.

The improved solution drops the second array, since we can compute it on the fly with some additional variables.
Note how at each step we only need to remember the result of the previous computation in order to calculate the new value, let's use 3 variables:
tot: total number of people so far, they will always take a single step forward at the next round
prev: total number of steps walked so far
curr: total number of steps to be walked to reach the next location

for the left to right array we would then have the following calculations:
init: curr = 0, prev = 0, tot = 0
2: curr = 3, prev = 0, tot = 3
1: curr = 8, prev = 0, tot = 5
0: useless

So if we translate it to the array which we did not calculate we would have:
2: curr of init = 0
1: curr of step 2 = 3
0: curr of step 1 = 8 

The proposed algorithm will always return the first best solution encountered from the END of the array.

Finding the nice solution was already not easy, but coding the best one hinges all on three simple lines:

prev = curr;
tot += in[i];
curr = tot + prev;

Which took most of the coding time to get done right :)

You can check my implementation of getPostboxPlace on my Gist alongside some test cases in PlacePostboxJTests.