48

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].

My code:

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

But it can't pass all tests.

input: [1, 3, 2]
Output:false
Expected Output:true

Input: [10, 1, 2, 3, 4, 5]
Output: false
Expected Output: true

Input: [0, -2, 5, 6]
Output: false
Expected Output: true

input:  [1, 1]
Output: false
Expected Output: true

Input: [1, 2, 3, 4, 3, 6]
Output: false
Expected Output: true

Input: [1, 2, 3, 4, 99, 5, 6]
Output: false
Expected Output: true
3
  • On what sequence does this fail? I am wondering if the >= comparison should just be >. Should the sequence [1, 2, 2, 3] produce True?
    – lit
    Mar 25, 2017 at 14:12
  • it's always going to be false! look again at your method return Apr 10, 2017 at 0:13
  • 1
    It should be return c<=1.
    – Goh-shans
    Oct 23, 2020 at 3:28

30 Answers 30

57

Your algorithm is much too simplistic. You have a right idea, checking consecutive pairs of elements that the earlier element is less than the later element, but more is required.

Make a routine first_bad_pair(sequence) that checks the list that all pairs of elements are in order. If so, return the value -1. Otherwise, return the index of the earlier element: this will be a value from 0 to n-2. Then one algorithm that would work is to check the original list. If it works, fine, but if not try deleting the earlier or later offending elements. If either of those work, fine, otherwise not fine.

I can think of other algorithms but this one seems the most straightforward. If you do not like the up-to-two temporary lists that are made by combining two slices of the original list, the equivalent could be done with comparisons in the original list using more if statements.

Here is Python code that passes all the tests you show.

def first_bad_pair(sequence):
    """Return the first index of a pair of elements where the earlier
    element is not less than the later elements. If no such pair
    exists, return -1."""
    for i in range(len(sequence)-1):
        if sequence[i] >= sequence[i+1]:
            return i
    return -1

def almostIncreasingSequence(sequence):
    """Return whether it is possible to obtain a strictly increasing
    sequence by removing no more than one element from the array."""
    j = first_bad_pair(sequence)
    if j == -1:
        return True  # List is increasing
    if first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:
        return True  # Deleting earlier element makes increasing
    if first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:
        return True  # Deleting later element makes increasing
    return False  # Deleting either does not make increasing

If you do want to avoid those temporary lists, here is other code that has a more complicated pair-checking routine.

def first_bad_pair(sequence, k):
    """Return the first index of a pair of elements in sequence[]
    for indices k-1, k+1, k+2, k+3, ... where the earlier element is
    not less than the later element. If no such pair exists, return -1."""
    if 0 < k < len(sequence) - 1:
        if sequence[k-1] >= sequence[k+1]:
            return k-1
    for i in range(k+1, len(sequence)-1):
        if sequence[i] >= sequence[i+1]:
            return i
    return -1

def almostIncreasingSequence(sequence):
    """Return whether it is possible to obtain a strictly increasing
    sequence by removing no more than one element from the array."""
    j = first_bad_pair(sequence, -1)
    if j == -1:
        return True  # List is increasing
    if first_bad_pair(sequence, j) == -1:
        return True  # Deleting earlier element makes increasing
    if first_bad_pair(sequence, j+1) == -1:
        return True  # Deleting later element makes increasing
    return False  # Deleting either does not make increasing

And here are the tests I used.

print('\nThese should be True.')
print(almostIncreasingSequence([]))
print(almostIncreasingSequence([1]))
print(almostIncreasingSequence([1, 2]))
print(almostIncreasingSequence([1, 2, 3]))
print(almostIncreasingSequence([1, 3, 2]))
print(almostIncreasingSequence([10, 1, 2, 3, 4, 5]))
print(almostIncreasingSequence([0, -2, 5, 6]))
print(almostIncreasingSequence([1, 1]))
print(almostIncreasingSequence([1, 2, 3, 4, 3, 6]))
print(almostIncreasingSequence([1, 2, 3, 4, 99, 5, 6]))
print(almostIncreasingSequence([1, 2, 2, 3]))

