"Can a given array be made strictly increasing by removing one number?"

Question

The premise of the problem is that given an array of numbers, can you remove only one to make it a strictly increasing sequence?

• [1, 1, 1, 2, 3] would be false because if you remove one of the 1s the array would still start off non-increasing because of the other two remaining 1s before it increased.
• [1, 2, 3, 4, 99, 5, 10] would be true because you can remove the 99 and the remaining array [1, 2, 3, 4, 5, 10] would be strictly increasing.
• [1, 88, 2, 3, 4, 99, 5, 6] would be false because removing any number would still leave an array that would not strictly increase.

For [1, 1] it would return true because even though removing one of the 1s would only leave one 1 which by definition can't increase sequentially because it is only one thing, I did not write the problem and this is the response they wanted.

and so on....

My questions

I've clearly made this code too complex, but it does work. Below my code is the tests that I used to check it with the expected returns commented out next to each.

How can I refactor this code to simplify it? Is there a way to do this without using chunk_while?

def almost_increasing_sequence(sequence)
  array_of_arrays = sequence.chunk_while {|i, j| i < j}.to_a
  if array_of_arrays.length == 1
    puts true
  elsif array_of_arrays.length > 2
    puts false
  else
    if (array_of_arrays[0].last <=> array_of_arrays[1].first) == 1
      if (array_of_arrays[0][-2] <=> array_of_arrays[1][0]) == -1
        puts true
      elsif (array_of_arrays[0].last <=> array_of_arrays[1][1]) == -1
        puts true
      elsif (array_of_arrays[0][-2]) == nil
        puts true
      else
        puts false
      end
    else
      puts true
    end
  end
end

almost_increasing_sequence([1, 2, 3, 4, 99, 5, 6]) #true
almost_increasing_sequence([1, 3, 2]) #true
almost_increasing_sequence([10, 1, 2, 3, 4, 5]) #true
almost_increasing_sequence([0, -2, 5, 6]) #true
almost_increasing_sequence([1, 2, 3, 4, 3, 6]) #true
almost_increasing_sequence([1, 1]) #true
almost_increasing_sequence([100, 200, 300, 400, 99, 500, 600]) #true
almost_increasing_sequence([1, 2, 1, 2]) #false
almost_increasing_sequence([1, 2, 3, 4, 5, 3, 5, 6]) #false
almost_increasing_sequence([40, 50, 60, 10, 20, 30]) #false
almost_increasing_sequence([1, 3, 2, 1]) #false
almost_increasing_sequence([1, 4, 10, 4, 2] ) #false
almost_increasing_sequence( [1, 1, 1, 2, 3]) #false
almost_increasing_sequence([10, 1, 2, 3, 4, 5, 6]) #true
almost_increasing_sequence([5, 7, 8, 90, 91, 92, 93]) #true

Answer 1

All of the provided implementations fail for [2,3,1,2].

Here is a correct and efficient solution with \$O(n)\$ time complexity:

def almost_increasing_sequence?(sequence)
  return false if sequence.length  < 2
  return true  if sequence.length == 2

  max1 = sequence[0]  # maximum up to the previous item
  max2 = sequence[1]  # maximum up to the current item
  count = 0

  sequence[1..-1].each_with_index do |item, index|
    prev = sequence[index]
    nxt  = sequence[index+2]

    if prev >= item
      count += 1
      return false if count > 1
      if index > 0 and item <= max1 and nxt and nxt <= max2
        return false
      end
    end

    max1 = prev if prev > max1
    max2 = item if item > max2
  end

  return count == 1
end

---

Some tests courtesy of @AJFaraday (corrected & extended):

[
  [[], false],
  [[1], false],
  [[1, 2], true],
  [[1, 2, 3, 4, 99, 5, 6], true],
  [[1, 3, 2], true],
  [[10, 1, 2, 3, 4, 5], true],
  [[0, -2, 5, 6], true],
  [[1, 2, 3, 4, 3, 6], true],
  [[1, 1], true],
  [[100, 200, 300, 400, 99, 500, 600], true],
  [[1, 2, 1, 2], false],
  [[1, 2, 3, 4, 5, 3, 5, 6], false],
  [[40, 50, 60, 10, 20, 30], false],
  [[1, 3, 2, 1], false],
  [[1, 4, 10, 4, 2] , false],
  [[1, 1, 1, 2, 3], false],
  [[10, 1, 2, 3, 4, 5, 6], true],
  [[5, 7, 8, 90, 91, 92, 93], false],
  [[2,3,1,2], false],
  [[1,2,1,2], false],
  [[1, 2, 3, 4, 5, 3, 5, 6], false],
  [[40, 50, 60, 10, 20, 30], false]
].each do |array, expected|
  if almost_increasing_sequence?(array) != expected
    puts "FAIL Should get #{expected} for #{array}"
  else
    puts "PASS"
  end
