<Codesignal> almostIncreasingSequence

Easy

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
  almostIncreasingSequence(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
  almostIncreasingSequence(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] 0.5 seconds (c)

• [input] array.integer sequence

  Guaranteed constraints:
  2 ≤ sequence.length ≤ 10^5,
  -10^5 ≤ sequence[i] ≤ 10^5.

• [output] boolean

  • Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
bool almostIncreasingSequence(arr_integer sequence)
{
	bool notIncreased=false;
	int index;
	arr_integer removed=alloc_arr_integer(sequence.size-1);

	for(int i=0;i<sequence.size-1;i++)
		if(sequence.arr[i+1]<=sequence.arr[i])
		{
			notIncreased=true;
			index=i;
			break;
		}
	if(!notIncreased)
		return true;

	for(int i=0;i<removed.size;i++)
		removed.arr[i]=sequence.arr[i<index?i:i+1];
	notIncreased=false;
	for(int i=0;i<removed.size-1;i++)
		if(removed.arr[i+1]<=removed.arr[i])
		{
			notIncreased=true;
			break;
		}
	if(!notIncreased)
		return true;

	for(int i=0;i<removed.size;i++)
		removed.arr[i]=sequence.arr[i<index+1?i:i+1];
	notIncreased=false;
	for(int i=0;i<removed.size-1;i++)
		if(removed.arr[i+1]<=removed.arr[i])
			return false;

	return true;
}