print('\nThese should be False.')
print(almostIncreasingSequence([1, 3, 2, 1]))
print(almostIncreasingSequence([3, 2, 1]))
print(almostIncreasingSequence([1, 1, 1]))
8
  • This fails on sequence [1, 1, 1, 2, 3] Mar 31, 2017 at 16:39
  • 6
    My routine returns False for [1, 1, 1, 2, 3], just as it should. Removing one element from that list or leaving it as is leaves two consecutive 1s so the resulting list would not be increasing. Note that the question refers to "a strictly increasing sequence" so repeated elements are not allowed. I added more tests to my code after I posted the code you see and my routine passed all the tests. Interestingly, your list was one of the added tests. Mar 31, 2017 at 23:26
  • 1
    solid solution and excellent explanation, I also started with the simplistic algorithm above and couldn't quite make the leap to your solution.
    – user9903
    Sep 2, 2017 at 12:53
  • 2
    @JayM: I think it is better to work through a course or book on the subject. I have solved many problems then later saw that I had developed a special case of a standard algorithm, but I would not have seen the generalization myself. I also took much longer than if I had know the generalization. Of course, also solve some problems using those algorithms, so do both but start the book first. Aug 25, 2018 at 14:32
  • 1
    @HalfWebDev: I just checked, and all three of those test cases pass, as they should. In your first case, deleting the first 5 makes a strictly increasing list. In your second case, deleting the 99 does it, and in your third case, deleting the 123 does it. So they pass my code and they should pass. Why did you call them "failing test cases"? Dec 16, 2021 at 22:30
23

The solution is close to the intuitive one, where you check if the current item in the sequence is greater than the current maximum value (which by definition is the previous item in a strictly increasing sequence).

The wrinkle is that in some scenarios you should remove the current item that violates the above, whilst in other scenarios you should remove previous larger item.

For example consider the following:

[1, 2, 5, 4, 6]

You check the sequence at item with value 4 and find it breaks the increasing sequence rule. In this example, it is obvious you should remove the previous item 5, and it is important to consider why. The reason why is that the value 4 is greater than the "previous" maximum (the maximum value before 5, which in this example is 2), hence the 5 is the outlier and should be removed.

Next consider the following:

[1, 4, 5, 2, 6]

You check the sequence at item with value 2 and find it breaks the increasing sequence rule. In this example, 2 is not greater than the "previous" maximum of 4 hence 2 is the outlier and should be removed.

Now you might argue that the net effect of each scenario described above is the same - one item is removed from the sequence, which we can track with a counter.
The important distinction however is how you update the maximum and previous_maximum values:

  • For [1, 2, 5, 4, 6], because 5 is the outlier, 4 should become the new maximum.

  • For [1, 4, 5, 2, 6], because 2 is the outlier, 5 should remain as the maximum.

This distinction is critical in evaluating further items in the sequence, ensuring we correctly ignore the previous outlier.

Here is the solution based upon the above description (O(n) complexity and O(1) space):

def almostIncreasingSequence(sequence):
    removed = 0
    previous_maximum = maximum = float('-infinity')
    for s in sequence:
        if s > maximum:
            # All good
            previous_maximum = maximum
            maximum = s
        elif s > previous_maximum:
            # Violation - remove current maximum outlier
            removed += 1
            maximum = s
        else:
            # Violation - remove current item outlier
            removed += 1
        if removed > 1:
            return False
    return True

We initially set the maximum and previous_maximum to -infinity and define a counter removed with value 0.

The first test case is the "passing" case and simply updates the maximum and previous_maximum values.

The second test case is triggered when s <= maximum and checks if s > previous_maximum - if this is true, then the previous maximum value is the outlier and is removed, with s being updated to the new maximum and the removed counter incremented.

The third test case is triggered when s <= maximum and s <= previous_maximum - in this case, s is the outlier, so s is removed (no changes to maximum and previous_maximum) and the removed counter incremented.

One edge case to consider is the following:

[10, 1, 2, 3, 4]

For this case, the first item is the outlier, but we only know this once we examine the second item (1). At this point, maximum is 10 whilst previous_maximum is -infinity, so 10 (or any sequence where the first item is larger than the second item) will be correctly identified as the outlier.

2
  • 1
    I love this solution. It fits how I was thinking about the problem, but I started using None instead of -inf which made the conditions way harder to reason about. May 9, 2022 at 21:30
  • its much simpler. I like this solution too Aug 27, 2022 at 11:03
7

This is mine. Hope you find this helpful:

def almostIncreasingSequence(sequence):

    #Take out the edge cases
    if len(sequence) <= 2:
        return True

    #Set up a new function to see if it's increasing sequence
    def IncreasingSequence(test_sequence):
        if len(test_sequence) == 2:
            if test_sequence[0] < test_sequence[1]:
                return True
        else:
            for i in range(0, len(test_sequence)-1):
                if test_sequence[i] >= test_sequence[i+1]:
                    return False
                else:
                    pass
            return True

    for i in range (0, len(sequence) - 1):
        if sequence[i] >= sequence [i+1]:
            #Either remove the current one or the next one
            test_seq1 = sequence[:i] + sequence[i+1:]
            test_seq2 = sequence[:i+1] + sequence[i+2:]
            if IncreasingSequence(test_seq1) == True:
                return True
            elif IncreasingSequence(test_seq2) == True:
                return True
            else:
                return False
