Minimum number of operations to make an array non-decreasing

Question

You have an array of integers.

In one step, you can change the value at any index into any integer value. What is the minimum number of steps in which you can make the array non-decreasing?

Eg 1:

If the array is [8, 12, 11, 15],

We can change the value at the index 2 from 11 to 13. Then the array becomes [8, 12, 13, 15]

So, no of steps needed = 1

Eg 2:

If the array is [9, 2, 5, 18, 20, 25, 19],

We can change the value at the index 0 from 9 to 2 and the value at the index 6 from 19 to 30. Then the array becomes [2, 2, 5, 18, 20, 25, 30]

So, no of steps needed = 2

Eg 3:

If the array is [9, 11, 5, 7],

We can change the value at the index 2 from 5 to 11 and the value at the index 3 from 7 to 11. Then the array becomes [9, 11, 11, 11]

So, no of steps needed = 2

Eg 4:

If the array is [13, 12, 10, 7, 6],

After making the changes, the array becomes [13, 13, 13, 13, 13] or [6, 7, 10, 12, 13]. There are multiple ways of doing this.

So, no of steps needed = 4

One way I tried would be to find all the decreasing subsequences and add the length of them - 1 to a variable named ans. Then return it. But it's failing in the Eg 3 mentioned above. How to solve this?

Answer 1

As @sfx mentions, this is equivalent to finding the longest non-decreasing subsequence.

If you find any non-decreasing subsequence S in the input array A, only the values of the remaining elements in A need to be changed to make the entire array non-decreasing. The number of elements to be changed is |A| - |S|.

If that subsequence is the longest non-decreasing subsequence, which gives you the greatest number of elements that are already sorted order, then the number of elements to be changed, |A| - |S|, will be minimized. If you selected any shorter non-decreasing subsequence, more elements would need to be changed.

You can find the length of this subsequence using Patience sorting.

The algorithm from Wikipedia:

1. The first card dealt forms a new pile consisting of the single card.
2. Each subsequent card is placed on some existing pile whose top card has a value no less than the new card's value, or to the right of all of the existing piles, thus forming a new pile.
3. When there are no more cards remaining to deal, the game ends.

Using your example 3:

[9, 11, 5, 7]

Insert [9]:

[9]

Insert [11]: There is no value greater than or equal to [11] in the output array, so add another stack:

[9, 11]

Insert [5]: The first value greater than or equal to [5] is [9], so replace [9]:

[5, 11]

Insert [7]: The first value greater than or equal to [7] is [11], replace [11]:

[5, 7]

The length of the output array is the length of the longest non-decreasing subsequence. The number of operations to make the entire sequence non-decreasing is equal to the number of elements in the input array minus the length of this subsequence.

Using binary search to determine where to place the next value, the worst case time complexity of this approach is O(n log n).

You can find discussion and references on the correctness of Patience sorting in finding the longest increasing subsequence here: Why does Patience sorting find the longest increasing subsequence?

Answer 2

I think this problem is equivalent to finding the longest non-decreasing chain in the sequence.

Take each index i to be the node of a graph. Then node i has an arrow to node j if and only if i < j and L[i] <= L[j]. Then you need to find the longest path in the graph using techniques from graph theory.

You won't get loops because of the condition i<j.