A puzzle involving dynamic programming, or maybe it doesn't, episode 2


Here's a programming challenge:

Given an array of numbers, count the number of ways the array can be partitioned into three contiguous parts such that each part has the same sum. For example, given the array { 1, 1, -1, 0, -1, 2, 2, 0, -2, 1 }, the answer is seven:

  1. 1 = 1 = (−1) + 0 + (−1) + 2 + 2 + 0 + (−2) + 1
  2. 1 = 1 + (−1) + 0 + (−1) + 2 = 2 + 0 + (−2) + 1
  3. 1 = 1 + (−1) + 0 + (−1) + 2 + 2 + 0 + (−2) = 1
  4. 1 + 1 + (−1) = 0 + (−1) + 2 = 2 + 0 + (−2) + 1
  5. 1 + 1 + (−1) = 0 + (−1) + 2 + 2 + 0 + (−2) = 1
  6. 1 + 1 + (−1) + 0 = (−1) + 2 = 2 + 0 + (−2) + 1
  7. 1 + 1 + (−1) + 0 = (−1) + 2 + 2 + 0 + (−2) = 1

Hint: Start with a solution to the partition problem, and use dynamic programming.

We will assume for now that empty parts are legal. (This is significant only if the array sum is zero.)

The hint to use dynamic programming is yet another red herring.

The first thing you notice is that partitioning without rearrangement is much easier than the general partition problem, since you have to study only C(N+1, 2) subsets rather than 2N. You can calculate sums of contiguous subsets very easily by keeping a running total and taking the difference between the endpoint and the starting point.

If you keep a parallel array with the running totals, you can pick out the subarrays quickly: They are the partitions where the left partition is at the point where the running total is one third of the array sum, and the right partition is at the point where the running total is two thirds of the array sum.

In our example above:

1 1 −1 0 −1 2 2 0 −2 1
1 2 1 1 0 2 4 4 2 3

Since the array total is 3, we want to find points where the running total is one third and two thirds of the total, or 1 and 2. I've highlighted them in the table above. Any time we see a 1 to the left of a 2, we have a successful partition: The first part is everything up to and including the 1; the middle part is everything after the 1 up to and including the 2; the last part is everything after the 2. For example,

1 1 −1 0 −1 2 2 0 −2 1
1 2 1 1 0 2 4 4 2 3

Therefore, to count the number of successful partitions, we need only count how many 1's come before 2's.

function equalthirds(a)
{
  var i;
  var total = 0;
  for (i = 0; i < a.length; i++) {
   total += a[i];
  }
  var third = total / 3;

  var firstpart = 0;
  var partitions = 0;

  var partial = 0;
  for (i = 0; i < a.length; i++) {
    partial += a[i];
    if (partial == third) firstpart++;
    if (partial == third * 2) partitions += firstpart;
  }
  return partitions;
}

equalthirds([ 1, 1, -1, 0, -1, 2, 2, 0, -2, 1 ]);

First, we get the total for the entire array, then calculate one third of the total. That is the target value for the partitions.

Next, we make another pass through the array tracking the running totals. Each time the partial sum reaches one third of the total, we increment the number of "successful first segments at or before this point". And each time the partial sum reaches two thirds of the total, that means that we found a valid spot for the second segment (and therefore also the third segment), so we count all of the successful first segments so far toward our partition count.