end

Answer 2

I'm not completely sure I've interpreted the requirements correctly, but I think this should do it:

def almost_increasing_array?(array, tolerance)
  unmatched = 0
  array[1..-1].each_with_index do |item, index|
    unmatched += 1 if array[index] >= item
    return false if unmatched > tolerance
  end
  true
end

The tolerance is extra but it basically says this:

• Ignore the first item in the array
• For the rest, compare them to the previous item
• If the previous item was more than this, increment 'unmatched' count.
• If more than the tolerance didn't increase, false. It's not 'almost increasing'

It looks like it works for all cases.

almost_increasing_array?([1, 3, 5], 1) # true
almost_increasing_array?([5, 4, 3, 2, 1], 1) # false
almost_increasing_array?([1, 2, 5, 4], 1) # true (only one decrease)
almost_increasing_array?([1, 7, 5, 4], 1) # false (two decreases)
almost_increasing_array?([1, 7, 5, 4], 2) # true (two decreases, but we said that's okay)

You could easily simplify by removing the tolerance argument (hard coding 1).

def almost_increasing_array?(array)
  unmatched = 0
  array[1..-1].each_with_index do |item, index|
    unmatched += 1 if array[index] >= item
    return false if unmatched > 1
  end
  true
end

Weaknesses:

• This includes an array which is fully increasing, too.
• This will fail as soon as an issue is found, but it may run slowly on huge arrays where there's a decrease right at the end.

Strengths:

• It's pretty simple to understand.
• This doesn't even have to be an array, it'll work for an instance of any Ennumerable class. Such as ActiveRecord::Relation, or Hash.

Answer 3

I originally wrote a way over-complicated answer to this. For whatever reason I missed the much simpler solutions. AJFaraday, however, was a lot smarter about things, and posted a nice answer (go upvote that!).

In the meantime, my review of your code is unaffected:

• Your naming isn't too hot. array_of_arrays - well, yes, it is, but so are a lot of things. Given the method that created it, I'd just call it chunks.

• Your use of the comparison operator, <=>, is also pretty obtuse, when all you need is simple greater/less than comparisons.

• But my biggest beef with this code is that it prints its result directly. Just make it return a boolean instead; let something else handle the printing, since it's not rightly this method's responsibility. Its only responsibility should be to answer the question "can this array be 'fixed' to become an increasing sequence?".

The last bit would also make it a lot easier to test. Right now you're "testing" by reading the stdout. But it's kinda annoying trying to read true, false, true, true, etc. and trying to figure out if it matches a comment in the code. That's the sort of task computers are better at. So I'd recommend writing actual tests.

Now as mentioned, AJFaraday came up with a much simpler solution than I initially did. Still, I feel the same thing can be accomplished in a more Ruby-esque manner. Namely:

def almost_increasing_sequence?(array)
  breaks = array.each_cons(2).count { |a, b| a >= b }
  breaks <= 1
end

which basically says, "for every two consecutive elements, count the ones that aren't increasing (i.e. sequence breaks), and if that count ends up greater than 1, the sequence can't be 'fixed'".

