1187. Make Array Strictly Increasing

HardArrayBinary SearchDynamic ProgrammingSorting
Leetcode Link

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:

  1. Sort and de-duplicate arr2: We first sort arr2 to make sure we can efficiently find the smallest possible number that we can use to replace an element in arr1 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.

  2. Extend arr1 with sentinel values: We add -inf and inf to the beginning and end of arr1 respectively. This step simplifies edge condition handling, ensuring that we don't need to add any extra conditions for the first and last elements.

  3. Initialize the DP array: We initialize all the elements in the new array f with inf (infinity), which represents an impossible situation. f[0] is set to 0 as no action is needed for the sentinel value -inf.

  4. Fill in the DP array: We iterate over arr1 and for each element arr[i], we do two checks:

    • If arr[i-1] < arr[i], no operation is needed for arr[i], so we carry over the value from f[i-1].
    • We perform a binary search to find the position j in arr2 where a replacement can be made if needed. Then, we iterate backwards through both arr1 and arr2 to find the best possible operation for the current element arr[i]. This is done by checking if replacing k elements from arr1 ending at i-1 with the k previous elements from arr2 before j will result in a valid sequence. If a valid replacement is found, we update f[i] with the minimum value obtained.

  5. Getting the result: After the table f is filled out, we look at f[n-1] (where n is the length of extended arr1) to get the result. If f[n-1] is still inf, it means that there's no possible way to make arr1 strictly increasing with any number of operations, so we return -1. Otherwise, we return f[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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which type of traversal does breadth first search do?

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:

  1. Pre-process arr2: The solution first sorts arr2 to enable efficient binary searches later. Additionally, it removes duplicates from arr2. 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 count m of unique elements.
    • arr2 is then truncated to only include these unique elements.

  2. Extend arr1 with sentinel values: -inf and inf are added at the start and end of arr1, respectively. With this, arr1 becomes arr, preventing out-of-bounds issues and avoiding edge cases.

  3. Initialize the DP array f: We initialize an array f with infinity values, other than the first element, which is 0. f represents our dynamic programming table where f[i] holds the minimum number of operations needed to keep arr[0 ... i] increasing.

  4. Populate f using the DP strategy:

    • For each i in the range 1 to n-1 (where n is the length of the modified arr), we check whether arr[i-1] < arr[i]. If true, we copy the number of operations from f[i-1] as no operation is needed for arr[i].
    • Perform a binary search on arr2 to find the index where you would insert arr[i] to keep arr2 sorted.
    • For every possible replacement count k up to the minimum of (i-1) and the found position in arr2, iterate back and check if replacing the last k elements of arr1 with the previous k elements in arr2 before the found position will maintain the sequence strictly increasing.

  5. 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 where arr[i] could fit in arr2.

  6. Update f[i]: Based on each valid scenario where a sequence of replacements leading to arr[i] maintains the strict increasing order, we update f[i] with the minimum value found, taking into account the number of replacements.

  7. Result retrieval: Finally, after completing the population of f, the solution checks the last element of f. If f[n-1] is still infinite, then it's not possible to make arr1 strictly increasing, hence return -1. Otherwise, the value of f[n-1] indicates the minimum number of operations required.

  8. Complexities: The time complexity of this solution is primarily determined by the for loops and the bisect_left binary searches. Since bisect_left operates in O(log m), where m is the length of arr2, and we may run these searches for each element in arr1 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example 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:

  1. Pre-process arr2: Sort and remove duplicates from arr2.

    After sorting: arr2 becomes [2, 4, 6] (in this case, no duplicates to remove).

  2. Extend arr1 with sentinel values: Add -inf and inf to the start and end of arr1.

    Now arr1 is [-inf, 1, 5, 3, inf].

  3. Initialize the DP array f: We setup f with inf values and set f[0] to 0.

    f: [0, inf, inf, inf, inf]

  4. 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 from arr2.

      Using binary search, find the smallest number in arr2 larger than arr1[2] which is 6 from arr2. After substituting with 6, f[3] should get value from f[2] plus 1 operation.

      Final f: [0, 0, 0, 1, inf]

  5. Result retrieval: Check the last real entry of f ([3] since [4] is for sentinel inf).

    f[3] is 1, which means that it only takes 1 operation to make arr1 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
Not Sure What to Study? Take the 2-min Quiz

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed as follows:

  1. Sorting of arr2 takes O(m log m) time, where m is the length of arr2.
  2. Removing duplicates from arr2 takes O(m) time.
  3. Preparing the modified arr with -inf and inf as boundaries takes O(n) time, where n is the length of arr1 plus 2 (for the added boundaries).
  4. Initializing the f array takes O(n) time.
  5. The main loop runs from 1 to n (happening n times) and within it:
    • The immediate comparison and assignment if arr[i - 1] < arr[i]: is O(1).
    • The binary search (bisect_left) operation inside the loop is O(log m).
    • The innermost loop iterates up to min(i - 1, j) times, which in the worst case could be O(min(n, m)).

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:

  1. The sorted and deduplicated arr2 which is O(m) where m is the length of the unique elements of the sorted arr2.
  2. The arr which includes the original arr1 plus two extra elements, which is O(n).
  3. The f array which is also O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Binary Search Speedrun

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

Dynamic Programming Introduction and Patterns

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

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«