The running time of this algorithm is O(N) and the space requirements are constant. This is optimal: You must read every element of the array, because if you skipped one, then an adversary could modify it and alter the totals. (And you can't do better than constant space.)

Exercise: What changes would be necessary if zero-length parts are not legal?

Comments (11)
  1. John Doe says:

    Exercise: With the provided algorithm, an empty part can only occur at the beginning and at the end, since partial cannot be equal to third and third * 2 simultaneously.

    As such, check if we're not in the first or last index before adding partitions up.

    1. Karellen says:

      Given that empty parts have value 0, empty parts are only valid where the sum of the array is 0, and in that case third and third * 2 are both 0, so partial can be equal to both simultaneously.

      For example, given: [-1, -1, 0, 2, -1, 1]

      You can have:
      1: [], [], [-1, -1, 0, 2, -1, 1]
      2: [], [-1, -1, 0, 2], [-1, 1]
      3: [-1, -1, 0, 2], [], [-1, 1]
      4: [-1, -1, 0, 2], [-1, 1], []
      5: [-1, -1, 0, 2, -1, 1], [], []

      Answer 3 has an empty part in the middle.

      1. John Doe says:

        Right. We could "normalize" the values such that the lowest would be 0, e.g. [0, 0, 1, 3, 0, 2], and apply this principle.

      2. Raidri says:

        You are missing one:
        6: [], [-1, -1, 0, 2, -1, 1], []

  2. cheong00 says:

    Btw, I think it's wrong to say "the hint is wrong". The hint only directs you to a more convoluted way to solve the problem, but if you're doing it right, you can follow the hint to solve it.

    Just like in many case where the interview questions has hint to use recursive function, but the question can also be solved without recursive function. Both way should be correct as long as "the instruction to use recursive function" is not written in the main part of question.

  3. John Doe says:

    Exercise (second take): The total == 0 must be special cased. In this case, we increment partitions for each partial == 0, and return Math.max(0, partitions - 2).

    1. Holger Stenger says:

      Can you elaborate how you would count partitions for this special case?

      The worst case is when all partials are 0 which happens when all array elements are 0. Luckily we can give explicit formulas for this case. For an array of length 0 containing only 0 the number of partitions with zero-length segments is \sum_{i=0}^n \sum_{j=0}^i 1 = (n+1)*(n+2)/2, without zero-length segments we have \sum_{i=2}^{n-1} \sum_{j=1}^{i-1} 1 = (n-2)*(n-1)/2, using index transformations and the identity \sum_{i=1}^n = n*(n+1)/2.

  4. jswolf19 says:

    If empty partitions are legal, then this algorithm doesn't take into account empty partitions at the beginning and end of the input array (assuming I'm running the code in my head correctly ^^;).
    For example, given the array [0,0,0], the algorithm outputs 6, but should be 10.

    [], [], [0, 0, 0]
    [], [0], [0, 0]
    [], [0, 0], [0]
    [], [0, 0, 0], []
    [0], [], [0, 0]
    [0], [0], [0]
    [0], [0, 0], []
    [0, 0], [], [0]
    [0, 0], [0], []
    [0, 0, 0], [], []

    Exercise: I think just swapping the ifs in the current algorithm would do it for you.

    1. jswolf19 says:

      "doesn’t take into account empty partitions at the beginning and end of the input array" should be "doesn’t take into account empty partitions at the beginning of the input array", as it does take into account the ones at the end...

  5. jswolf19 says:

    Exercise (second take): You would just want to not go to the end of the array.
    i < a.length - 2 should do it ^^;

  6. jswolf19 says:

    Exercise (third take, and having hopefully learned not to click "Post Comment" buttons so hastily):

    You *do* want to swap the ifs (which removes the counting of empty parts in the middle), and you want to loop to the penultimate array item, so a.length - 1 instead of a.length - 2, but you only want to add to firstpart if there are at least 2 elements left (to remove the counting of empty parts at the end), so you could add a condition to the first if statement, or special case out the final partitions increment check.

    for (i = 0; i < a.length - 1; i++) {
    partial += a[i];
    if (partial == third * 2) partitions += firstpart;
    if (partial == third && i < a.length - 2) firstpart++;
    }

    or

    for (i = 0; i < a.length - 2; i++) {
    partial += a[i];
    if (partial == third * 2) partitions += firstpart;
    if (partial == third) firstpart++;
    }
    partial += a[a.length - 1];
    if (partial == third * 2) partitions += firstpart;

Comments are closed.

Skip to main content