'How to get almost increasing sequence of integers

Given a sequence of integers as an array,i have to 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

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

The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

Here is what i have already tried , but it doesnt work for all situations

function almostIncreasingSequence(sequence) {
    for (var i = 0; i < sequence.length; i++) {
        if (sequence[i] > sequence[i + 1]) {
            sequence.splice(i, 1);
           return true;
        };
        return false;
    };
}

javascript

Solution 1:^[1]

Here is my answer

function almostIncreasingSequence(sequence) {
    if (isIncreasingSequence(sequence)) {
        return true;
    }



    for (var i = 0; i < sequence.length > 0; i++) {
        var tmpSequence = sequence.slice(0); // copy original array

        tmpSequence.splice(i, 1);
        if (isIncreasingSequence(tmpSequence)) {
            return true;
        }
    }

    return false;
}

function isIncreasingSequence(sequence) {
    for (var i = 0; i < sequence.length - 1; i++) {
        if (sequence[i] >= sequence[i + 1]) {
            return false;
        }
    }

    return true;
}

almostIncreasingSequence([1, 3, 2, 1]); // false
almostIncreasingSequence([1, 3, 2]); // true

Solution 2:^[2]

function almostIncreasingSequence(sequence) {
  var found = false;
  for (var i=0;i<sequence.length;i++) {
    if(sequence[i] <= sequence[i-1]) {
      if(found) {
        return false;
      }
      found = true;
      
      if(i === 1 || i + 1 === sequence.length) {
        continue;
      }
      else if (sequence[i] > sequence[i-2]) {
        sequence[i-1] = sequence[i-2];
      }
      else if(sequence[i-1] >= sequence[i+1]) {
        return false;
      }
    }
  }
  return true;
}

Solution 3:^[3]

Here is my solution.

First I look for a decreasing sequence. If none, then return true If there is a decreasing sequence inside the array, I create two more arrays excluding the two items in the decreasing sequence, and check those two new arrays. If one of them has no decreasing sequences, then return true, otherwise return false

function indexOfFail(sequence) {
    let index = null;
    for (let i = 0; i < sequence.length -1; i++) {
        if (sequence[i] >= sequence[i + 1]) {
            index = i;
            break;
        }
    }
    return index;
}

function almostIncreasingSequence(sequence) {

    let index = indexOfFail(sequence);
    if (index == null) return true;

    let tmp1 = sequence.slice(0);
    tmp1.splice(index, 1); //remove failed item
    if (indexOfFail(tmp1) == null) return true;
    
    let tmp2 = sequence.slice(0);
    tmp2.splice(index + 1, 1); //remove next item to failed item
    if (indexOfFail(tmp2) == null) return true;
    
    return false;

}

Solution 4:^[4]

function almostIncreasingSequence(seq) {
  var bad=0
  for(var i=1;i<seq.length;i++) if(seq[i]<=seq[i-1]) {
    bad++
    if(bad>1) return false
    if(seq[i]<=seq[i-2]&&seq[i+1]<=seq[i-1]) return false
  }
  return true
}

Solution 5:^[5]

I know post is old, but here is php solution to the problem

function almostIncreasingSequence($sequence){

$error = false;
$check_current_again = false;

for ($i = 0; $i + 1 < count($sequence); $i++) {
    $next = $i + 1;

    if($check_current_again){
        $i = $i - 1;            
    }

    $check_current_again = false;
    if($sequence[$i] >= $sequence[$next]){
        if($error){
            return false;
        }

        $error = true;

        if($i > 0 && $sequence[$i -1] >= $sequence[$i + 1]){
            $check_current_again = true;
        }
    }       
}
return true;

}

Solution 6:^[6]

Solution of a question:

function almostIncreasingSequence(sequence) {
  var inc = true;
  for (var i = 0; i < sequence.length; i++) {
    if (sequence[i] >= sequence[i + 1]) {
      if (inc) {
        inc = false;
      }
      else {
        return false;
      }
    }
  };
  return true;
}