0
7

Here's my simple solution

def almostIncreasingSequence(sequence):
    removed_one = False
    prev_maxval = None
    maxval = None
    for s in sequence:
        if not maxval or s > maxval:
            prev_maxval = maxval
            maxval = s
        elif not prev_maxval or s > prev_maxval:
            if removed_one:
                return False
            removed_one = True
            maxval = s
        else:
            if removed_one:
                return False
            removed_one = True
    return True
1
  • 1
    Best space and time complexity solution. Thanks! Aug 8, 2021 at 17:07
6

The reason why your modest algorithm fails here (apart from the missing '=' in return) is, it's just counting the elements which are greater than the next one and returning a result if that count is more than 1.

What's important in this is to look at the list after removing one element at a time from it, and confirm that it is still a sorted list.

My attempt at this is really short and works for all scenario. It fails the time constraint on the last hidden test set alone in the exercise.

enter image description here

As the problem name suggests, I directly wanted to compare the list to its sorted version, and handle the 'almost' case later - thus having the almostIncreasingSequence. i.e.:

if sequence==sorted(sequence):
   .
   .

But as the problem says:

determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array (at a time).

I started visualizing the list by removing an element at a time during iteration, and check if the rest of the list is a sorted version of itself. Thus bringing me to this:

for i in range(len(sequence)):
    temp=sequence.copy()
    del temp[i]
    if temp==sorted(temp):
        .
        .

It was here when I could see that if this condition is true for the full list, then we have what is required - an almostIncreasingSequence! So I completed my code this way:

def almostIncreasingSequence(sequence):
    t=0
    for i in range(len(sequence)):
        temp=sequence.copy()
        del temp[i]
        if temp==sorted(temp):
            t+=1
    return(True if t>0 else False)

This solution still fails on lists such as [1, 1, 1, 2, 3]. As @rory-daulton noted in his comments, we need to differentiate between a 'sorted' and an 'increasingSequence' in this problem. While the test [1, 1, 1, 2, 3] is sorted, its on an increasingSequence as demanded in the problem. To handle this, following is the final code with a one line condition added to check for consecutive same numbers:

def almostIncreasingSequence(sequence):
    t=0
    for i in range(len(sequence)):
        temp=sequence.copy()
        del temp[i]
        if temp==sorted(temp) and not(any(i==j for i,j in zip(sorted(temp), sorted(temp)[1:]))):
            t+=1
    return t>0

As this still fails the execution time limit on the last of the test (the list must be really big), I am still looking if there is a way to optimize this solution of mine.

0
4
def almostIncreasingSequence(sequence):
    if len(sequence) == 1:
        return True
    
    decreasing = 0
    for i in range(1,len(sequence)):
        if sequence[i] <= sequence[i-1]:
            decreasing +=1
            if decreasing > 1:
                return False
        
        if sequence[i] <= sequence[i-2] and i-2 >=0:
            if i != len(sequence)-1 and sequence[i+1] <= sequence[i-1]:
                return False
    return True
1
  • 1
    Hello and welcome to SO! While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. Please read the tour, and How do I write a good answer? Please also note that there are many other answers to this question. If your answer is included in one of them please consider to delete it and upvote the existing. Jan 6, 2021 at 7:35
3

There are two possibilities whenever you hit the condition of the sequence[i-1]>=sequence[i]

  • Delete index i-1
  • Delete index i

So my idea was to create copy and delete the indexes and check if they are sorted and then at the end you can do the or and return if the ans is attainable. Complexity will be O(N2)[because of del] and space O(N)

def almostIncreasingSequence(sequence):
    c0,c1=1,1
    n=len(sequence)
    l1=[]
    l2=[]
    for i in sequence:
        l1.append(i)
        l2.append(i)
    for i in range(1,n):
        if sequence[i-1]>=sequence[i]:
            del l1[i]
            del l2[i-1]
            break
    for i in range(1,n-1):
        if l1[i-1]>=l1[i]:
            c0=0
            break
    for i in range(1,n-1):
        if l2[i-1]>=l2[i]:
            c1=0
            break
    return bool(c0 or c1)

This is accepted solution.

2
  • Curious why you iterate over sequence to make copies? Is l1=sequence[:] less efficient?
    – Ian Atkin
    Jan 30, 2020 at 5:07
  • You can also do that, at that time maybe I was thinking to do some experiment but at the end avoided it.
    – Amit Singh
    Jan 31, 2020 at 15:49
2

I'm still working on mine. Wrote it like this but I can't pass the last 3 hidden tests.

