Number of ways to delete a number from an array to maintain the array in non-decreasing order
sheikhazad
502
Interview

I need help to find Number of ways to delete a number from an array to maintain the array in non-decreasing order. E.g.
[4,5,2,6,7], output = 1, we can remove element 2.
[4,5,2,2,7], output = 0, removing one element doesnt make array non-decreasing sequence
[2,1], output = 2, we can remove either element
[3,2,5], output = 2, we can remove either 3 or 2
[6,7,9], output = 2, we can remove either 7 or 9
[6,7,5], output = 1, we can remove 5

I have a very silly algo, and works with above all test cases but not sure if it will work for all cases and I know it's not efficient one. Pls help with faster algo.

int NumberOfWaysToDeleteANumToMakeNonDecreasingSeq(vector<int>&A)
{
	//1)Sorted arrays {1,2,3,4,5} or size = 2, cut any tree
	if(is_sorted(A.begin(), A.end()) || A.size()==2)
	{  return A.size();	}

	int count{0};
	//Return first unsorted iterator (i.e last 4 in {3,4,5,4} )
	auto UnsortedIt = is_sorted_until(A.begin(), A.end());
	//2) {3,4,5,4} or {3,4,6,5}
	if(UnsortedIt+1 == A.end()) //If last item is the unsorted one,
    {//2.1) If unsorted item is >= previous to previous, cut last item or 2nd last
        if( (distance(A.begin(), UnsortedIt) >=2) &&
            ( *UnsortedIt >= *(UnsortedIt-2) ) )
           {  count += 2; } //{3,4,5,4}, {3,4,6,5} => cut last item or 2nd last
        //2.2) {3,4,6,2} => cut last item
        else { ++count; }
    }
    else //3) If unsorted item is not the last item in array
    {
        vector<int>copyA(A);
        //3.1) {5,2,2,2,2}, {1,5,2,2,2,2} =>remove 5
        A.erase(UnsortedIt-1);
        if(is_sorted(A.begin(), A.end())) ++count;

        //3.2) {4,5,2,6,7} => remove 2
        auto UnsortedIt2 = is_sorted_until(copyA.begin(), copyA.end());
        copyA.erase(UnsortedIt2);
        if(is_sorted(copyA.begin(), copyA.end())) ++count;
    }
	return count;
}
Comments (2)