console.log(almostIncreasingSequence([1, 3, 2, 1])); // false
console.log(almostIncreasingSequence([1, 3, 2])); // true

Solution 7:^[7]

I think sequence is not almost increasing if there is more than one number which is smaller than it's previous number:

function almostIncreasingSequence(sequence) {
    var found = 0;
    sequence.forEach((el, index) => {
        var next= sequence[index + 1] || Infinity;
        if (el >= next) {
            found++;
        }
    });
    return found <= 1;
}
console.log("1, 3, 2, 1: ", almostIncreasingSequence([1, 3, 2, 1]));
console.log("1, 3, 2: ", almostIncreasingSequence([1, 3, 2]));
console.log("1, 2, 5, 5, 5: ", almostIncreasingSequence([1, 2, 5, 5, 5]));

And even simpler and shorter with array.filter:

function almostIncreasingSequence(sequence) {
    return sequence.filter((it, index) => it >= (sequence[index + 1] || Infinity)).length <= 1;
}
console.log("1, 3, 2, 1: ", almostIncreasingSequence([1, 3, 2, 1]));
console.log("1, 3, 2: ", almostIncreasingSequence([1, 3, 2]));
console.log("1, 2, 5, 5, 5: ", almostIncreasingSequence([1, 2, 5, 5, 5]));
console.log("1, 2, 4, 5, 5: ", almostIncreasingSequence([1, 2, 4, 5, 5]));

Solution 8:^[8]

function Test(arr){
    var set_once = false;
    for (i=0; i<arr.length; i++){
        if(arr[i+1] <= arr[i]){
            if(!set_once){
                set_once = true;
                arr.splice(i+1,1);
                i = i-1;
                }else{
                 return false;
            }
        }
    }
    return true
}

Solution 9:^[9]

Algorithm: An almost increasing sequence can only have one number that is smaller than its previous number, and it must not equal than the number before its previous number. Also, the previous number must not equal to the number after the current number.

Illustration: Consider the following 4 numbers:

a, b, c, d

a and c must not equal to each other, so are b and d. We must nest this condition within (b > c) condition.

Actual JavaScript code:

const almostIncreasingSequence = seq => {
  let decrementCount = 0;

  for (let i = 1; i < seq.length - 1; i ++) {
    if (seq[i] <= seq[i - 1]) {
      decrementCount++;
      if (seq[i] <= seq[i - 2] && seq[i + 1] <= seq[i - 1]) {
        return false;
      }
    }
  }

  return decrementCount <= 1;
}

Solution 10:^[10]

Here is a solution in PHP

function almostIncreasingSequence($sequence) {
    $foundOne = false;

    for ($i = -1, $j = 0, $k = 1; $k < count($sequence); $k++) {
        $deleteCurrent = false;
        if ($sequence[$j] >= $sequence[$k])
        {
            if ($foundOne)
            {
                return false;
            }
            $foundOne = true;
            if ($k > 1 && $sequence[$i] >= $sequence[$k])
            {
                $deleteCurrent = true;
            }
        }
        if (!$foundOne)
        {
            $i = $j;
        }
        if (!$deleteCurrent)
        {
            $j = $k;
        }
    }
    return true;
}

Solution 11:^[11]

  static bool almostIncreasingSequence(int[] sequence)
    {
        int counter = 0;           
        if (sequence.Length <3)
            return true;

        int prevNo = sequence.Min() - 1;

        for (int i = 0; i < sequence.Length; i++)
        {
            if (counter < 2)
            {

                if (prevNo < sequence[i])
                    prevNo = sequence[i];
                else
                {
                    if (i == 0 || i == sequence.Length - 1)
                    {
                        counter += 1;
                    }
                    else if (i > 1)
                    {
                        if (sequence[i] <= sequence[i - 2])
                        {
                            if (prevNo < sequence[i + 1])
                            {
                                counter += 1;
                            }
                            else
                            {
                                counter += 2;
                            }

                        }
                        else
                        {
                            prevNo = sequence[i];
                            counter = counter + 1;
                        }
                    }
                   // {
                        if (i < sequence.Length - 2)
                        {
                            if (sequence[i] < sequence[i + 1])
                            {
                                counter = counter + 1;
                                prevNo = sequence[i];
                            }
                            else
                            {
                                counter += 1;
                            }
                        }
                 //   }


                    if (counter >= 2)
                        return false;
                }
            }

        }
        return true;

    }