def almostIncreasingSequence(sequence):

boolMe = 0
checkRep = 0

for x in range(0, len(sequence)-1):

    if sequence[x]>sequence[x+1]:
        boolMe = boolMe + 1
        if (x!=0) & (x!=(len(sequence)-2)):
            if sequence[x-1]>sequence[x+2]:
                boolMe = boolMe + 1
    if sequence.count(sequence[x])>1:
        checkRep = checkRep + 1

    if (boolMe > 1) | (checkRep > 2):    
        return False
return True
1
  • cant pass those last 4 hidden tests, performance fails, i think the list is large and im On^2
    – rashid
    May 3, 2019 at 6:41
2

Here is a solution in Java.

boolean almostIncreasingSequence(int[] sequence) {

    int count = 0;

    for(int i=1; i< sequence.length; i++){
      if(sequence[i] <= sequence[i-1]){
         count++;
         
         if( i > 1 && i < sequence.length -1  
             && sequence[i] <= sequence[i-2] 
             && sequence[i+1] <= sequence[i-1] )
         {
            count++;
         }
      }
  }

    return count <= 1;
}
1

This was a pretty cool exercise.

I did it like this:

def almostIncreasingSequence(list):
  removedIdx = []                   #Indexes that need to be removed

  for idx, item in enumerate(list):
    tmp = []                        #Indexes between current index and 0 that break the increasing order
    for i in range(idx-1, -1, -1):
      if list[idx]<=list[i]:        #Add index to tmp if number breaks order
        tmp.append(i)
    if len(tmp)>1:                  #If more than one of the former numbers breaks order  
      removedIdx.append(idx)        #Add current index to removedIdx
    else:
      if len(tmp)>0:                #If only one of the former numbers breaks order
        removedIdx.append(tmp[0])   #Add it to removedIdx
  return len(set(removedIdx))<=1

print('\nThese should be True.')
print(almostIncreasingSequence([]))
print(almostIncreasingSequence([1]))
print(almostIncreasingSequence([1, 2]))
print(almostIncreasingSequence([1, 2, 3]))
print(almostIncreasingSequence([1, 3, 2]))
print(almostIncreasingSequence([10, 1, 2, 3, 4, 5]))
print(almostIncreasingSequence([0, -2, 5, 6]))
print(almostIncreasingSequence([1, 1]))
print(almostIncreasingSequence([1, 2, 3, 4, 3, 6]))
print(almostIncreasingSequence([1, 2, 3, 4, 99, 5, 6]))
print(almostIncreasingSequence([1, 2, 2, 3]))

print('\nThese should be False.')
print(almostIncreasingSequence([1, 3, 2, 1]))
print(almostIncreasingSequence([3, 2, 1]))
print(almostIncreasingSequence([1, 1, 1]))
print(almostIncreasingSequence([1, 1, 1, 2, 3]))
1

With Python3, I started with something like this...

def almostIncreasingSequence(sequence):
    for i, x in enumerate(sequence):
        ret = False
        s = sequence[:i]+sequence[i+1:]
        for j, y in enumerate(s[1:]):
            if s[j+1] <= s[j]:
                ret = True
                break
            if ret:
                break
        if not ret:
            return True
    return False

But kept timing out on Check #29.

I kicked myself when I realized that this works, too, but still times out on #29. I have no idea how to speed it up.

def almostIncreasingSequence(sequence):
    for i, x in enumerate(sequence):    
        s = sequence[:i]
        s.extend(sequence[i+1:])
        if s == sorted(set(s)):
            return True
    return False
1

Well, here's also my solution, I think it's a little bit cleaner than other solutions proposed here so I'll just bring it below.

What it does is it basically checks for an index in which i-th value is larger than (i+1)-th value, if it finds such an index, checks whether removing any of those two makes the list into an increasing sequence.

def almostIncreasingSequence(sequence):

    def is_increasing(lst):
        for idx in range(len(lst)-1):
            if lst[idx] >= lst[idx + 1]:
                return False
        return True

    for idx in range(len(sequence) - 1):
        if sequence[idx] >= sequence[idx + 1]:
            fixable = is_increasing([*sequence[:idx], *sequence[idx+1:]]) or is_increasing([*sequence[:idx+1], *sequence[idx+2:]])
            if not fixable:
                return False

    return True
2
  • really liked it. Can you tell me one thing - [*sequence[:idx], *sequence[idx+1:]] Is this list concatenation with the use of " * " and " , " like ' + ' operator on list?
    – pragun
    May 6, 2019 at 9:24
  • 1
    @pragun Yeah, it's called the unpack operator and well in this use case, works exactly as + would have. Also notice that variable unpacking outside of function calls is supported in python 3+ and this line would fail in python2.*
    – SpiXel
    May 7, 2019 at 8:42
