The ultimate dynamic programming guide by FAANG engineers. Structured prep with real-world DP questions to get interview-ready in hours!

New Dynamic Programming Interview-Python.png

Some of the toughest questions in technical interviews require dynamic programming solutions. Dynamic programming (DP) is an advanced optimization technique applied to recursive solutions. However, DP is not a one-size-fits-all technique, and it requires practice to develop the ability to identify the underlying DP patterns. With a strategic approach, coding interview prep for DP problems shouldn’t take more than a few weeks.

This course starts with an introduction to DP and thoroughly discusses five DP patterns. You’ll learn to apply each pattern to several related problems, with a visual representation of the working of the pattern, and learn to appreciate the advantages of DP solutions over naive solutions.

After completing this course, you will have the skills you need to unlock even the most challenging questions, grok the coding interview, and level up your career with confidence.

This course is also available in JavaScript, C++, and Java—with more coming soon!

Grokking Dynamic Programming Interview in Python

# 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$ 
- $[3], sum = 3$

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

**Constraints:**
- $1\leq$ `nums.length` $\leq 900$
- $1\leq$ `nums[i]` $\leq 10^4$

# Examples

align-center

# Try it yourself

Implement your solution in the following playground.

Help me debug only the function minimum_partition_array_sum_difference.I don't need the corrected code.I don't want explanations or code reviews. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Please don't give me the corrected code. Just provide me exact and to-the-point advice on how to correct the code so that it runs successfully on the test cases provided. 

Your current task is to review minimum_partition_array_sum_difference function And Answer the following questions: Ensure that the 0/1 Knapsack  pattern used? Does the code follow proper language guidelines. At the end, review the code.

Please provide a brief time complexity analysis of the function minimum_partition_array_sum_difference.While calculating time complexity, include the time complexity of built-in Pythonfunctions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function minimum_partition_array_sum_difference.While calculating space complexity, include the space complexity of built-in Pythonfunctions invoked by the code. The Answer should be to the point and in a few lines.

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = [] 
        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(self.__inputs[0] + self.__inputs[1])

        if json.dumps(self.__inputs[0] + self.__inputs[1]) == json.dumps(self.__actual_outputs[0]):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

def minimum_partition_array_sum_difference(nums):
    # Write your code here
	
    # your code will replace the placeholder return statement below
    return -1

testcases:
  - name: "testcase 6"
    inputs:
    - 1 : [5, 4, 4, 7, 2, 9]
    output: 
    - 1 : 1
  - name: "testcase 7"
    inputs:
    - 1: [3, 25, 4, 12, 2]
    output:
    - 1 : 4
  - name: "testcase 8"
    inputs:
    - 1: [3, 7, 4, 12, 2]
    output:
    - 1 : 0
  - name: "testcase 9"
    inputs:
    - 1: [1, 1, 1, 1000, 1]
    output:
    - 1 : 996
  - name: "testcase 10"
    inputs:
    - 1: [45, 2, 9, 87, 9, 12, 54, 56]
    output:
    - 1 : 6
  - name: "testcase 11"
    inputs:
    - 1: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    output:
    - 1 : 10
  - name: "testcase 12"
    inputs:
    - 1: [4, 11, 15, 17, 18, 25, 26, 29, 32, 35, 37, 42, 43, 45, 46, 48, 49, 55, 62, 66, 67, 68, 70, 78, 83, 88, 92, 94, 96, 100]
    output:
    - 1 : 1

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : [5, 4, 4, 7, 2, 9]
    output: 
    - 1 : 1
  - name: "testcase 2"
    inputs:
    - 1: [3, 25, 4, 12, 2]
    output:
    - 1 : 4
  - name: "testcase 3"
    inputs:
    - 1: [3, 7, 4, 12, 2]
    output:
    - 1 : 0
  - name: "testcase 4"
    inputs:
    - 1: [1, 1, 1, 1000, 1]
    output:
    - 1 : 996
  - name: "testcase 5"
    inputs:
    - 1: [45, 2, 9, 87, 9, 12, 54, 56]
    output:
    - 1 : 6

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
        """
        self.__inputs is the list of inputs that are passed as input to function
        store the result using the self.store_result(error_msg, status)
        return : void
        """
        # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
        if self.__inputs[0] > 1000:
            self.store_result ("input 1 should be less than 1000", ValidationFunction.FAIL)
        elif self.__inputs[1] > 1000:
            self.store_result("input 2 should be less than 1000", ValidationFunction.FAIL)
        else:
            self.store_result("", ValidationFunction.PASS)


>**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]$

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

- $[4], [7, 1] =>$ Difference $= 4$ 
- $[7], [4, 1] =>$ Difference $= 2$
- $[1], [4, 7] =>$ Difference $= 10$ 
- $[7,1], [4] =>$ Difference $= 4$ 
- $[4,1], [7] =>$ Difference $= 2$ 
- $[4,7], [1] =>$ Difference $= 10$
- $[4, 7, 1], [] =>$ Difference $= 12$
- $[], [4, 7, 1] =>$ Difference $= 12$

The calculation above shows that we need a recursive solution to make all possible combinations. In other words, we divide the problem into subproblems, and for each array element, we decide whether to place it in the first or second partitioned array. This is done using the following rules: 

- **Base case:** If we reach the end of the array, and there are no elements to add in either of the partitioned arrays, we return the absolute difference between the sums of the two arrays.

- Otherwise, we calculate the difference in the sums of the two arrays for the two scenarios:

  - add the current element to the first partitioned array
  - add it to the second partitioned array

We then select the option that results in the minimum difference.

Let’s implement the algorithm as discussed above:






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

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Partition Array Into Two Arrays to Minimize Sum Difference