# Optimizing an "almost-increasing" array problem

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?

Try doing it with recursion, checking each pair (or the one before if you’re skipping this one), rather than checking the entire array every iteration.

1 Like

``````defmodule Example do
@remove_limit 1

# function head for a default argument
def sample(list, removed_so_far \\ 0)

# check if we have reached a remove limit
def sample(_list, removed_so_far) when removed_so_far > @remove_limit, do: false

# if a limit is not reached so far and a list have last item left

# if a limit is not reached so far and a list is empty
def sample([], _removed_so_far), do: true

# if first and second item are not a part of an increasing list
# then function calls itself without a second argument
# if that would fail (return false) then function calls again itself
# but this time without a first argument instead
def sample([first, second | tail], removed_so_far) when first >= second do
removed_so_far = removed_so_far + 1
sample([first | tail], removed_so_far) || sample([second | tail], removed_so_far)
end

# in any other case we just skip a first item and perform check for a list's tail
def sample([_first, second | tail], removed_so_far) do
sample([second | tail], removed_so_far)
end
end
``````
2 Likes

Thanks to you and @cmo for your responses. There are a few test cases that defeat @Eiji’s solution (it incorrectly returns `true` when given `[1,2,1,2]`) but it uses tail recursion, which is the right way to go, I think. Here’s what I wound up with:

``````def solution(sequence) do
solution(sequence, length(sequence))
end

def solution(sequence, count) when count <= 0 do
is_ascending?(List.delete_at(sequence, count))
end

def solution(sequence, count) do
is_ascending?(List.delete_at(sequence, count)) or solution(sequence, count - 1)
end

def is_ascending?([_]),        do: true
def is_ascending?([a,b|tail]), do: b > a and is_ascending?([b|tail])
``````

I think that, in cases where you’re dealing with very long lists, the `Enum` module is gonna be too slow much of the time because it always enumerates over the whole list. In cases like that, you want tail recursion instead.

Ya know what else has to iterate over the whole list? `List.delete_at`, especially when called with `length(list)`. A quick benchmark:

``````Mix.install([:benchee])

list1 = 1..100 |> Enum.to_list()
length1 = length(list1)

list2 = 1..1000 |> Enum.to_list()
length2 = length(list2)

list3 = 1..10000 |> Enum.to_list()
length3 = length(list3)

Benchee.run(
%{
"100 elements" => fn -> List.delete_at(list1, length1) end,
"1000 elements" => fn -> List.delete_at(list2, length2) end,
"10000 elements" => fn -> List.delete_at(list3, length3) end
},
time: 10,
memory_time: 2
)
``````

produces the output on my machine:

``````Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.13.4
Erlang 25.0.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 42 s

Benchmarking 100 elements ...
Benchmarking 1000 elements ...
Benchmarking 10000 elements ...

Name                     ips        average  deviation         median         99th %
100 elements        393.26 K        2.54 μs  ±1944.85%        1.85 μs        4.95 μs
1000 elements        80.38 K       12.44 μs   ±142.97%       10.82 μs       42.36 μs
10000 elements        6.85 K      145.95 μs    ±33.72%      143.90 μs      279.72 μs

Comparison:
100 elements        393.26 K
1000 elements        80.38 K - 4.89x slower +9.90 μs
10000 elements        6.85 K - 57.40x slower +143.41 μs

Memory usage statistics:

Name              Memory usage
100 elements           3.18 KB
1000 elements         20.95 KB - 6.59x memory usage +17.77 KB
10000 elements       224.88 KB - 70.72x memory usage +221.70 KB
``````

Even calling `length` on the input is not desirable, since it has to traverse the list all the way to the end.

Calling `List.delete_at` as part of a recursion is a quick way to end up in the `O(N^2)` Bad Place.

To express this with functions, we can use `Enum.reduce_while/3` because of the control flow it gives us:

``````Enum.reduce_while(list, initial_state, fn element, state ->
# keep going:
{:cont, new_state}
# give up early:
{:halt, final_state}
end)
``````

The trick with `reduce` and friends is to pick the right shape for the “state” data.

In this problem, we have two important parts of the state:

• the last element we want to compare the new one to
• what have we seen so far?
• almost-increasing with no errors
• almost-increasing with one error
• (no third case because we want to give up)

This suggests that “state” is a tuple of `{status, last_element}`.