1

C++ Answer with looping array only once

bool almostIncreasingSequence(std::vector<int> a) 
{
    int n=a.size(), p=-1, c=0;
    
    for (int i=1;i<n;i++)
      if (a[i-1]>=a[i]) 
        p=i, c++;
    
    if (c>1) return 0;
    if (c==0) return 1;
    if (p==n-1 || p==1) return 1;
    if (a[p-1] < a[p+1]) return 1;
    if (a[p-2] < a[p]) return 1;
    return 0;
}
1

I worked on this problem using JavaScript, the idea is to find the breakpoints where the sequence is not strictly increasing, from [0, ..., x - 1] and [x, ..., n.length - 1]. If there are more than 1 breakpoint, then return false.

Once I am able to locate the break point, just check the combination both [0, ..., x - 1, x + 1, ..., n.length - 1] and [0, ..., x - 2, x, ..., n.length - 1], to check whether breakpoint existed in those 2 arrays. It can be simplified to check 2 pairs of points also.

Here is my solution:

function almostIncreasingSequence(sequence) {
  const breakpoints = findBreak(sequence);

  if (breakpoints.length === 0) return true;
  if (breakpoints.length > 1) return false;

  const removedSeq = sequence
    .slice(0, breakpoints[0])
    .concat(sequence.slice(breakpoints[0] + 1, sequence.length));

  const removedSeq2 = sequence
    .slice(0, breakpoints[0] - 1)
    .concat(sequence.slice(breakpoints[0], sequence.length));

  return (
    findBreak(removedSeq).length === 0 || findBreak(removedSeq2).length === 0
  );
}

const findBreak = (sequence) => {
  const breakpoints = [];
  for (let i = 1; i < sequence.length; i++) {
    if (sequence[i] <= sequence[i - 1]) {
      breakpoints.push(i);
    }
  }
  return breakpoints;
};
1

Here is the solution for javascript, take those principles and convert them to the desired lang. It makes two array copies (sequence1, sequence2) and checks several things for both:

  1. sequence1 - deletes one or more next array items where the next item is smaller than the former item. Then it counts number of deletions (iterator1).

  2. sequence2 - deletes one or more former array items where the former item is bigger than the next item. Then it counts number of deletions (iterator2).

  3. checks separately for both arrays sequence1 and sequence2 if they have duplicated item which will set separate result flags to false (bigger1, bigger2)

  4. check to see whether any of the two arrays (sequence1, sequence2) pass the criteria to be valid. If yes return true for that array and end program. Criteria for checking is: number of deletions of items from the array in question cannot be larger than 1, and there should be no duplicated items (bigger1, bigger2). If there are duplicates it means that two number are the same thus one is not bigger than another one.

However, for some reason testing page almostincreasingSequence at Codesignal (test 12) returns the array [1, 1] to be true which is not correct because the criteria they have been describing says that the next number has to be strictly bigger than the former one, not equal to it. I have made the code according to their written criteria (next number has to be bigger, not equal to).

Code:

function solution(sequence) {
  let iterator1 = 0;
  let iterator2 = 0;
  let bigger1 = true;
  let bigger2 = true;
  let sequence1 = sequence.slice(); // copy of the orig array
  let sequence2 = sequence.slice();

  for (let i = 0; i < sequence1.length; i++) {
    if (typeof sequence1[i+1] !== 'undefined' && sequence1[i+1] < sequence1[i]) {
      sequence1.splice(i+1, 1);  // delete number
      iterator1++;  // count number of deletions
      i = -1; continue;  // restart for loop from i = 0
    }
  }
  
  for (let i = 0; i < sequence2.length; i++) {
    if (typeof sequence2[i+1] !== 'undefined' && sequence2[i] > sequence2[i+1]) {
      sequence2.splice(i, 1);
      iterator2++;
      i = -1; continue;
    }
  }
      
  for (let i = 0; i < sequence1.length; i++) {
    for (let k = i + 1; k < sequence1.length; k++) {
      if (sequence1[i] == sequence1[k]) {  // if two numbers are equal..
          bigger1 = false;  // one is not bigger than another - false
      }
    }
  }
  
  for (let i = 0; i < sequence2.length; i++) {
    for (let k = i + 1; k < sequence2.length; k++) {
      if (sequence2[i] == sequence2[k]) {
          bigger2 = false;
      }
    }
  }
  
  if (iterator1 < 2 && bigger1 == true) {
    return true;
  } else if (iterator2 < 2 && bigger2 == true) {
    return true;
  } else {
    return false;
  }

}

