2
votes

I am having trouble with a problem and how to address it. Mind you, I am relatively new to JavaScript and the problem feels like I am over complicating it.

The problem:

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.

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].

Thanks for all your comments! I wanted to update this to be a better question, and also inform you I have found a solution if someone would like to check it and see if there is a cleaner way to put it. :)

function almostIncreasingSequence(sequence) {    
  if(sequence.length == 2) return true;
  var error = 0;
  for(var i = 0; i < sequence.length - 1; i++){
    if(sequence[i] >= sequence[i+1]){
      var noStepBack = sequence[i-1] && sequence[i-1] >= sequence[i+1];
      var noStepFoward = sequence[i+2] && sequence[i] >= sequence[i+2];
      if(i > 0 && noStepBack && noStepFoward) {
        error+=2;
      }else{
        error++;
      }
    }
    if(error > 1){
      return false;
    }
  }
  return true;
}
3
Welcome to Stack Overflow. Please read: stackoverflow.com/help/mcve - Twisty
Note how the question states "strictly increasing sequence", it doesn't specify how it increases, so you could have [1, 2, 3, 5, 8, 13] and it would be valid, my hint to you is to try seeing if the difference is positive instead of a specific number - Patrick Barr
This seemingly simple problem seems hard to solve correctly... - le_m
@Twisty thank you for that! I continued on to read more best question posting practices and hopefully my next question hits the mark! Thanks again - Almost_Ashleigh

3 Answers

1
votes

Think about what your code:

sequence[i+1] - sequence[i] !== 1, variable++;

would do for the following array:[1,2,3,8,8].

From the problem description, it is not clear weather the program must remove one character. But if that is the case, the code below should do it.

function canGetStrictlyIncreasingSeq(numbers) {
  var counter = 0;
  var lastGreatestNumber = numbers[0];
  for (var i = 1; i < numbers.length; i++) {
    if (lastGreatestNumber >= numbers[i]) {
      counter++;
      lastGreatestNumber = numbers[i];
    } else {
      lastGreatestNumber = numbers[i];
    }
  }
  if (counter <= 1)
    return true;
  return false;
}

var nums1 = [1, 2, 3, 4, 5]; //true
var nums2 = [1, 2, 2, 3, 4]; //true
var nums3 = [1, 3, 8, 1, 9]; //true
var nums4 = [3, 2, 5, 6, 9]; //true
var nums5 = [3, 2, 1, 0, 5]; //false
var nums6 = [1, 2, 2, 2, 3]; //false
var nums7 = [1, 1, 1, 1, 1]; //false
var nums8 = [1, 2]; //true
var nums9 = [1, 2, 2]; //true
var nums10 = [1, 1, 2, 3, 4, 5, 5]; //false
var nums11 = [10, 1, 2, 3, 4, 5]; //true
var nums12 = [1, 2, 3, 4, 99, 5, 6]; //true


console.log(canGetStrictlyIncreasingSeq(nums1));
console.log(canGetStrictlyIncreasingSeq(nums2));
console.log(canGetStrictlyIncreasingSeq(nums3));
console.log(canGetStrictlyIncreasingSeq(nums4));
console.log(canGetStrictlyIncreasingSeq(nums5));
console.log(canGetStrictlyIncreasingSeq(nums6));
console.log(canGetStrictlyIncreasingSeq(nums7));
console.log(canGetStrictlyIncreasingSeq(nums8));
console.log(canGetStrictlyIncreasingSeq(nums9));
console.log(canGetStrictlyIncreasingSeq(nums10));
console.log(canGetStrictlyIncreasingSeq(nums11));
console.log(canGetStrictlyIncreasingSeq(nums12));
0
votes

Lets take a step back and think about the problem: "Given a sequence of Integers as an array" - we're dealing with arrays of data...but you already knew that.

"determine whether it is possible to obtain a strictly increasing sequence" ok, we need to make something that checks for valid sequence.

"by removing no more than one element from the array." so we can try plucking each element one-by-one and if at least one resulting array is sequential, its possible.

Now instead of one large problem we have two smaller ones

First, we're dealing with arrays, so avail yourself to JavaScript's built-in Array functions to make things easier. In the below, we use 'every()', 'forEach()', 'splice()', 'push()', and 'some()' You can read into how they work here https://www.w3schools.com/jsref/jsref_obj_array.asp It's not long and well worth your time.

Lets deal with the first problem: Determining if an array is sequential. The below function does this

function checkSequence(inputArray){
    return inputArray.every(function(value, index, arr){
        if (index == 0  && value < arr[index + 1]) {return true}
        else if (index < arr.length  && value < arr[index + 1] && value > arr[index - 1]) {return true}
        else if (index = arr.length - 1 && value > arr[index - 1]) {return true}
        else {return false}
    });
}

It takes an input array, and uses an Array built-in function called every(), which runs a test on each element in an array and returns 'true' if all the elements test true. Our test expects the first element to always be lower less than the second for any given element to be greater than the previous, and less than the next, and for the last element to be greater than the next-to-last if any element does not satisfy this test, the whole thing returns false Now we have a means of seeing of an array is sequential, which will make the next part much easier

Now we make another function to pluck out individual elements and see if anythign works

function isPossible(input){
    var results = []; //we will store our future results here
    input.forEach(function(value, index, arr){
        copy = Array.from(arr); //we work on a copy of 'arr' to avoid messing it up (splice mangles what you give it, and we need the un-maimed version for later iterations)
        copy.splice(index, 1); //remove an element from copy (a copy of 'arr')      
        results.push(checkSequence(copy)); //see if it is still in sequence
    });
    return results.some(function(value){return value});
}

We first make an array to store the results of each attempt into the array 'results' we will use it later. Then, we take a supplied array 'input' and use "forEach()", which performs a function with each element in an array. for each element, we make a new array with that element removed from it, and we run the "checkSequence()" function we made before on it, and finally store the result in the results array.

When the forEach is done, we take the results array and use 'some()' on it, which works just like 'every()' only it returns true if at least one value is true

Now, you simply call isPossible(your_array) and it will satisfy the problem

0
votes

Taking into account Patrick Barr's suggestion and assuming that es6 and arrow functions are fine, this solution using Array.prototype.filter could work. The filter itself will return array of elements that should be removed to satisfy conditions of the problem:

UPDATED

function isSequential(array) {
    return array && array.length > 0 ? array.filter((x,i) => x >= array[i + 1] || array[i + 1] <= array[i - 1]).length < 2 : false;
}


console.log(isSequential([1]));
console.log(isSequential([1,2,4,5,6]));
console.log(isSequential([1,2,2,3,4,5,6]));
console.log(isSequential([1,4,3,2,5,6]));
console.log(isSequential([1,2,3,4,5,6]));
console.log(isSequential([1,2,0,3,4]));
console.log(isSequential([1,1]));
console.log(isSequential([1,2,0,1,2]));
console.log(isSequential([1,2,3,1,2,3]));
console.log(isSequential([]));
console.log(isSequential([1,0,0,1]));
console.log(isSequential([1,2,6,3,4])); //should be true, but return false