Solution 12:^[12]

Here is a python3 implementation of the same. took me a while. not that clean of a code But take O(N) time and O(1) space so that's ok I guess.
In this case, I had used an approach where I maintained a counter variable and a pointer I increased the counter by 1 each time the sequence was not in an increasing fashion. and maintained a pointer to the index of the element which was out of sequence. if the counter had value more than 1 then the sequence is breaking at 2 points and it almost increasing sequence can not be achieved. if the sequence was already in place then the counter would be zero. the tricky part comes when the counter is 1 here we make use of the index variable which we maintained that is p if the c == 1 and the index is 0 or the length of sequence then the element which is breaking the sequence is at the start or end which can be removed to obtain an increasing sequence.

and if that's, not the case. we check for the adjacent values and they are breaking any order or not. if they are not breaking the order return True else its False. Hope I was able to help. Forgive the Bad indentation. I am new to the code editor at StackOverflow

def almostIncreasingSequence(sequence):
p = -1
c = 0
for i in range(1, len(sequence)):
    if sequence[i-1] >= sequence[i]:
        p = i
        c += 1
if c > 1:
    return False
if c == 0:
    return True

if p == n -1 or p == 1:
    return True

if sequence[p-1] < sequence[p+1] or sequence[p-2] < sequence[p]:
    return True
return False

Solution 13:^[13]

Here's an extremely dirty version of it. Lately, I've been trying to make solutions that are language agnostic, so that I don't become dependent on functions for problem solving, but learn them later for whatever language I specialize in.

Perhaps one of the dirtiest ways to do it, but time complexity is O(3N) = O(N). Space complexity is O(2N).

The logic comes from the fact that you only need to check for ONE missing element, so there is no need to do anything fancy, just save the index of that element and check the array without that element. Because sometimes you can run into another element being the issue (particularly in the case of duplicates), you should save the index of both problem elements.

Again, extremely dirty, but it passes all test cases and time constraints.

function almostIncreasingSequence(sequence) {
   let wrongindex = 0;
   let nextwrongindex = 0;
   for(let i = 0; i < sequence.length - 1; i++){
      if(sequence[i] >= sequence[i + 1]){
          wrongindex = i;
          nextwrongindex = i+1;
      }
   }
   let newArr = [];
   let newArr2 = [];
   for(let i = 0; i < sequence.length; i++){
    if(i != wrongindex){
     newArr.push(sequence[i]);
    }
   }
   
   for(let i = 0; i < sequence.length; i++){
    if(i != nextwrongindex){
     newArr2.push(sequence[i]);
    }
   }
   
   let isincreasingcount = 0;;
   
   for(let i = 0; i < newArr.length - 1; i++){
     if(newArr[i] >= newArr[i+1]){
         isincreasingcount++;
     }
   }
   
   for(let i = 0; i < newArr2.length -1; i++){
     if(newArr2[i] >= newArr2[i+1]){
         isincreasingcount++;
     }
   }
   if(isincreasingcount > 1){
       return false;
   }
   return true;
}

Solution 14:^[14]

$sequence = [0, -2, 6, 8] (Expected Output: true)
$sequence = [123, -17, -5, 1, 2, 12, 41, 45] (Expected Output: true)
$sequence = [10, 1, 2, 3, 4, 5, 6, 1] (Expected Output: false)
$sequence = [3, 5, 62, 98, 3] (Expected Output: true)
$sequence = [40, 49, 63, 10, 22, 30] (Expected Output: false)