/* Sample tests */ 
let arr = [1, 2, 1, 2];  // false
//let arr = [3, 6, 5, 8, 10, 20, 15];  // false
//let arr = [1, 3, 2, 1];  // false
//let arr = [1, 3, 2];  // true
//let arr = [10, 1, 2, 3, 4, 5];  // true
//let arr = [1, 2, 1, 3, 2];  // false
//let arr = [1, 1, 2, 3, 4, 4];  // false
//let arr = [1, 4, 10, 4, 2];  // false
//let arr = [1, 1, 1, 2, 3];  // false
//let arr = [0, -2, 5, 6];  // true
//let arr = [1, 2, 3, 4, 5, 3, 5, 6];  // false
//let arr = [40, 50, 60, 10, 20, 30];  // false
//let arr = [1, 1]; // false 
//let arr = [1, 2, 5, 3, 5];  // true
//let arr = [1, 2, 5, 5, 5];  // false
//let arr = [10, 1, 2, 3, 4, 5, 6, 1];  // false
//let arr = [1, 2, 3, 4, 3, 6];  // true (Test 16)
//let arr = [1, 2, 3, 4, 99, 5, 6];  // true
//let arr = [123, -17, -5, 1, 2, 3, 12, 43, 45];  // true
//let arr = [3, 5, 67, 98, 3];  // true

solution(arr);

But if you want code to pass criteria despite of their instructions, thus to allow numbers to be equal like [1, 1] = true and not strictly next number bigger than former one, then solution would be this:

function solution(sequence) {
  let iterator1 = 0;
  let iterator2 = 0;
  let sequence1 = sequence.slice();
  let sequence2 = sequence.slice();

  for (let i = 0; i < sequence1.length; i++) {
    if (typeof sequence1[i+1] !== 'undefined' && sequence1[i+1] <= sequence1[i]) {
      sequence1.splice(i+1, 1);
      iterator1++;
      i = -1; continue;
    }
  }
  
  for (let i = 0; i < sequence2.length; i++) {
    if (typeof sequence2[i+1] !== 'undefined' && sequence2[i] >= sequence2[i+1]) {
      sequence2.splice(i, 1);
      iterator2++;
      i = -1; continue;
    }
  }
    
  if (iterator1 < 2) {
    return true;
  } else if (iterator2 < 2) {
    return true;
  } else {
    return false;
  }

}
0
boolean almostIncreasingSequence(int[] sequence) {
    int length = sequence.length;
    if(length ==1) return true;
    if(length ==2 && sequence[1] > sequence[0]) return true;
    int count = 0;
    int index = 0;
    boolean iter = true;

    while(iter){
        index = checkSequence(sequence,index);
        if(index != -1){
            count++;
            index++;
            if(index >= length-1){
                iter=false;
            }else if(index-1 !=0){
                if(sequence[index-1] <= sequence[index]){
                    iter=false;
                    count++;
                }else if(((sequence[index] <= sequence[index-2])) && ((sequence[index+1] <= sequence[index-1]))){
                    iter=false;
                    count++;                    
                }
            }
        }else{
            iter = false;
        }
    }
    if(count > 1) return false;
    return true;
}

 int checkSequence(int[] sequence, int index){
    for(; index < sequence.length-1; index++){
        if(sequence[index+1] <= sequence[index]){
            return index; 
        }
    }
    return -1;
}
1
  • The same with me but it can not pass the execution duration at test case 36!
    – kidnan1991
    May 18, 2019 at 16:24
0

Below is the Python3 code that I used and it worked fine:

def almostIncreasingSequence(sequence):
flag = False

if(len(sequence) < 3):
    return True

if(sequence == sorted(sequence)):
    if(len(sequence)==len(set(sequence))):
        return True

bigFlag = True
for i in range(len(sequence)):
    if(bigFlag and i < len(sequence)-1 and sequence[i] < sequence[i+1]):
        bigFlag = True
        continue
    tempSeq = sequence[:i] + sequence[i+1:]
    if(tempSeq == sorted(tempSeq)):
        if(len(tempSeq)==len(set(tempSeq))):
            flag = True
            break
    bigFlag = False
return flag
0
0

This works on most cases except has problems with performance.

def almostIncreasingSequence(sequence):
    if len(sequence)==2:
        return sequence==sorted(list(sequence))
    else:
        for i in range(0,len(sequence)):
            newsequence=sequence[:i]+sequence[i+1:]
            if (newsequence==sorted(list(newsequence))) and len(newsequence)==len(set(newsequence)):
                return True
                break
            else:
                result=False
    return result
1
0

This is my Solution,

def almostIncreasingSequence(sequence):

