Grokking Dynamic Programming Interview in Python/

...

/

Partition Array Into Two Arrays to Minimize Sum Difference

Partition Array Into Two Arrays to Minimize Sum Difference

Let's solve the Partition Array Into Two Arrays to Minimize Sum Difference problem using Dynamic Programming.

We'll cover the following...

Statement

Suppose you are given an array, nums, containing positive numbers. You need to partition the array into two arrays such that the absolute difference between their sums is minimized.

Note: Each element of the nums array should be present in one of the partitioned arrays.

Let’s say you have the following array:

  • [2, 3, 1]

The two partitioned arrays with the minimum difference in their sums are:

  • [2,1],sum=3[2, 1], sum = 3
  • [3],sum=3[3], sum = 3

So, the minimum difference becomes ∣3−3∣=0|3-3| = 0.

Constraints:

  • 1≤1\leq nums.length ≤900\leq 900
  • 1≤1\leq nums[i] ≤104\leq 10^4

Examples

No.

nums

partitioned arrays

mimimum difference

1

[5, 4, 4, 7, 2, 9 ]

[4, 5, 7], [2, 4, 9]

1

2

[3, 25, 4, 12, 2]

[25], [12, 4, 3, 2]

4

3

[3, 7, 4, 12, 2]

[7, 4, 3], [12, 2]

0

Try it yourself

Implement your solution in the following playground.

Press + to interact
Python
usercode > main.py
def minimum_partition_array_sum_difference(nums):

    # Write your code here

	

    # your code will replace the placeholder return statement below

    return -1
Partition Array Into Two Arrays to Minimize Sum Difference

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach

A naive approach is to generate all possible combinations of two arrays from the original array. We then check which combination minimizes the difference between the sums of the two partitioned arrays.

For example, we have the following array of values:

  • nums: [4,7,1][4, 7, 1]

To find the minimum difference, we try all possible combinations:

  • [4],[7,1]=>[4], [7, 1] => Difference =4= 4
  • [7],[4,1]=>[7], [4, 1] =>
...