Now we need an “initial” value. The empty list is almost-increasing, and we know the minimum value for elements is `-105` so we can start with a value that will always be less than the first element of list:

``````Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
...
end)
``````

(Note: there’s nothing magical about `:all_increasing`, it’s chosen solely for human readability)

There are two factors that decide what to do next:

• the last state
• the comparison result between `last_element` and `element`

so let’s use a `case`:

``````Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
case {last_status, el > last_element} do

end
end)
``````

The first case is easy: if the list is almost-increasing and `el` is bigger, then the list is still almost-increasing and we should next look at `element`:

``````Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
case {last_status, element > last_element} do
{:all_increasing, true} ->
{:cont, {:all_increasing, element}}
end
end)
``````

The next-easiest case is when we’ve already found a “bad” element and we find another one. In that case, it’s time to give up:

``````Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
case {last_status, element > last_element} do
{:all_increasing, true} ->
{:cont, {:all_increasing, element}}

{:one_wrong, false} ->
{:halt, :not_increasing}
end
end)
``````

Almost as easy: if we’ve seen one wrong element but the current one is increasing, keep going:

``````Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
case {last_status, element > last_element} do
{:all_increasing, true} ->
{:cont, {:all_increasing, element}}

{:one_wrong, true} ->
{:cont, {:one_wrong, element}}

{:one_wrong, false} ->
{:halt, :not_increasing}
end
end)
``````

The tricky one is if the current element is “bad” but there are no previous errors. In that case, we continue noting that there’s been an error AND skip `el` (since it’s bad):

``````Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
case {last_status, element > last_element} do
{:all_increasing, true} ->
{:cont, {:all_increasing, element}}

{:all_increasing, false} ->
{:cont, {:one_wrong, last_element}}

{:one_wrong, true} ->
{:cont, {:one_wrong, element}}

{:one_wrong, false} ->
{:halt, :not_increasing}
end
end)
``````

Without passing `last_element` in that case, sequences like `[1,2,1,2]` aren’t correctly detected.

Finally, the result of `Enum.reduce_while` is the last accumulator so it needs to be cleaned up into the boolean result.

Final code with some cleanup:

``````defmodule Sequence do
def almost_increasing(sequence) do
case Enum.reduce_while(sequence, {:all_increasing, -1000}, &do_almost_increasing/2) do
{:all_increasing, _} -> true
{:one_wrong, _} -> true
:not_increasing -> false
end
end

defp do_almost_increasing(el, {state, last_element}) do
case {state, el > last_element} do
{:all_increasing, true} ->
{:cont, {:all_increasing, el}}

{:all_increasing, false} ->
{:cont, {:one_wrong, last_element}}

{:one_wrong, true} ->
{:cont, {:one_wrong, el}}

{:one_wrong, false} ->
{:halt, :not_increasing}
end
end
end
``````
3 Likes

Can you please check the updated version?

``````defmodule Example do
@remove_limit 1

# function head for a default argument
def sample(list, previous \\ nil, removed_so_far \\ 0)

# check if we have reached a remove limit
def sample(_list, _previous, removed_so_far) when removed_so_far > @remove_limit, do: false

# if a limit is not reached so far and a list have last item left
def sample([_head], _previous, _removed_so_far), do: true

# if a limit is not reached so far and a list is empty
def sample([], _previous, _removed_so_far), do: true

# ensure nil which as atom is bigger than any integer is not part of check
def sample([nil | tail], previous, removed_so_far), do: sample(tail, previous, removed_so_far)

# if first and second item are not a part of an increasing list
# then function calls itself without a second argument
# if that would fail (return false) then function calls again itself
# but this time without a first argument instead
def sample([first, second | tail], previous, removed_so_far) when first >= second do
removed_so_far = removed_so_far + 1

sample([first | tail], previous, removed_so_far) ||
sample([previous, second | tail], previous, removed_so_far)
end

# in any other case we just skip a first item and perform check for a list's tail
def sample([first, second | tail], _previous, removed_so_far) do
sample([second | tail], first, removed_so_far)
end
end
``````

When removing `first` from unmatched check I have added `previous` to list in order to perform check properly in that specific case.

1 Like

Thanks! I had previously tried a solution that sets a flag when the first bad result is found, but I wrote it so clumsily it didn’t work. Thank you for explaining the underlying reasoning.