def hasIncreasingOrder(slicedSquence, lengthOfArray):
    count =0
    output = True
    while(count < (lengthOfArray-1)) :
        if slicedSquence[count] >= slicedSquence[count+1] :
            output = False
            break
        count = count +1
    return output

count = 0
seqOutput = False
lengthOfArray = len(sequence)
while count < lengthOfArray:
    newArray = sequence[:count] + sequence[count+1:] 
    if hasIncreasingOrder(newArray, lengthOfArray-1):
        seqOutput = True
        break
    count = count+1
return seqOutput
0

This one works well.

bool almostIncreasingSequence(std::vector<int> sequence) {
/*
if(is_sorted(sequence.begin(), sequence.end())){
    return true;
    }
*/
int max = INT_MIN;
int secondMax  = INT_MIN;
int count = 0;
int i = 0;

while(i < sequence.size()){
    if(sequence[i] > max){
        secondMax = max;
        max = sequence[i];

}else if(sequence[i] > secondMax){
        max = sequence[i];
        count++;
        cout<<"count after increase = "<<count<<endl;
    }else {count++; cout<<"ELSE count++ = "<<count<<endl;}


    i++;
}

return count <= 1;


}
0
def almostIncreasingSequence(sequence):
    if len(sequence) == 1:
        return False
    if len(sequence) == 2:
        return True
    c = 0
    c1 = 0
    for i in range(1,len(sequence)):
        if sequence[i-1] >= sequence[i]:
            c += 1
        if i != 0 and i+1 < len(sequence):
            if sequence[i-1] >= sequence[i+1]:
                c1 += 1
        if c > 1 or c1 > 1:
            return False
    return c1 == 1 or c == 1
0

this is mine and it runs fine. I just remove suggested elements and see if new list is strictly increasing

To check if a list is strictly increasing. I check if there are any duplicates first. I then check if the sorted list is the same as the original list

import numpy as np

def IncreasingSequence(sequence):
    temp=sequence.copy()
    temp.sort()
    if (len(sequence) != len(set(sequence))):
        return False
    if (sequence==temp):
        return True
    
    return False
def almostIncreasingSequence(sequence):

    for i in range(len(sequence)-1):
        if sequence[i] >= sequence[i+1]:
            sequence_temp=sequence.copy()
            sequence_temp.pop(i)
            # print(sequence_temp)
            # print(IncreasingSequence(sequence_temp))
            if (IncreasingSequence(sequence_temp)):
                return True
            # Might be the neighbor that is worth removing
            sequence_temp=sequence.copy()
            sequence_temp.pop(i+1)
            if (IncreasingSequence(sequence_temp)):
                return True
    
    return False
0

I spent a whole day trying to make it as short as possible, but no luck. But here is my accepted answer in CodeSignal.

def almostIncreasingSequence(sequence):
    if len(sequence)<=2:
        return True
    
    def isstepdown(subsequence):
        return [a>=b for a,b in zip(subsequence, subsequence[1:])]
    
    stepdowns = isstepdown(sequence)
    n_stepdown = sum(stepdowns)
    if n_stepdown>1:
        return False
    else:
        sequence2 = sequence.copy()
        
        sequence.pop(stepdowns.index(True))
        stepdowns_temp = isstepdown(sequence)
        n_stepdown = sum(stepdowns_temp)

        sequence2.pop(stepdowns.index(True)+1)
        stepdowns_temp = isstepdown(sequence2)
        n_stepdown += sum(stepdowns_temp)   
        if n_stepdown<=1:
            return True
        else:
            return False
0

Here is another solution. Passes all the tests. Just one method. One pass through the list.

def almostIncreasingSequence(sequence):

count = 0

if len(sequence) < 3:
    return True
for i in range(1, len(sequence) - 2): #to test only inner elements
    if (sequence[i] >= sequence[i+1]): 
        count += 1
        if count == 2:  # the second time this occurs
            return False
        #check if skipping one of these items solves the problem
        if sequence[i-1] >= sequence[i+1] and sequence[i] >= sequence[i+2]:
            return False
        i += 1
#handle the first element
if sequence[0] >= sequence[1]:
    count += 1
    if count == 2:
        return False
#handle the last element
if sequence[-2] >= sequence[-1] and count == 1:
    return False            
return True 
0

Works on CodeSignal test cases

def almostIncreasingSequence(sequence): s = sequence # for ease

