Checking whether a sequence of integers is increasing

Question

I'm stuck only partially passing the below problem.

Given a sequence of integers, check whether it is possible to obtain a strictly increasing sequence by erasing no more than one element from it.

Example

sequence = [1, 3, 2, 1]
almostIncreasingSequence(sequence) = false

sequence = [1, 3, 2]
almostIncreasingSequence(sequence) = true

My code that is only passing some examples:

bool almostIncreasingSequence(int[] sequence) {
   int seqIncreasing = 0;
    if (sequence.Length == 1) return true;
    for (int i = 0;i < sequence.Length-2;i++)
    {
        if ((sequence[i] == sequence[++i]+1)||(sequence[i] == sequence[++i])) 
        {
            seqIncreasing++; 
        } 
    } 
    return ((seqIncreasing == sequence.Length) || (--seqIncreasing == sequence.Length));
}

Failed Examples:

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

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

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

Input:
    sequence: [1, 1]
Output:
    false
Expected Output:
    true

Answer 1

The LINQ-based answer is fine, and expresses the basic problem well. It's easy to read and understand, and solves the problem directly. However, it does have the problem that it requires generating a new sequence for each element in the original. As the sequences get longer, this becomes dramatically more costly and eventually, intractable.

It doesn't help that it requires the use of Skip() and Take(), which themselves add to the overhead of handling the original sequence.

A different approach is to scan the sequence once, but keep track of whether a deletion has already been attempted and when finding an out-of-sequence element, to a) immediately return false if a deletion was already found, and b) don't include the deleted element in the determination of the sequence.

The code you tried almost accomplishes this. Here's a version that works:

static bool almostIncreasingSequence(int[] sequence)
{
    bool foundOne = false;

    for (int i = -1, j = 0, k = 1; k < sequence.Length; k++)
    {
        bool deleteCurrent = false;

        if (sequence[j] >= sequence[k])
        {
            if (foundOne)
            {
                return false;
            }
            foundOne = true;

            if (k > 1 && sequence[i] >= sequence[k])
            {
                deleteCurrent = true;
            }
        }

        if (!foundOne)
        {
            i = j;
        }

        if (!deleteCurrent)
        {
            j = k;
        }
    }

    return true;
}

Note: I originally thought your attempt could be fixed with a minor change. But ultimately, it turned out that it had to be essentially the same as the generic implementation I wrote (especially once I fixed that one too…see below). The only material difference is really just whether one uses an array or a generic IEnumerable<T>.

For grins, I wrote another approach that is in the vein of the LINQ-based solution, in that it works on any sequence, not just arrays. I also made it generic (albeit with the constraint that the type implements IComparable<T>). That looks like this:

static bool almostIncreasingSequence<T>(IEnumerable<T> sequence) where T : IComparable<T>
{
    bool foundOne = false;
    int i = 0;
    T previous = default(T), previousPrevious = default(T);

    foreach (T t in sequence)
    {
        bool deleteCurrent = false;

        if (i > 0)
        {
            if (previous.CompareTo(t) >= 0)
            {
                if (foundOne)
                {
                    return false;
                }

                // So, which one do we delete? If the element before the previous
                // one is in sequence with the current element, delete the previous
                // element. If it's out of sequence with the current element, delete
                // the current element. If we don't have a previous previous element,
                // delete the previous one.

                if (i > 1 && previousPrevious.CompareTo(t) >= 0)
                {
                    deleteCurrent = true;
                }

                foundOne = true;
            }
        }

        if (!foundOne)
        {
            previousPrevious = previous;
        }

        if (!deleteCurrent)
        {
            previous = t;
        }
        i++;
    }

    return true;
}

Of course, if you're willing to copy the original sequence into a temporary array, if it's not already one, then you could easily make the array-based version generic, which would make the code a lot simpler but still generic. It just depends on what your priorities are.

Addendum:

The basic performance difference between the LINQ method and a linear method (such as mine above) is obvious, but I was curious and wanted to quantify this difference. So I ran some tests, using randomly generated sequences, to get a rough idea of the difference.

I performed two versions of the tests: the first, I ran a loop with 1000 trials, where the sequences could be anywhere between 10 and 100 elements long; and the second, with 10,000 trials and sequences between 100 and 1000 elements long. I performed the second version, because on my laptop the entire test of 1000 trials with shorter sequences completed in less than 1/20th of a second, too short a time for me to have confidence in the validity of the result.

With that first version, the code spent about 1ms calling the linear method of the check, and about 30ms calling the LINQ method, for a 30x difference in speed. Increasing the number of trials to 10,000 confirmed the result; the times scaled almost exactly 10x for each method, keeping a difference of 30x.

With the second version, the difference was closer to 400x. The linear version took about 0.07 seconds, while the LINQ version took 30 seconds.

As expected, the longer the sequence, the worse the disparity. For very short sequences, not only is the code unlikely to ever spend much time in the sequence-checking logic, the discrepancy between the linear and LINQ methods is going to be relatively small. But as the sequences get longer, the discrepancy will trend to very poor performance for the LINQ version while the linear version remains an excellent performer.

The LINQ version is very readable and concise. So in a situation where the inputs are always going to be relatively short (on the order of a dozen or two elements at the most), I'd go with the LINQ version. But if I expected to execute this test routinely with data that was any longer than that, I would avoid the LINQ and stick with the much more efficient linear approach.

