Optimizing an "almost-increasing" array problem

Questions & Help Questions
, ,
1

Below, the problem specs:

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.

Note: sequence a0, a1, …, an is considered to be a strictly increasing if a0 < a1 < ... < an. Sequence containing only one element is also considered to be strictly increasing.

Example

  • For sequence = [1, 3, 2, 1], the output should be
    solution(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
    solution(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].

Input/Output

  • [execution time limit] 12 seconds (exs)
  • [input] array.integer sequenceGuaranteed constraints:
    2 ≤ sequence.length ≤ 105,
    -105 ≤ sequence[i] ≤ 105.
  • [output] booleanReturn true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

Okay, so I wrote this to solve it:

def solution(sequence) do
    iterate(sequence, 0)
end

def strictly_increasing?(list) do
    list == Enum.uniq(list) |> Enum.sort
end

def iterate(enumerable, index) do
    altered = List.delete_at(enumerable, index)
    cond do
        strictly_increasing?(altered) -> true
        index == length(altered) -> false
        true -> iterate(enumerable, index+1)
    end
end

The problem with my solution is that it works, but it times out on the “submit” tests. Is there any way to speed this up, or do I need to switch to a totally difference algorithm?