We were discussing an interesting coding exercise where we wanted to split a positive integer array such that the left and right are as nearly balanced in their sum as possible.
we discussed a two pass solution where we find the sums from the left and the right ends and then compare these at each candidate position. The sums from the left and the right help us evaluate if the split at the specified index will result in equal sums. There may be many such splits possible but we pick the index that match the criteria in our iteration.
Then we refined each candidate position by adjusting the left and the right if we know the entire sum
We provided a code sample for this yesterday. What we didn't discuss was whether there is a one-pass solution possible where the iteration from left to right gives the desired partition.
One way to try to do it in one-pass would be keep track of average from either end and grow the left or the right towards the solution based on the difference in the averages. This way we are attempting to make incremental progress from start to finish where each incremental state is guaranteed to make progress over the previous state. It is a progress because we are reducing the array correctly by eliminating the need for a left or a right Whether we take the average or the sum, the question is should we or should we not pass a candidate position without including all the elements in either the left sum or the right sum. Subsequent elements we encounter may actually make this index position a viable split.
Let us take an example:
5 2 1 3
if we take the left initialized to 5 and the right initialized to 3 then we grow the right because it is imbalanced and evaluate based on the succeeding element. In this case we , pick 2 and 1 and choose 1, then add 1 to the right and we now have left as 5 and right as 4. Similarly, we look into the succeeding element as 2 and add it to the right. This way we have achieved the desired split at index = 1
The greedy strategy may not work here because we might skip a candidate index based on the succeeding elements however the undiscovered subarray might might side entirely with the left irrespective of the adjacent element. Hence it is not proper to skip the index based on the adjacent element only. The qualification or disqualification of a method varies based on whether the array can have positive or negative integers
we discussed a two pass solution where we find the sums from the left and the right ends and then compare these at each candidate position. The sums from the left and the right help us evaluate if the split at the specified index will result in equal sums. There may be many such splits possible but we pick the index that match the criteria in our iteration.
Then we refined each candidate position by adjusting the left and the right if we know the entire sum
We provided a code sample for this yesterday. What we didn't discuss was whether there is a one-pass solution possible where the iteration from left to right gives the desired partition.
One way to try to do it in one-pass would be keep track of average from either end and grow the left or the right towards the solution based on the difference in the averages. This way we are attempting to make incremental progress from start to finish where each incremental state is guaranteed to make progress over the previous state. It is a progress because we are reducing the array correctly by eliminating the need for a left or a right Whether we take the average or the sum, the question is should we or should we not pass a candidate position without including all the elements in either the left sum or the right sum. Subsequent elements we encounter may actually make this index position a viable split.
Let us take an example:
5 2 1 3
if we take the left initialized to 5 and the right initialized to 3 then we grow the right because it is imbalanced and evaluate based on the succeeding element. In this case we , pick 2 and 1 and choose 1, then add 1 to the right and we now have left as 5 and right as 4. Similarly, we look into the succeeding element as 2 and add it to the right. This way we have achieved the desired split at index = 1
The greedy strategy may not work here because we might skip a candidate index based on the succeeding elements however the undiscovered subarray might might side entirely with the left irrespective of the adjacent element. Hence it is not proper to skip the index based on the adjacent element only. The qualification or disqualification of a method varies based on whether the array can have positive or negative integers
No comments:
Post a Comment