This almostIncreasingSequence function will return the given Array is Increasing Sequence or not. You can try the above array examples.

print_r(almostIncreasingSequence($sequence));

function almostIncreasingSequence($sequence){

$found = 0;
$status = true;
for ($i=0;$i<sizeof($sequence);$i++) {
  if(($sequence[$i] <= @$sequence[$i-1]) && isset($sequence[$i-1])) {
    $found++;
    if($found > 1) $status = false; 
    if($sequence[$i] <= $sequence[$i-2] && $sequence[$i+1] <= $sequence[$i-1] && isset($sequence[$i+1])) $status = false;
  }      
}
return (($status == 0) ? $status : true);
}

Solution 15:^[15]

Just for the diversity. That's how I solved it.

function almostIncreasingSequence(sequence) {

    let failsSeq = new Array(sequence.length).fill(0);

    for(let i=0; i<sequence.length; i++) {
        if (sequence[i+1] && sequence[i] >= sequence[i+1]) {
            failsSeq[i] += 1;
            if (sequence[i+2] && sequence[i] >= sequence[i+2]) {
                failsSeq[i] += 1;
            }
            if (sequence[i-1] && sequence[i+1] && sequence[i-1]>=sequence[i+1]) {
                failsSeq[i] += 1;
            }
        }
    }
    
    const failsTotal = failsSeq.reduce( (acc, currValue) => acc + currValue);
    const failSingle = failsSeq.filter( (item) => item >= 2 ).length;
    
   
    if (failSingle === 1 && failsTotal === 2) {
        return true;
    }
    
    return failsTotal > 1 ? false : true;

}

Solution 16:^[16]

for eg 1,2,[5,3],6

We can solve this by 2 pointers, p2 will be ahead of p1 by 1 at the beginning. Once we found that, from the eg, 5 > 3, we need to skip each and check if the sequence is still valid, for that reason we call increasingSeq(), and skip 5 by (p1 -1). Then we skip 3 by (p2 + 1).

Once we skip those we start comparing the sequence again.

function almostIncreasingSequence(sequence) {
    if (sequence.length < 2) return true;
    let p1 = 0;
    let p2 = 1;

    while(p2 < sequence.length) {
        if (sequence[p1] >= sequence[p2]) {
            const a = increasingSeq(sequence, p1 - 1, p2);
            const b = increasingSeq(sequence, p1, p2 +1 )
            return a || b
        }
        p1 = p2;
        p2++
    }
    return true;
}

function increasingSeq(sequence, p1, p2) {
    while(p2 < sequence.length) {
        if (sequence[p1] >= sequence[p2]) return false;
        p1 = p2;
        p2++
    }
    return true;
}

Solution 17:^[17]

My Python3 answer:

O(n) time and O(1) space

def almostIncreasingSequence(sequence):
    
counter = 0

for idx in range(1, len(sequence)):
    
    # n is smaller or equal to n-1
    if sequence[idx] <= sequence[idx-1]:
        counter += 1
        
        # checking if index to be checked is within bounds
        if idx - 2 >= 0 and idx + 1 <= len(sequence)-1:
            # n is smaller or equal to n-1 and n+1 is smaller or equal to n-1
            print(sequence[idx], sequence[idx-2], sequence[idx+1], sequence[idx-1])
            if sequence[idx] <= sequence[idx-2] and sequence[idx+1] <= sequence[idx-1]:
                counter += 1
    print(counter)      
# return true if 1 or 0 in counter otherwise return false
return counter <= 1

Solution 18:^[18]

