1187. Make Array Strictly Increasing
Problem Description
The problem requires us to take two integer arrays, arr1
and arr2
, and determine the minimum number of operations to make arr1
strictly increasing. A strictly increasing array means that each element is greater than the previous one.
In a single operation, we can replace an element in arr1
with any element from arr2
. This operation can only be considered valid if it helps in making the sequence strictly increasing.
Our goal is to find out the least number of such substitutions that we must carry out to achieve our strictly increasing sequence in arr1
. If it's not possible to make arr1
strictly increasing regardless of how many operations we perform, we should return -1
.
Intuition
To solve this problem, we use dynamic programming. The key is to create a new array f
where each f[i]
represents the minimum number of operations needed to make the subsequence arr[0 ... i]
strictly increasing.
Here is a step-by-step explanation of the solution:
-
Sort and de-duplicate
arr2
: We first sortarr2
to make sure we can efficiently find the smallest possible number that we can use to replace an element inarr1
to maintain the strictly increasing order. Also, we remove the duplicates because they won't provide any additional value when we want to perform the replacement. -
Extend
arr1
with sentinel values: We add-inf
andinf
to the beginning and end ofarr1
respectively. This step simplifies edge condition handling, ensuring that we don't need to add any extra conditions for the first and last elements. -
Initialize the DP array: We initialize all the elements in the new array
f
withinf
(infinity), which represents an impossible situation.f[0]
is set to0
as no action is needed for the sentinel value-inf
. -
Fill in the DP array: We iterate over
arr1
and for each elementarr[i]
, we do two checks:- If
arr[i-1] < arr[i]
, no operation is needed forarr[i]
, so we carry over the value fromf[i-1]
. - We perform a binary search to find the position
j
inarr2
where a replacement can be made if needed. Then, we iterate backwards through botharr1
andarr2
to find the best possible operation for the current elementarr[i]
. This is done by checking if replacingk
elements fromarr1
ending ati-1
with thek
previous elements fromarr2
beforej
will result in a valid sequence. If a valid replacement is found, we updatef[i]
with the minimum value obtained.
- If
-
Getting the result: After the table
f
is filled out, we look atf[n-1]
(wheren
is the length of extendedarr1
) to get the result. Iff[n-1]
is stillinf
, it means that there's no possible way to makearr1
strictly increasing with any number of operations, so we return-1
. Otherwise, we returnf[n-1]
, which represents the minimum number of operations required.
The algorithm ensures we cover all scenarios to find the minimum operations without unnecessary repetition by examining each possible subsequence of arr1
and the potential elements from arr2
.
Learn more about Binary Search, Dynamic Programming and Sorting patterns.
Solution Approach
The reference solution approach applies a dynamic programming strategy with binary search and data pre-processing to minimize operations. Here's the breakdown of the implementation stages:
-
Pre-process
arr2
: The solution first sortsarr2
to enable efficient binary searches later. Additionally, it removes duplicates fromarr2
. This is done using a unique approach:- It iterates through the sorted
arr2
, comparing each element with the previous one. - It only keeps unique elements, essentially in-place deduplication by shifting non-duplicate elements to the beginning of
arr2
and keeping countm
of unique elements. arr2
is then truncated to only include these unique elements.
- It iterates through the sorted
-
Extend
arr1
with sentinel values:-inf
andinf
are added at the start and end ofarr1
, respectively. With this,arr1
becomesarr
, preventing out-of-bounds issues and avoiding edge cases. -
Initialize the DP array
f
: We initialize an arrayf
with infinity values, other than the first element, which is0
.f
represents our dynamic programming table wheref[i]
holds the minimum number of operations needed to keeparr[0 ... i]
increasing. -
Populate
f
using the DP strategy:- For each
i
in the range1
ton-1
(wheren
is the length of the modifiedarr
), we check whetherarr[i-1] < arr[i]
. If true, we copy the number of operations fromf[i-1]
as no operation is needed forarr[i]
. - Perform a binary search on
arr2
to find the index where you would insertarr[i]
to keeparr2
sorted. - For every possible replacement count
k
up to the minimum of(i-1)
and the found position inarr2
, iterate back and check if replacing the lastk
elements ofarr1
with the previousk
elements inarr2
before the found position will maintain the sequence strictly increasing.
- For each
-
Use
bisect_left
for binary search: This function from Python's bisect module finds the index where a given number would be placed to maintain the list's sorted order. It's used to find wherearr[i]
could fit inarr2
. -
Update
f[i]
: Based on each valid scenario where a sequence of replacements leading toarr[i]
maintains the strict increasing order, we updatef[i]
with the minimum value found, taking into account the number of replacements. -
Result retrieval: Finally, after completing the population of
f
, the solution checks the last element off
. Iff[n-1]
is still infinite, then it's not possible to makearr1
strictly increasing, hence return-1
. Otherwise, the value off[n-1]
indicates the minimum number of operations required. -
Complexities: The time complexity of this solution is primarily determined by the
for
loops and thebisect_left
binary searches. Sincebisect_left
operates inO(log m)
, wherem
is the length ofarr2
, and we may run these searches for each element inarr1
which itself is processed in nested loops, the overall time complexity is substantial, but the exact rate depends on the input patterns.
The code uses common dynamic programming techniques such as tabulation (storing intermediate results in f
array) and relies on efficient binary searching to accelerate decision-making about potential replacements. The use of sentinel values as boundaries is a classic edge-case management technique in array processing problems.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider two arrays as an example to illustrate the solution approach:
arr1
: [1, 5, 3]arr2
: [4, 2, 6]
Steps of the Approach:
-
Pre-process
arr2
: Sort and remove duplicates fromarr2
.After sorting:
arr2
becomes [2, 4, 6] (in this case, no duplicates to remove). -
Extend
arr1
with sentinel values: Add-inf
andinf
to the start and end ofarr1
.Now
arr1
is[-inf, 1, 5, 3, inf]
. -
Initialize the DP array
f
: We setupf
withinf
values and setf[0]
to0
.f
: [0, inf, inf, inf, inf] -
Populate
f
using the DP strategy:-
For i=1 (arr1[1] = 1),
arr1[0] < arr1[1]
, so no substitution required and f[1] gets value from f[0]. -
For i=2 (arr1[2] = 5),
arr1[1] < arr1[2]
, so no substitution required and f[2] gets value from f[1]. -
For i=3 (arr1[3] = 3),
arr1[2] > arr1[3]
, which breaks the strictly increasing condition. We need to find the best substitution fromarr2
.Using binary search, find the smallest number in
arr2
larger thanarr1[2]
which is 6 fromarr2
. After substituting with 6, f[3] should get value from f[2] plus 1 operation.Final
f
: [0, 0, 0, 1, inf]
-
-
Result retrieval: Check the last real entry of
f
([3] since [4] is for sentinelinf
).f[3]
is1
, which means that it only takes 1 operation to makearr1
strictly increasing.
By following these steps with the given example, we have found that the minimum number of operations required to make arr1
strictly increasing is 1 which is achieved by replacing the third element of arr1
with 6 from arr2
.
Solution Implementation
1from bisect import bisect_left
2from math import inf
3
4class Solution:
5 def make_array_increasing(self, arr1: List[int], arr2: List[int]) -> int:
6 arr2.sort() # Sort the second array
7
8 # Remove duplicates from arr2 efficiently.
9 unique_length = 0
10 for element in arr2:
11 if unique_length == 0 or element != arr2[unique_length - 1]:
12 arr2[unique_length] = element
13 unique_length += 1
14 arr2 = arr2[:unique_length]
15
16 # Prepend and append infinity to handle edge conditions smoothly.
17 arr = [-inf] + arr1 + [inf]
18 num_elements = len(arr)
19
20 # Initialize the minimum operations array with infinity.
21 min_ops = [inf] * num_elements
22 min_ops[0] = 0 # No operation needed for the first element.
23
24 for i in range(1, num_elements): # Iterate over arr
25 # If the current element is greater than the previous one, no operation is needed.
26 if arr[i - 1] < arr[i]:
27 min_ops[i] = min_ops[i - 1]
28
29 # Find the index of the smallest element in arr2 which is greater than or equal to arr[i].
30 replacement_idx = bisect_left(arr2, arr[i])
31
32 # Try to replace elements in arr1 with smaller elements in arr2
33 for replace_count in range(1, min(i, replacement_idx) + 1):
34 # Check if a valid replacement sequence is possible.
35 if arr[i - replace_count - 1] < arr2[replacement_idx - replace_count]:
36 min_ops[i] = min(min_ops[i], min_ops[i - replace_count - 1] + replace_count)
37
38 # If no operations can convert arr1, then return -1, otherwise return the minimum operations.
39 return -1 if min_ops[num_elements - 1] == inf else min_ops[num_elements - 1]
40
1class Solution {
2
3 public int makeArrayIncreasing(int[] arr1, int[] arr2) {
4 // Sort the second array and remove duplicates
5 Arrays.sort(arr2);
6 int uniqueElementsCount = removeDuplicates(arr2);
7
8 // Assign a value to represent infinity
9 final int INF = Integer.MAX_VALUE;
10
11 // Create a new array with 'infinity' as boundaries
12 int[] modifiedArray = new int[arr1.length + 2];
13 modifiedArray[0] = -INF;
14 modifiedArray[modifiedArray.length - 1] = INF;
15
16 // Copy elements from arr1 to the middle of modifiedArray
17 System.arraycopy(arr1, 0, modifiedArray, 1, arr1.length);
18
19 // Initialize the state array with 'infinity'
20 int[] state = new int[modifiedArray.length];
21 Arrays.fill(state, INF);
22
23 // First element (boundary) will always have a state of 0
24 state[0] = 0;
25
26 // Dynamic programming to find minimum operations
27 for (int i = 1; i < modifiedArray.length; ++i) {
28 // Carry forward the state if the current element is greater than the previous one
29 if (modifiedArray[i - 1] < modifiedArray[i]) {
30 state[i] = state[i - 1];
31 }
32
33 // Binary search to find the number of operations needed
34 int insertPos = binarySearch(arr2, modifiedArray[i], uniqueElementsCount);
35 for (int k = 1; k <= Math.min(i - 1, insertPos); ++k) {
36 if (modifiedArray[i - k - 1] < arr2[insertPos - k]) {
37 state[i] = Math.min(state[i], state[i - k - 1] + k);
38 }
39 }
40 }
41
42 // If state at the last position is 'infinity', return -1
43 return state[modifiedArray.length - 1] == INF ? -1 : state[modifiedArray.length - 1];
44 }
45
46 // Helper method to remove duplicates from sorted array and return the count of unique elements
47 private int removeDuplicates(int[] sortedArray) {
48 int counter = 0;
49 for (int number : sortedArray) {
50 if (counter == 0 || number != sortedArray[counter - 1]) {
51 sortedArray[counter++] = number;
52 }
53 }
54 return counter; // Return unique elements count
55 }
56
57 // Helper method to perform binary search
58 private int binarySearch(int[] nums, int target, int size) {
59 int left = 0, right = size;
60 while (left < right) {
61 int mid = (left + right) >> 1;
62 if (nums[mid] >= target) {
63 right = mid;
64 } else {
65 left = mid + 1;
66 }
67 }
68 return left; // Position where target should be inserted
69 }
70}
71
1class Solution {
2public:
3 int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
4 // Sort the second array and remove any duplicate elements
5 sort(arr2.begin(), arr2.end());
6 arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
7
8 // Initialize infinity as a very large number since we are using integers
9 const int INF = 1 << 30;
10
11 // Add boundary values to the first array
12 arr1.insert(arr1.begin(), -INF);
13 arr1.push_back(INF);
14
15 int n = arr1.size(); // Size of the modified first array
16 // Initialize the dp (dynamic programming) array with infinity
17 // This will keep track of the minimum operations needed to make subarrays increasing
18 vector<int> dp(n, INF);
19 dp[0] = 0; // Base case: no operations needed for the first element
20
21 // Iterate through the first array
22 for (int i = 1; i < n; ++i) {
23 // If the current element is greater than the previous one, no operation is needed
24 if (arr1[i - 1] < arr1[i]) {
25 dp[i] = dp[i - 1];
26 }
27 // Find the position in arr2 where the current element of arr1 would fit
28 int closestInArr2 = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
29
30 // Look for the minimum operations required to make the
31 // subarray ending in position i increasing by replacing
32 // elements with the ones from arr2
33 for (int k = 1; k <= min(i - 1, closestInArr2); ++k) {
34 // Ensure that by replacing the last k elements of arr1[i-k-1...i-1]
35 // with arr2[closestInArr2-k...closestInArr2-1] we get a valid increasing subarray
36 if (arr1[i - k - 1] < arr2[closestInArr2 - k]) {
37 dp[i] = min(dp[i], dp[i - k - 1] + k);
38 }
39 }
40 }
41 // If the value in dp for last index is still INF, it means we
42 // couldn't make the array strictly increasing, return -1 in that case.
43 return dp[n - 1] >= INF ? -1 : dp[n - 1];
44 }
45};
46
1function makeArrayIncreasing(arr1: number[], arr2: number[]): number {
2 // Sort the second array and remove duplicates
3 arr2.sort((a, b) => a - b);
4 let uniqueArr2Length = 0;
5 for (const num of arr2) {
6 if (uniqueArr2Length === 0 || num !== arr2[uniqueArr2Length - 1]) {
7 arr2[uniqueArr2Length++] = num;
8 }
9 }
10 arr2 = arr2.slice(0, uniqueArr2Length); // Get the unique elements in arr2
11
12 // Define infinity for infeasible situations
13 const infinity = 1 << 30;
14 arr1 = [-infinity, ...arr1, infinity]; // Pad arr1 with -inf and inf at the ends
15 const arr1Length = arr1.length;
16 const minOperations: number[] = new Array(arr1Length).fill(infinity);
17 minOperations[0] = 0;
18
19 // Binary search to find the position of the element just larger than 'x' in 'arr'
20 const binarySearch = (arr: number[], x: number): number => {
21 let left = 0;
22 let right = arr.length;
23 while (left < right) {
24 const mid = (left + right) >> 1;
25 if (arr[mid] >= x) {
26 right = mid;
27 } else {
28 left = mid + 1;
29 }
30 }
31 return left;
32 };
33
34 // Calculate the minimum number of moves needed
35 for (let i = 1; i < arr1Length; ++i) {
36 if (arr1[i - 1] < arr1[i]) {
37 minOperations[i] = minOperations[i - 1]; // If current is bigger, no change needed
38 }
39 const position = binarySearch(arr2, arr1[i]);
40
41 // Replace elements in arr1 with elements in arr2 for minimum operations
42 for (let k = 1; k <= Math.min(i - 1, position); ++k) {
43 if (arr1[i - k - 1] < arr2[position - k]) {
44 minOperations[i] = Math.min(minOperations[i], minOperations[i - k - 1] + k);
45 }
46 }
47 }
48
49 // If the last element has inf value, it's impossible to make the array strictly increasing
50 return minOperations[arr1Length - 1] >= infinity ? -1 : minOperations[arr1Length - 1];
51}
52
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed as follows:
- Sorting of
arr2
takesO(m log m)
time, wherem
is the length ofarr2
. - Removing duplicates from
arr2
takesO(m)
time. - Preparing the modified
arr
with-inf
andinf
as boundaries takesO(n)
time, wheren
is the length ofarr1
plus 2 (for the added boundaries). - Initializing the
f
array takesO(n)
time. - The main loop runs from
1
ton
(happeningn
times) and within it:- The immediate comparison and assignment
if arr[i - 1] < arr[i]:
isO(1)
. - The binary search (
bisect_left
) operation inside the loop isO(log m)
. - The innermost loop iterates up to
min(i - 1, j)
times, which in the worst case could beO(min(n, m))
.
- The immediate comparison and assignment
Considering the above operations, the overall worst-case time complexity of the main portion of the code (ignoring the time to create the array f
and arr
) seems to be O(n * min(n, m) * log m)
due to the nested loops and the binary search within the main loop.
Space Complexity
The space complexity can be evaluated as follows:
- The sorted and deduplicated
arr2
which isO(m)
wherem
is the length of the unique elements of the sortedarr2
. - The
arr
which includes the originalarr1
plus two extra elements, which isO(n)
. - The
f
array which is alsoO(n)
.
Thus, the total space complexity amounts to O(m + n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!