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
 Sort arr2: Since we may need to replace elements in
arr1
multiple times, it makes sense to sortarr2
first so that we can quickly find suitable replacements.  Use Dynamic Programming: We will use a dictionary
dp
to maintain the minimum number of operations needed to make the prefix ofarr1
up to indexi
strictly increasing.  Iterate through arr1: For each element
arr1[i]
, we look at its predecessor (if exists) and decide whether to replace it or not. We updatedp
accordingly.  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


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 ofarr2
.  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:
“Maximal Square” (LeetCode Problem #221): It’s a standard dynamic programming problem which helps you understand how to build solutions from subproblems.
“Best Time to Buy and Sell Stock” (LeetCode Problem #121): This problem requires dynamic programming and tracking multiple states.
“Climbing Stairs” (LeetCode Problem #70): It’s a simpler dynamic programming problem that introduces the idea of tracking and updating states.
“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”.
“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.
“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.
“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.
“Longest Palindromic Subsequence” (LeetCode Problem #516): It helps to understand the concept of subsequences and dynamic programming.
“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.
“Minimum Path Sum” (LeetCode Problem #64): This problem gives you practice in dynamic programming on grids.


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
Data types and variables: Understand and create different types of data including integers, floatingpoint numbers, lists, and dictionaries.
Class and function definitions: Define a class and methods within that class. Understand the
self
keyword and how to use it.List sorting: Sort elements in a list.
Iteration: Iterate over elements in a list or keys in a dictionary.
Dictionary operations: Get, set, and update values in a dictionary. Understand the
get()
function and how it works.Comparison and logical operations: Compare values using relational operators like
>
. Use logical operators likeand
andor
.Conditional statements: Use
if
,elif
, andelse
statements to perform different actions based on different conditions.Inbuilt functions: Understand and use builtin functions like
min()
andlen()
.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.Binary search: Understand and implement binary search.
The problem solving approach:
Start with sorting the second array and initializing a dynamic programming dictionary with
1: 0
as an entry, where the key1
represents the previous number in the first array, and0
represents the minimum number of operations.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.
Replace the old dynamic programming dictionary with the new one for the next iteration.
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 stepbystep, 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
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))
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()
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)
Iteration
Iterate over a list and print each element.
1 2
for num in nums: print(num)
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'))
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')
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')
Inbuilt functions
Use inbuilt functions like min() and len().
1 2
print(min(10, 20, 30)) print(len('Hello, world!'))
Modules and libraries
Import a module and use its functions.
1 2
import math print(math.sqrt(16))
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))