prevMax = s[0] # stores previous max value to which current element has to be compared
found = False
maxI = 0 #index of prevMax
for i in range(1, len(s)):
    if s[i] <= prevMax:
        if found:
            return False
        else:
            found = True
            if maxI > 0 : #checks if current item is smaller thant the prevMax and the value before that 
                if s[i] <= s[maxI] and s[i] > s[maxI - 1]:
                    prevMax = s[i]
                    maxI = i
            else: # checks if the current and next element are smaller than the prevMax value
                if (i+1) < len(s) and s[i+1] <= s[maxI]:
                    prevMax = s[i]
                    maxI = i
    else:
        prevMax = s[i]
        maxI = i

return True
0

This is my solution.

    def almostIncreasingSequence(sequence):
        duplicated = 0
        for i in range(1, len(sequence) - 1):
            if sequence[i-1] == sequence[i] == sequence[i+1]:
                return False
            elif sequence[i-1] == sequence[i]:
                duplicated += 1
            elif sequence[i] == sequence[i+1]:
                duplicated += 1
            elif sequence[i-1] <= sequence[i] <= sequence[i+1]:
                continue
            else:
                return False
        return 0 <= duplicated <= 1
0

My solution (in Kotlin) passed all test cases in CodeSignal as well as performance:

fun isStrictlyIncreasing(sequence: MutableList<Int>): Int {
    for (i in 0 .. sequence.size - 2) {
        if (sequence[i] >= sequence[i + 1]) {
            return i
        }
    }
    return -1
}

fun solution(sequence: MutableList<Int>): Boolean {
    var j = isStrictlyIncreasing(sequence)
    if (j == -1) return true
    
    val seq = sequence.toMutableList()
    seq.removeAt(j)
    if (isStrictlyIncreasing(seq) == -1)
        return true
        
    val seq2 = sequence.toMutableList()
    seq2.removeAt(j + 1)
    if (isStrictlyIncreasing(seq2) == -1)
        return true 
    return false
}
0

I was fairly happy with my solution. Seemed very readable and concise, however it fails the execution tests. Posting here as I hadn't seen anyone else really take this type of approach to the problem. Was hoping that the map function would be faster than many of the for loop answers already posted. Any comments or feedback are greatly appreciated.

def strictly_increasing_test(sequence):
return sequence == sorted(list(set(sequence)))
    
def test_sequence(sequence, x):
    new = sequence[:]
    new.pop(x)
    return new

def solution(sequence):
    testSequences = map(lambda x: test_sequence(sequence, x), range(len(sequence)))
    tests = set(map(strictly_increasing_test, testSequences))
    return any(tests)
0
// Java program for the above approach
class Sequence{

// Function to find if is it possible
// to make the array strictly increasing
// by removing at most one element
public static boolean check(int arr[], int n)
{
    
    // Stores the count of numbers that
    // are needed to be removed
    int count = 0;

    // Store the index of the element
    // that needs to be removed
    int index = -1;

    // Traverse the range [1, N - 1]
    for(int i = 1; i < n; i++) 
    {
        
        // If arr[i-1] is greater than
        // or equal to arr[i]
        if (arr[i - 1] >= arr[i])
        {
            
            // Increment the count by 1
            count++;

            // Update index
            index = i;
        }
    }

    // If count is greater than one
    if (count > 1)
        return false;

    // If no element is removed
    if (count == 0)
        return true;

    // If only the last or the
    // first element is removed
    if (index == n - 1 || index == 1)
        return true;

    // If a[index] is removed
    if (arr[index - 1] < arr[index + 1])
        return true;

    // If a[index - 1] is removed
    if (index - 2 >= 0 && arr[index - 2] < arr[index])
        return true;
    
    // if there is no element to compare
    if(index < 0)
        return true;

    return false;
}

// Driver Code
public static void main(String args[])
{
    int []arr = { 1, 2, 5, 3, 5 };
    int N = arr.length;
    
    if (check(arr, N))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
-1

Swift

//Brute Force //Running Time: O(n * n)

func isIncreasing(sequence: [Int]) -> Bool {
  if sequence.count == 1 { return true }
  
  var isStrictlyIncreasing = false
  
for (indexOfPotentialNumberToRemove) in 0...sequence.count - 1 {
      
    print("indexOfPotentialNumberToRemove: \(indexOfPotentialNumberToRemove)")
  
    if isStrictlyIncreasing { return true }
    var remainingArray =  sequence
    remainingArray.remove(at: indexOfPotentialNumberToRemove)
    
    isStrictlyIncreasing = true
    for i in 0...remainingArray.count - 1 {
        if i + 1 < remainingArray.count {
            let currentNumber = remainingArray[i]
            let nextNumber = remainingArray[i + 1]
            if nextNumber <= currentNumber {
                isStrictlyIncreasing = false
                break
            }
            
        }
    }
    
  }
  
  return isStrictlyIncreasing
  

}

0

Not the answer you're looking for? Browse other questions tagged or ask your own question.