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

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

• The code does work, though I can see why you raised the exception to my question. I have edited my question to reflect the rules of this forum. Can it be released so I can learn how to code better? Mar 24 '17 at 14:04

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

• This is correct. They don't work for the array you suggest or [1, 2, 1, 2], [1, 2, 3, 4, 5, 3, 5, 6], and [40, 50, 60, 10, 20, 30]. Mar 27 '17 at 17:17
• @ReedMacConnell plz accept i added a working ruby example Mar 27 '17 at 23:18
• Thank you this works and it's a lot less complex than my original. Mar 29 '17 at 13:52

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.
• Doh, don't know why I made such a complicated answer. Your own code can actually be reduced to array.each_cons(2).count { |a, b| a >= b } <= tolerance (if we don't need to return early) Mar 25 '17 at 17:30
• @flambino perhaps, tho it might never be read again ;) Mar 25 '17 at 17:31
• Not sure I understand. What might never be read again? Mar 25 '17 at 17:32
• Well, I disagree. I'd much rather do that than mess around with explicit indices and block side-effects like incrementing a closed-over counter variable. It literally just says "for every two consecutive elements, count the ones that aren't increasing and compare to the given tolerance" Mar 25 '17 at 17:36
• @AjFaraday I appreciate your input, I've taken a lot from what you've put here. However, the implementations you've suggested don't work for [1,2,1,2], [1, 2, 3, 4, 5, 3, 5, 6], or [40, 50, 60, 10, 20, 30]. Mar 27 '17 at 17:13

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

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

end

• @Flamnino I appreciate your input, I've taken a lot from what you've put here. However, the implementations you've suggested don't work for [1,2,1,2], [1, 2, 3, 4, 5, 3, 5, 6], or [40, 50, 60, 10, 20, 30]. Mar 27 '17 at 17:15
• @ReedMacConnell wow, I am having no luck with this question, am I? Perhaps my first answer was better. I ran the current one through the tests I wrote, and thought I'd licked it, but apparently my tests aren't good enough Mar 27 '17 at 17:36
• This is from Codefights.com and is one of the early and presumably easier challenges. My code gets all the tests right when I run it locally, but it will not pass because I use the "chunk_while. I've been trying to figure out the better way to do this for weeks. Mar 27 '17 at 17:46
• @ReedMacConnell Hmm... yeah, I'm sure it's easy once you figure it out :) Incidentally, my original answer – which works, actually - also used chunk_while; made a lot of sense to use that Mar 27 '17 at 18:14

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 :(

• Horribly inefficient and still incorrect. Mar 27 '17 at 22:46
• @kyrill Is ther a case I've missed? Mar 27 '17 at 22:48
• Pretty much all that OP has mentioned in comment on your original answer. For example [1, 2, 1, 2]. Mar 27 '17 at 22:51
• They're literally included in the examples Mar 27 '17 at 22:52
• And the results are incorrect. Mar 27 '17 at 22:53