Make Array Strictly Increasing

Let’s solve the problem of making an array strictly increasing by replacing elements from another array. We’ll break it down into simple steps.

We need to make arr1 strictly increasing by replacing its elements with elements from arr2. We want to find the minimum number of such replacements. If it’s not possible to make arr1 strictly increasing, we return -1.

Solution Approach

1. Sort arr2: Since we may need to replace elements in arr1 multiple times, it makes sense to sort arr2 first so that we can quickly find suitable replacements.
2. Use Dynamic Programming: We will use a dictionary dp to maintain the minimum number of operations needed to make the prefix of arr1 up to index i strictly increasing.
3. Iterate through arr1: For each element arr1[i], we look at its predecessor (if exists) and decide whether to replace it or not. We update dp accordingly.
4. Check the Result: If we manage to iterate through arr1 without any issues, we return the minimum number of operations needed. Otherwise, we return -1.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        m = len(arr1)
        # dp[x] = y means we need y operations to make the array up to i strictly increasing and end with x
        dp = {-1: 0}

        for num in arr1:
            new_dp = collections.defaultdict(lambda: float('inf'))
            for key in dp:
                # If current number is greater than the previous ending number (key), it's valid
                if num > key:
                    new_dp[num] = min(new_dp[num], dp[key])
                # Find the smallest number in arr2 that can replace the current number
                loc = bisect.bisect_right(arr2, key)
                if loc < len(arr2):
                    new_dp[arr2[loc]] = min(new_dp[arr2[loc]], dp[key] + 1)
            dp = new_dp

        # If dp is not empty, return the minimum number of operations needed
        if dp:
            return min(dp.values())
        return -1

Insights and Key Takeaways

• Sorting arr2 allows efficient replacement decisions using binary search (bisect_right in Python).
• Dynamic programming helps in keeping track of the minimum operations needed at each step, ensuring that the final solution is optimal.
• The time complexity of this approach is O(m * n * log(n)) where m is the length of arr1 and n is the length of arr2.
• The space complexity is O(m * n) for the dynamic programming storage.
• This problem demonstrates a mix of sorting, binary search, and dynamic programming, focusing on optimizing the replacements to achieve the goal.

Identifying Problem Isomorphism

“Make Array Strictly Increasing” requires you to find the minimum number of operations needed to make the array strictly increasing, where an operation consists of replacing an element.

An approximate isomorphic problem is “Minimum Swaps to Make Sequences Increasing”. Here, you have two integer arrays of the same length, and the goal is to make both of them strictly increasing by swapping the same position elements between the arrays any number of times. You are required to find the minimum number of swaps to make both the sequences strictly increasing.

These are not exactly identical but share a common objective - to transform the original array or arrays into strictly increasing sequences with minimum operations. The strategy to achieve the goal is where the main difference lies. In “Make Array Strictly Increasing”, we replace elements, while in “Minimum Swaps to Make Sequences Increasing”, we swap elements between two arrays.

“Make Array Strictly Increasing” is more complex because it involves not just decision making about which elements to replace, but also what to replace them with. Understanding and solving “Minimum Swaps to Make Sequences Increasing” can provide good groundwork to tackle the more complex problem of “Make Array Strictly Increasing”.

10 Prerequisite LeetCode Problems

To tackle the problem “1187. Make Array Strictly Increasing”, you should have understanding of dynamic programming and exposure to problems that require tracking multiple states.

Here are 10 problems to prepare for this:

1. “Maximal Square” (LeetCode Problem #221): It’s a standard dynamic programming problem which helps you understand how to build solutions from subproblems.

2. “Best Time to Buy and Sell Stock” (LeetCode Problem #121): This problem requires dynamic programming and tracking multiple states.

3. “Climbing Stairs” (LeetCode Problem #70): It’s a simpler dynamic programming problem that introduces the idea of tracking and updating states.

4. “Longest Increasing Subsequence” (LeetCode Problem #300): This problem is about finding the longest subsequence in an array which is in increasing order. It introduces concepts that are directly relevant to “Make Array Strictly Increasing”.

5. “House Robber” (LeetCode Problem #198): In this problem, you’re asked to find the maximum amount of money you can rob from houses located in a line, which is a classic example of dynamic programming.

6. “Coin Change” (LeetCode Problem #322): It’s a popular dynamic programming problem where you’re asked to compute the fewest number of coins needed to make up a certain amount.

7. “Unique Paths” (LeetCode Problem #62): This problem introduces the concept of counting the number of paths in a grid, which is a simpler version of state tracking problems.

8. “Longest Palindromic Subsequence” (LeetCode Problem #516): It helps to understand the concept of subsequences and dynamic programming.

9. “Longest Common Subsequence” (LeetCode Problem #1143): This problem requires you to find the longest common subsequence between two strings, which can be solved through dynamic programming.

10. “Minimum Path Sum” (LeetCode Problem #64): This problem gives you practice in dynamic programming on grids.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        dp = {-1: 0} 
        arr2.sort()

        for num1 in arr1:
            new_dp = {}
            for key in dp:
                if num1 > key:
                    new_dp[num1] = min(new_dp.get(num1, float('inf')), dp[key])
                loc = bisect.bisect_right(arr2, key)
                if loc < len(arr2):
                    new_dp[arr2[loc]] = min(new_dp.get(arr2[loc], float('inf')), dp[key] + 1)
            dp = new_dp
            print(dp)

        if dp:
            return min(dp.values())
        return -1

Problem Classification

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing. In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j]. If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4] Output: 1 Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7]. Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1] Output: 2 Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7]. Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3] Output: -1 Explanation: You can’t make arr1 strictly increasing.

Constraints:

1 <= arr1.length, arr2.length <= 2000 0 <= arr1[i], arr2[i] <= 10^9

Language Agnostic Coding Drills

1. Data types and variables: Understand and create different types of data including integers, floating-point numbers, lists, and dictionaries.

2. Class and function definitions: Define a class and methods within that class. Understand the self keyword and how to use it.

3. List sorting: Sort elements in a list.

4. Iteration: Iterate over elements in a list or keys in a dictionary.

5. Dictionary operations: Get, set, and update values in a dictionary. Understand the get() function and how it works.

6. Comparison and logical operations: Compare values using relational operators like >. Use logical operators like and and or.

7. Conditional statements: Use if, elif, and else statements to perform different actions based on different conditions.

8. Inbuilt functions: Understand and use built-in functions like min() and len().

9. Modules and libraries: Understand what a library is, how to import it, and use its functions. Here we use the bisect module for binary search operations.

10. Binary search: Understand and implement binary search.

The problem solving approach:

1. Start with sorting the second array and initializing a dynamic programming dictionary with -1: 0 as an entry, where the key -1 represents the previous number in the first array, and 0 represents the minimum number of operations.

2. For each number in the first array, create a new dynamic programming dictionary. For each key in the old dynamic programming dictionary, perform the following operations:

   • If the number in the first array is greater than the key, it means we can keep the current number. We then update the number of operations in the new dynamic programming dictionary.
   • We find the position in the sorted second array where a number just greater than the key could be inserted. If this position is valid, it means we can replace the current number with a number from the second array that is just greater than the previous number. Again, we update the number of operations in the new dynamic programming dictionary.

3. Replace the old dynamic programming dictionary with the new one for the next iteration.

4. After processing all numbers from the first array, if there are any entries left in the dynamic programming dictionary, return the minimum number of operations. If the dictionary is empty, return -1.

Understanding the problem step-by-step, starting from understanding the problem statement, breaking down the code into smaller learning units, implementing those units, and then combining them to solve the problem is a good approach to learning and teaching programming and problem solving.

Targeted Drills in Python

1. Data types and variables

   Create different types of variables. Print their types to verify.

   1 2 3 4 5

   a = 10 b = 3.14 c = [1, 2, 3] d = {'name': 'John', 'age': 25} print(type(a), type(b), type(c), type(d))

2. Class and function definitions

   Define a simple class with a few methods.

   1 2 3 4 5 6 7 8 9

   class MyClass: def __init__(self, name): self.name = name def say_hello(self): print(f"Hello, {self.name}!") obj = MyClass('John') obj.say_hello()

3. List sorting

   Create a list with unsorted numbers and sort it.

   1 2 3

   nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] nums.sort() print(nums)

4. Iteration

   Iterate over a list and print each element.

   1 2	for num in nums: print(num)

5. Dictionary operations

   Create a dictionary and perform some basic operations on it.

   1 2 3 4

   dictionary = {'one': 1, 'two': 2} dictionary['three'] = 3 print(dictionary.get('two')) print(dictionary.get('four', 'Not Found'))

6. Comparison and logical operations

   Use comparison and logical operations in a program.

   1 2 3 4

   a = 10 b = 20 if a > b or a == 10: print('a is greater than b or a is 10')

7. Conditional statements

   Write a program with multiple conditions.

   1 2 3 4 5 6

   if a > b: print('a is greater than b') elif a < b: print('a is less than b') else: print('a is equal to b')

8. Inbuilt functions

   Use inbuilt functions like min() and len().

   1 2	print(min(10, 20, 30)) print(len('Hello, world!'))

9. Modules and libraries

   Import a module and use its functions.

   1 2	import math print(math.sqrt(16))

10. Binary search

    Implement binary search function and test it.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

    def binary_search(list, item): low = 0 high = len(list) - 1 while low <= high: mid = (low + high) // 2 guess = list[mid] if guess == item: return mid elif guess > item: high = mid - 1 else: low = mid + 1 return None my_list = [1, 3, 5, 7, 9] print(binary_search(my_list, 3))