A note on the randomly-generated sequences: I wrote the code to generate a monotonically increasing sequence of non-negative numbers, of the desired length, and then inserted between 0 and 2 (inclusive) new elements having a value of int.MinValue or int.MaxValue (also randomly selected, for each insertion). In this way, a third of the tests involved sequences that were trivially valid, a third involved sequences that required finding the correct single element to remove, and a third were not valid (i.e. did not meet the requirement that it could be made monotonically increasing by deleting at most one element).

Answer 2

UPDATE: Fixed a bug related to the way I was generating subsequences using Except. The obvious issue was that the subsequences generated when the original sequence contained duplicate items could be wrong; all positions of duplicate items could be potentially removed.

This problem seems deceptively simple but you can easily get bogged down in loops with ifs and elses that will never get it exactly right.

The best way to solve this is to take a step back and understand what the condition you are asking for really means. An almost strictly increasing sequence is one such that, of all possible subsequences created be removing one single item, at least one must be strictly increasing.

Ok, that seems to be sound reasoning, and its easy to implement, so lets do it:

First, a trivial method that tells us if a given sequence is strictly increasing:

private static bool IsStrictlyIncreasing<T>(this IEnumerable<T> sequence)
    where T : IComparable<T>
{
    using (var e = sequence.GetEnumerator())
    {
        if (!e.MoveNext())
            return true;

        var previous = e.Current;

        while (e.MoveNext())
        {
            if (e.Current.CompareTo(previous) <= 0)
                return false;

            previous = e.Current;
        }

        return true;
    }
}

Now we need a helper method to generate all possible subsequences removing one item (as stated above, simply using Except will not cut it if T has value equality semantics):

private static IEnumerable<IEnumerable<T>> GenerateSubsequences<T>(
    this IEnumerable<T> sequence)
    => Enumerable.Range(0, sequence.Count())
                 .Select(i => sequence.Take(i)
                                      .Concat(sequence.Skip(i + 1)))

And now, we simply need to check all subsequences and find at least one that is strictly increasing:

public static bool IsAlmostStrictlyIncreasing<T>(this IEnumerable<T> sequence)
    where T : IComparable<T>
    => sequence.GenerateSubsequences()
               .Any(s => s.IsStrictlyIncreasing());

That should do it.

Answer 3

Having solved that CodeSignal challenge using C# myself, I can tell you how I approached it.

First, a helper method to handle the logic of deciding when to remove an element from a sequence:

private static bool removeElement(IEnumerable<int> sequence, int i) {
    // This method handles the logic for determining whether to remove an element from a sequence of integers.
    // Initialize the return variable and declare some useful element aliases.
    bool removeElement = false;
    int c = sequence.ElementAt(i), p = sequence.ElementAtOrDefault(i - 1), n = sequence.ElementAtOrDefault(i + 1);

    // Remove the first element if and only if it is greater than or equal to the next element.
    if      (i == 0)                      removeElement = (c >= n);
    // Remove the last element if and only if it is less than or equal to the previous element.
    else if (i == (sequence.Count() - 1)) removeElement = (c <= p);
    // Removal logic for an element somewhere in the middle of the sequence:
    else {
        // If the current element is greater than the previous element...
        // ...and the current element is less than the next element, then do not remove the current element.
        if (c > p && c < n) removeElement = false;
        // If the current element is greater than or equal to the next element, then it might need to be removed.
        else if (c > p && c >= n) {
            removeElement = true;

            // Handle edge case for test 19.
            // If the current element is the next-to-last element...
            // ...and the only reason it's being considered for removal is because it is less than the last element...
            // ...then skip it and remove the last element instead.
            if (i == (sequence.Count() - 2)) removeElement = false;

            // Handle edge case for test 16.
            // If the current element occurs before the next-to-last element...
            if (i < (sequence.Count() - 2))
                // ...and both the current and next elements are less than the following element...
                // ...then skip the current element and remove the next one instead.
                if (n < sequence.ElementAt(i + 2) && c < sequence.ElementAt(i + 2)) removeElement = false;
        // Otherwise, remove the current element.
        } else removeElement = true;
    }

    return removeElement;
}

Then I wrote two versions of the main method: one using LINQ, and one without.

LINQ version:

bool almostIncreasingSequence(int[] sequence) {
    // Eliminate the most trivial cases first.
    if      (sequence.Length <= 2)                                        return true;
    else if (sequence.SequenceEqual(sequence.Distinct().OrderBy(x => x))) return true;
    else {
        // Get the index of the first element that should be removed from the sequence.
        int index = Enumerable.Range(0, sequence.Length).First(x => removeElement(sequence, x));
        // Remove that element from the sequence.
        sequence = sequence.Where((x, i) => i != index).ToArray();
    }

    // Return whether or not the remaining sequence is strictly increasing.
    return sequence.SequenceEqual(sequence.Distinct().OrderBy(x => x));
}

Non-LINQ version:

bool almostIncreasingSequence(int[] sequence) {
    // Eliminate the most trivial cases.
    if (sequence.Length <= 2) return true;
    // Make a copy of the input array in the form of a List collection.
    var initSequence = new List<int>(sequence);
    // Iterate through the List.
    for (int i = 0; i < initSequence.Count; i++) {
        // If the current element needs to be removed from the List, remove it.
        if (removeElement(initSequence, i)) {
            initSequence.RemoveAt(i);
            // Now the entire sequence after the first removal must be strictly increasing.
            // If this is not the case, return false.
            for (int j = i; j < initSequence.Count; j++) {
                if (removeElement(initSequence, j)) return false;
            }

            break;
        }
    }

    return true;
}

Both variations pass all of the provided test cases:

38/38 tests passed.
Sample tests: 19/19
Hidden tests: 19/19
Score: 300/300