AJFaraday also added a tolerance argument to the method; that too can be added here (and the method shortened while we're at it):

def almost_increasing_sequence?(array, tolerance = 1)
  array.each_cons(2).count { |a, b| a >= b } <= tolerance
end

The major difference, however, is that this will work its way through the entire array before delivering a verdict - even if the array can be deemed unfixable almost immediately.

An early return version can however be made, for instance by using #reduce to keep track of the sequence breaks without introducing a closure variable:

def almost_increasing_sequence?(array, tolerance = 1)
  array.each_cons(2).reduce(0) do |breaks, (a, b)|
    breaks += 1 if a >= b
    return false if breaks > tolerance
    breaks
  end
  true
end

---

My earlier answer included a section on testing, which I'll include here, since it's still relevant, regardless of the exact implementation (which is how tests should work). The only thing missing (as that came about after I'd written it), is the idea of a tolerance argument. Adding tests for that functionality is however left as an exercise to the reader.

For testing, there are a lot of good test frameworks in Ruby (and I highly encourage you to look into them!), but for something this simple it's quicker to write something yourself:

[
  [[1, 2, 3, 4, 99, 5, 6], true],
  [[1, 3, 2], true],
  [[10, 1, 2, 3, 4, 5], true],
  [[0, -2, 5, 6], true],
  [[1, 2, 3, 4, 3, 6], true],
  [[1, 1], true],
  [[100, 200, 300, 400, 99, 500, 600], true],
  [[1, 2, 1, 2], false],
  [[1, 2, 3, 4, 5, 3, 5, 6], false],
  [[40, 50, 60, 10, 20, 30], false],
  [[1, 3, 2, 1], false],
  [[1, 4, 10, 4, 2] , false],
  [[1, 1, 1, 2, 3], false],
  [[10, 1, 2, 3, 4, 5, 6], true],
  [[5, 7, 8, 90, 91, 92, 93], true]
].each do |array, expected|
  if almost_increasing_sequence?(array) != expected
    puts "FAIL Should get #{expected} for #{array}"
  else
    puts "PASS"
  end
end

Or, if you want, you can use minitest (included in Ruby's stdlib since 2.0) for more formal testing (I prefer the spec style, as I usually use RSpec, not minitest):

require 'minitest/autorun'

def almost_increasing_sequence?(array, tolerance = 1)
  # implementation here
end

describe 'almost_increasing_sequence?' do
  it 'returns true for an already increasing sequence' do
    almost_increasing_sequence?((1..10).to_a).must_equal true
  end

  it 'returns true for an empty sequence' do
    almost_increasing_sequence?([]).must_equal true
  end

  it 'returns true for a 1- or 2-element sequence' do
    almost_increasing_sequence?([1]).must_equal true
    almost_increasing_sequence?([100, 1]).must_equal true
  end

  it 'returns false for a "flat" sequence' do
    almost_increasing_sequence?([1] * 10).must_equal false
  end

  it 'returns false for a sequence with multiple "breaks"' do
    almost_increasing_sequence?([1, 99, 2, 99, 4]).must_equal false
  end

  it 'returns true if removing the greater side of the break fixes the sequence' do
    almost_increasing_sequence?([1, 99, 2, 3]).must_equal true
  end

  it 'returns true if removing the lesser side of the break fixes the sequence' do
    almost_increasing_sequence?([1, 2, 1, 3]).must_equal true
  end
end

Again, full specs aren't necessary, but writing it out helps break the problem down, rather than just staring at some example input and trying to figure out why it doesn't work.

---

Edit: Since I seem to be making a hash of this, here's my original method, which seems to pass all tests, however it still makes use of chunk_while, which, according to the comments, is a no-go for some reason:

def almost_increasing_sequence?(array)
  chunks = array.chunk_while(&:<).to_a

  return true if chunks.size < 2
  return false if chunks.size > 2

  head, tail = chunks

  return true if head.size == 1 || tail.size == 1

  head[-2] < tail.first || head.last < tail[1]
end

Answer 4

In my previous answer, I had misunderstood the requirement. As opposed to just deciding if the array decreased more than once, the requirement was to ask if there was only one item in the array which could be removed. Here's an updated solution:

def almost_increasing_array?(array)
  return true if array == array.sort
  index = 0
  removable = array.select do |item|
    temp_array = array.dup
    temp_array.delete_at(index)
    index += 1
    temp_array != temp_array.sort
  end
  (array.length - removable.length) >= 1
end

This collects the items in the array which, when removed, leave a sorted array behind.

If it's completely sorted, any item can be removed and the array is sorted.

If it's "almost sorted", one or more item will be removable, leaving behind a sorted array.

Tested with this code:

[
  [1,2,3,4],
  [1,2,1,2],
  [1, 2, 3, 4, 5, 3, 5, 6],
  [40, 50, 60, 10, 20, 30],
  [1,2,3,10,4,6, 10, 9]
].each do |input|
  puts input.inspect
  puts almost_increasing_array?(input)
end

It returns this result:

[1, 2, 3, 4]
true
[1, 2, 1, 2]
true
[1, 2, 3, 4, 5, 3, 5, 6]
true
[40, 50, 60, 10, 20, 30]
false
[1, 2, 3, 10, 4, 6, 10, 9]
false

It could actually be more descriptive in its output:

def how_sorted_is(array)
  return 'Fully sorted :D' if array == array.sort
  removable = array.each_index.select do |index|
    temp_array = array.dup
    temp_array.delete_at(index)
    temp_array != temp_array.sort
  end
  case (array.length - removable.length)
    when 0
      'Not sorted :('
    else #between 0 and the original length
      'Almost sorted :|'
  end
end

Result:

[1, 2, 3, 4]
Fully sorted :D
[1, 2, 1, 2]
Almost sorted :|
[1, 2, 3, 4, 5, 3, 5, 6]
Almost sorted :|
[40, 50, 60, 10, 20, 30]
Not sorted :(
[1, 2, 3, 10, 4, 6, 10, 9]
Not sorted :(