boolean almostIncreasingSequence(int[] sequence) {
int n = sequence.length;
if (n == 2)
{
    return true;
}
int count = 0;
boolean result = true;
for (int i = 0; i < sequence.length - 1; i++)
{

    if (sequence[i] >= sequence[i+1])
    {
        count++;
        if (i != 0 && sequence[i-1] >= sequence[i+1])
        {
            result = false;
        }
        if (i < n-2 && sequence[i] < sequence[i+2])
        {
            result = true;
        }
        if (i == n - 2)
        {
            result = true;
        }
    }              
}
return (count < 2 && result);

}

Solution 19:^[19]

Here is a complete working solution:

function almostIncreasingSequence($s) 
{
  $bad=0;
  
  for($i=1;$i<count($s);$i++)
  {
      if($s[$i]<=$s[$i-1]) $bad++;
  
      if($bad>1) return false;
      
      if(isset($s[$i+1]) && isset($s[$i-2]) && $s[$i]<=$s[$i-2] && $s[$i+1]<=$s[$i-1]) return false;
  }
  
  return true;
}

Solution 20:^[20]

This is my optimized solution with python:

def solution(sequence):
    if len(sequence) > 2:
        for i in range(len(sequence)-1):
            if sequence[i]>sequence[i+1]:
                news = sequence[:i]+sequence[i+1:]
                if news == sorted(news) and len(set(news)) == len(news):
                    return True
                else:
                    news = sequence[:i+1]+sequence[i+2:]
                    if news == sorted(news) and len(set(news)) == len(news):
                        return True
        return False
    else:
        return True

Solution 21:^[21]

I've checked out that most proposals fails with the new tests added to codeSignal. My approach is not quite optimal but it's easy to understand.

First, I store into a hashmap the problematic indexes (the current and the previous one). After that you can run simulations of the array without the problematic items. It just simply minimizes the brute force approach and it passes all the test even with high amount of items.

Time complexity: O(N+N) Space complexity: O(1)

Tests passed: 38/38. Sample tests: 19/19 Hidden tests: 19/19 Score: 300/300

Edited: I added a "break" after first problematic number encountered in order to just handle the first issue. So time complexity now is better.

bool almostIncreasingSequence(vector<int> sequence) {
    int length = sequence.size();
    if (length < 2) {
        return false;
    }
    
    // Store invalid indexes
    unordered_map<int, int> m;
    for(int i=1;i<length;++i) {        
        if (sequence[i-1] >= sequence[i]) {
            m[i-1]++;
            m[i]++;
            break; // new added
        }
    }
    // Scan invalid indexes
    for(auto it : m) {
        int prev = -1;
        int numInvalid = 0;
        const int id = it.first;

        // Simulate
        for(int i=0;i<length;++i) {
            if (id!=i) { // Do not add the problematic one
                if (prev != -1 && prev >= sequence[i]) {
                    ++numInvalid;
                    break;
                }
                prev = sequence[i];
            }
        }
        if (numInvalid == 0) {
            return true;
        }
    }
    return false;
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution	Source
Solution 1	Vasil Nikolov
Solution 2	Vipin PS
Solution 3	Carlos Ceriani
Solution 4	Vipin PS
Solution 5
Solution 6	ollazarev
Solution 7
Solution 8	Mohan
Solution 9	WebDeg Brian
Solution 10	hoangdv
Solution 11	Rose
Solution 12	Akash g krishnan
Solution 13
Solution 14
Solution 15	Janiis
Solution 16
Solution 17	Joao Henrique
Solution 18	mihsa
Solution 19	Ideatera Studios
Solution 20	Houda M
Solution 21

'How to get almost increasing sequence of integers

Solution 1:[1]

Solution 2:[2]

Solution 3:[3]

Solution 4:[4]

Solution 5:[5]

Solution 6:[6]

Solution 7:[7]

Solution 8:[8]

Solution 9:[9]

Solution 10:[10]

Solution 11:[11]

Solution 12:[12]

Solution 13:[13]

Solution 14:[14]

Solution 15:[15]

Solution 16:[16]

Solution 17:[17]

Solution 18:[18]

Solution 19:[19]

Solution 20:[20]

Solution 21:[21]