CODEWITHSUNDEEP
c++c++11sequence
Vader
Vader

Reputation: 111

Increasing Sequence C++

I try to solve this challenge on CodeFights, but, it doesn't work. My best solution got 25/26 (time limit exceeded on the last test) but I deleted that because I tried it yesterday (it was O(n^2)). Now I tried a new one in O(n). I am very tired and I really want to get this done today, so please help me.

Here are the statements: Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

And here is my code until now... (poor code):

#include <iostream>
#include <vector>

#include <algorithm>

bool almostIncreasingSequence(std::vector<int> sequence) 
{
    int count = 0;


    for(int i = 0; i < sequence.size()-1; i++)
    {
        if(sequence[i] > sequence[i+1])
        {
            count++;
            sequence.erase(sequence.begin(), sequence.begin() + i);
            i--;
        }
        if(count == 2)
            return false;
    }
    return true;
}

int main()
{
    std::cout << std::endl;
    return 0;
}

Upvotes: 5

Views: 6462

Answers (4)

Pankaj Tanwar
Pankaj Tanwar

Reputation: 1

#include<iostream>
#include<vector>
using namespace std;
int almostIncreasingSequence( vector<int> sequence );

int main(){
    int array[] = {40, 50, 60, 10, 20, 30};
    std::vector<int> vect (array, array + sizeof(array) / sizeof(int) );
    bool ret = almostIncreasingSequence(vect);

    if( ret ){
        std::cout<<"Array is strictly increasing.";
    }
    else{
std::cout<<"Array is not strictly increasing.";
    }
    return 0;
}
bool almostIncreasingSequence(std::vector<int> sequence) {
    int val = 0;
    int currentBig = sequence.at(0);
    for (int i = 1; i < sequence.size(); i++){
        if( currentBig < sequence.at(i))
        {
            currentBig = sequence.at(i);
        }
        else{
            val++;
            if( val>1)
            {
                return false;
            }
            if( i > 1 ){
                if (sequence.at(i) > sequence.at(i-2)){
                    if( currentBig < sequence.at(i) ){
                    }
                    else{
                        currentBig = sequence.at(i);
                    }
                }
            }
            else{
                currentBig = sequence.at(i);
            }
        }
    }
    return true;
}

Upvotes: 0

zmbq
zmbq

Reputation: 39013

This is still O(N^2), because you delete the first element of the vector in each iteration. Don't delete the first element and don't i-- in the loop.

If you must erase the numbers (you don't, but still), at least do it from the end of the list. That way erasing a number is probably an O(1) operation (I'm not 100% sure that's how std::vector is implemented).

You really don't have to erase the numbers.

Upvotes: 0

WhiZTiM
WhiZTiM

Reputation: 21576

Here is a C++11 solution with O(N) runtime:

constexpr auto Max = std::numeric_limits<std::size_t>::max();
bool is_sorted_but_skip(const std::vector<int>& vec, std::size_t index = Max){
    auto Start = index == 0 ? 1 : 0;
    auto prev = vec[Start];
    for(std::size_t i = Start + 1; i < vec.size(); i++){
        if(i == index) continue;
        if(prev >= vec[i]) return false;
        prev = vec[i];
    }
    return true;
}

bool almostIncreasingSequence(std::vector<int> v) 
{
    auto iter = std::adjacent_find(v.begin(), v.end(), [](int L, int R){ return L >= R; });
    if(is_sorted_but_skip(v, std::distance(v.begin(), iter)))
        return true;
    return is_sorted_but_skip(v, std::distance(v.begin(), std::next(iter)));
}

We use std::adjacent_find to find the first element, iter greater than or equal its next element. Then we check that sequence is strictly sorted while skipping iter's position.

Otherwise, we check that the sequence is strictly sorted while we skip iter+1's position

Worse case complexity: 3 linear scan

Demo

Upvotes: 3

einpoklum
einpoklum

Reputation: 131533

Here's a hint (well, almost a solution really):

If you see a decrease between one element to the next, then you have to remove one of them (*).

Now, what if you find two decreases, between two disjoint pairs of elements? That's right :-)

Keeping that in mind, you should be able to solve your problem using a linear scan and a bit of constant-time work.

(*) excluding the first and the last pair of elements.

Upvotes: 0

Related Questions