Check if it's possible to make an integer array strictly ascending by removing a single element

[ajibpaudel]

I am a beginner in C++. Below is the function I wrote to check if an array can be made strictly ascending by removing an element of the array. It will be great if someone can suggest some modification to make the code take lesser time to run.

  bool almostIncreasingSequence(std::vector<int> sequence){
        bool result = false;
        vector <int> new1;
        for(int i=0;i<sequence.size();i++){
            new1 = sequence;
            new1.erase(new1.begin()+i);
            for(int k=0;k<new1.size()-1;k++){
                if(new1[k]<new1[k+1])
                    result = true;
                else{
                    result =false;
                    break;
                }
            }
                if (result == true)
                    break;
        }
            if(sequence.size()==2)
            result=true;
        return result;
   }

[Ganado]

EDIT: MY SOLUTION IS PARTIALLY WRONG,

Since you're only seeing if a certain numbers of removals is necessary (in this case, 1), you should still able to do the algorithm in O(n) time instead of O(n^2), because you only need to compare adjacent values for increasing/decreasing behavior.

I would avoid having to copy and mutate (erase elements) the vector unless absolutely necessary.

increasing (going left to right):
          11
        7
      5
    3
  2

almost increasing (going left to right):
         9
            8
      5  
    3
  2

not almost increasing (going left to right):
           9
              8
     6  
        3
  2

I would have a counter that just says how many times you had to decrease from the previous element while iterating, and if that counter of decreases goes above 1, then it isn't "almost" increasing.

Edit: The tricky part here is that you have to keep track of the "max so far" element so that a situation like {7, 8, 9, 1, 2, 3} still returns false.

#include <iostream>
#include <vector>

bool almostIncreasingSequence(const std::vector<int>& sequence) // no copying necessary to check!
{
    int times_decreasing = 0;
    for (size_t i = 1; i < sequence.size(); i++)
    {
        if (sequence[i] < sequence[i-1]) // you decide: Should this be <= or < ? (depends what your exact problem is)
        {
            times_decreasing++;
        }
    }
    return times_decreasing == 1; // <= if you want a completely-sorted array to still be true
}


int main()
{
    std::vector<int> seq1 { 0, 1, 2, 3, 4 };
    std::vector<int> seq2 { 0, 1, 2, 5, 4 };
    std::vector<int> seq3 { 0, 1, 6, 5, 4 };
    

    if (almostIncreasingSequence(seq1))
        std::cout << "yes" << std::endl;   
    else
        std::cout << "no" << std::endl;   
        
    if (almostIncreasingSequence(seq2))
        std::cout << "yes" << std::endl;   
    else
        std::cout << "no" << std::endl;   
        
    if (almostIncreasingSequence(seq3))
        std::cout << "yes" << std::endl;   
    else
        std::cout << "no" << std::endl;   
        
}

Edit: Shoot, my solution is wrong. since it would pass for {8, 8, 8, 7, 7, 7};

I'll either edit or delete this soon.

[Handy Andy]

Hello ajibpaudel,

You could just not use this function in the first place.

If "sequence" was sorted in ascending to begin with then erasing one element from the vector will keep it in ascending order just one element less.

When you remove an element from a vector the vector class will resize the vector automatically there is nothing you have to do.

The for loop seams a bit pointless and msybe the if statement at line 18.

If I have misunderstood anything here let me know.

Hope that helps,

Andy

Edit: Ok it looks like I totally misunderstood this.

[ajibpaudel]

Thanks for the replies.
@Ganado, yes your code gave wrong answer for arrays of type [1, 2, 3, 4, 5, 3, 5, 6], [1, 2, 1, 2] etc.

@Handy Andy, my code does not work for arrays having 2 integers only, so I put the if statement at line 18 to make it work for all cases.

Actually, this is an assignment in an online C++ code learning challenge in codefight.com, my code passed tests for all arrays but failed the time test, so trying to get help to reduce run time so that I can submit the code and move to next challenge.

[lastchance]

#include <iostream>                        
#include <sstream>
#include <vector>
using namespace std;

bool almostIncreasing( vector<int> &a )
{
   bool available = true;               
   int last = a.size() - 1;
   for ( int i = 1; i <= last; i++ )
   {
      if ( a[i] <= a[i-1] )                         // Must remove either a[i] or a[i-1]
      {                                              
         if ( !available ) return false;            // No lives left; bye-bye
         if ( i == last )  return true;             // Got this far: just remove the last one

         if ( i > 1 )                               // If a[0] >= a[1] then remove a[0]
         {
            int low = a[i-2], high = a[i+1];        // Need to find an intermediate between these
            if ( high <= low + 1 ) return false;    // No room for any intermediate; bound to fail
            bool ok = ( low < a[i-1] && a[i-1] < high )   ||   ( low < a[i] && a[i] < high );
            if ( !ok ) return false;                // Removing neither will help
         }
         available = false;                         // Last life just went
      }
   }
   return true;
}

//======================================================================

int main()
{
   vector<int> a;
   int i;
   string line;
   cout << "Input an array as a single line: ";   getline( cin, line );
   stringstream ss( line );
   while( ss >> i ) a.push_back( i );

   cout << "Sequence status: " << boolalpha << almostIncreasing( a );
}

Input an array as a single line: 1 2 3 2 3
Sequence status: false

Input an array as a single line: 1 2 3 2 4
Sequence status: true

[ajibpaudel]

Thanks. Great! it works.

[rabster]

Here is a generic method which looks nice.

#include <algorithm>
#include <iostream>

template<typename T>
bool solveableSequence(const T& container) {
    if (container.size() == 1) {
        return true; //depends on whether or not a sequence with 1 element qualfies, otherwise change to false
    }
    
    std::size_t operations = 0;
    decltype(std::begin(container)) last = std::begin(container);
    for (auto begin = last, end = std::prev(std::end(container)); begin != end; ++begin) {
        if (!(*last < *std::next(begin))) { //< is for strict ascending, <= is for loose ascending and you might wanna use <= for the return
            ++operations;
            
            if (operations > 1) {
                return false;
            }
        }
        else {
            last = begin + 1;
        }
    }
    return operations == 1; // <= for already sorted data;
}

template<typename T>
void solveSequence(const T& container) {
    std::cout << std::boolalpha << solveableSequence(container) << std::endl;
}

using initList = std::initializer_list<int>;
int main() {
    solveSequence(initList{1, 2, 1, 2});
    solveSequence(initList{8, 8, 8, 7, 7, 7});
    solveSequence(initList{1, 2, 2, 3});
    solveSequence(initList{1, 2, 3, 2, 3});
    solveSequence(initList{1, 2, 3, 2, 4});
    solveSequence(initList{1, 2, 3, 6, 5});
    solveSequence(initList{9, 8, 7});
    solveSequence(initList{1, 2, 3, 6, 5, 4});
}

[ajibpaudel]

Thanks, it's useful to learn different ways of solving the problem.