Count the number of ways to make a sequence sorted by deleting one item

Question

I recently cam across a question that is basically a variant of the following problem:

We want to make an array sorted in non-decreasing order by deleting exactly one item from it. How many ways can we do that ?

For example, if the input array is [3, 4, 5, 4], the answer will 2, as we can delete either 5 or the second 4.

If the array is [3, 4, 5, 2] the answer will be 1, as we can delete 2.

If the array is [1, 2, 3, 4, 5] the answer will be 5, as we can delete any one of the elements.

I am struggling to solve this problem. Any pointer / direction regarding the solution strategy would be highly appreciated.

Answer 1

The examples you give already cover most cases; the answer is always either 0, 1, 2 or N, and you should be able to find the solution by iterating over the sequence once.

Iterate over the array from left to right, looking for pairs of adjacent elements of which the left one is greater than the right one.

If you get to the end of the sequence without finding a decreasing pair, then the sequence is already non-decreasing, and the answer is N.

If you find a decreasing pair, check whether removing the left element works, i.e. whether the element before it is not greater than the right element, and then check whether removing the right element works, i.e. whether the left element is not greater than the element after the right element.

If neither of these options works, you can return the answer 0, because it is impossible to make the sequence non-decreasing; e.g. [2,2,1,1].

If 1 or 2 of the options work, go on checking the rest of the sequence; if you find another decreasing pair, the answer becomes 0 (impossible).

In pseudo-code:

options = 0
for i is 1 to array.length - 1
    if array[i-1] > array[i]
        if options is not 0
            return 0
        if i is 1 or array[i-2] <= array[i]
            ++options
        if i is array.length - 1 or array[i-1] <= array[i+1]
            ++options
        if options is 0
            return 0
if options is 0
    options = array.length
return options

Or translated into a simple Javascript code snippet:

function numberOfWays(array) {
    var options = 0
    for (var i = 1; i < array.length; i++) {
        if (array[i-1] > array[i]) {
            if (options != 0) return 0;
            if (i == 1 || array[i-2] <= array[i]) ++options;
            if (i == array.length - 1 || array[i-1] <= array[i+1]) ++options;
            if (options == 0) return 0;
        }
    }
    return (options == 0) ? array.length : options;
}

var arrays = [[1,2,3,4],[1,3,2,4],[1,2,4,3],[1,3,4,2],[2,4,1,3],[2,2,1,1]];
for (var a in arrays)
    document.write(arrays[a] + " &rarr; " + numberOfWays(arrays[a]) + "<br>");