Daily bit(e) of C++ | Strictly increasing array
Daily bit(e) of C++ #301, Common interview problem: Strictly increasing array.
Today, we will look at a common C++ interview problem: Strictly increasing array.
Given two arrays of positive integers, determine the lowest number of operations to make the first array strictly increasing.
In one operation, you can change one element of the first array to a value from the second array (i.e. arr1[i] = arr2[j]).
Return -1 if strictly increasing order cannot be achieved.
While there are two options for achieving a strictly increasing array in the above example, both require three operations.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/fj5jGP7eG.
Solution
First, let’s analyze how we achieve a strictly increasing array. When we consider two neighbouring elements, we can be in two possible situations:
array[i] < array[i+1], i.e. the elements are already in strictly increasing order; however, we still might need to change array[i+1], otherwise we could run into a problem later
array[i] >= array[i+1], i.e. the elements are not in strictly increasing order, we must change array[i+1]
Note that to calculate the state of array[i+1], we only require the value at array[i] and the number of changes we made.
Moreover, we can calculate these values iteratively. For each index, we can calculate all possible values for this index and the corresponding number of changes.
Note that the number of possible values is capped at n+1, where n is the length of the second array. If we switch a value, we have at most n unique values, plus one for the original value.
Finally, when switching, we want to always pick the lowest value from the second array that maintains the strict increasing order. If we sort the second array, we can do this in log(n).
This leaves us with O(m*n*logn) time complexity and O(n) space complexity.
