almostIncreasingSequence - Javascript

Question

Hi guys I'm using Codefights concurrently while I learn algorithims & data structures and I cant seem to solve this 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.

My code is failing due to performance and I have a general idea why considering my copying of the original array and looping through both. But I am unable to think of a more optimized way.

function almostIncreasingSequence(sequence) {
    let result = false;
    for(let i = 0; i < sequence.length; i++) {
        let newSequence = [...sequence]
        newSequence.splice(i,1)
        result = isArraySequential(newSequence)
        if (result) {
            return result;
        }
    }
        return result;
}

function isArraySequential(array) {
    let isSequential = true;
    for(let i = 0; i < array.length; i++) {
        if(i == array.length - 1) {return isSequential}
         if (array[i + 1] < array[i] || array[i + 1] == array[i]) {
            return !isSequential;
        }
    }
}

Fibrinolysis

Answer 1

You don't need to constantly check the entire array, nor use multiple loops.

The problem can be broken down to smaller questions. For each element in the list...

• Is the current element greater than the last (increasing)?
  • Yes...
    • Good! We don't need to do anything.
  • No...
    • Has this happened already? If so, it's not almost increasing.
    • If we remove the previous item, are the surrounding items fixed?
    • No? What if we remove the current item instead?
    • Still no? Then that means we can't solve this in one move. It's not almost increasing.

The code would look something like this:

function almostIncreasingSequence(sequence) {
  let invalidItemsCount = 0;
  
  for (let i = 1; i < sequence.length; i++) {
    if (sequence[i] <= sequence[i-1]) {
      invalidItemsCount++;
      if (invalidItemsCount > 1) return false;
      if (sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]) return false;
    }
  }
  
  return true;
}

var test1 = [0,1,2,3,4,7,6,7,8,9,10];
var test2 = [0,1,2,4,3,4,5,7,6,7,8,9,10];

console.log(almostIncreasingSequence(test1));
console.log(almostIncreasingSequence(test2));

Commented version:

function almostIncreasingSequence(sequence) {
  //Keep track of how many replacements we've had to make
  let invalidItemsCount = 0;
  
  //Start our loop at 1 so that [i-1] doesn't refer to index "-1"
  for (let i = 1; i < sequence.length; i++) {
  
    //If this item is not increasing, we'll need to address it
    if (sequence[i] <= sequence[i-1]) {
    
      //Increment our invalidItemsCount
      invalidItemsCount++;               
      
      //If this is our second invalidItem, then it's not almost increasing.
      if (invalidItemsCount > 1) return false;  
      
      //If removing the previous element doesn't help, and removing the current item doesn't help,
      //then we can't solve this in one move. It's not almost increasing.
      if (sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]) return false;
      
    }
  }
  
  //We've made it through the entire loop without fail. This is almost increasing.
  return true;
}

var test1 = [0,1,2,3,4,7,6,7,8,9,10];
var test2 = [0,1,2,4,3,4,5,7,6,7,8,9,10];

console.log(almostIncreasingSequence(test1));
console.log(almostIncreasingSequence(test2));

Carleton

thanks for the help. I thought about doing something like that but was unsure how to condition the last if statement. I appreciate the comments and will try to fully understand this solution. – Fibrinolysis

Answer 2

package main

import "fmt"

func main() {
    fmt.Println(almostIncreasingSequence([]int{10, 1, 2, 3, 4, 5}))
    fmt.Println(almostIncreasingSequence([]int{1, 2, 3, 2, 3, 6}))
    fmt.Println(almostIncreasingSequence([]int{1, 2, 3, 4, 99, 5, 6}))
    fmt.Println(almostIncreasingSequence([]int{1, 2, 3, 4, 5, 6, 5}))
    fmt.Println(almostIncreasingSequence([]int{1, 5, 3, 4, 5, 6, 5}))
}

func almostIncreasingSequence(sequence []int) bool {
    count := 0
    for i := 1; i <= len(sequence)-1; i++ {
        if sequence[i] <= sequence[i-1] {
            count++
            if count > 1 {
                return false
            }

            if i <= 1 || i == len(sequence)-1 {
                continue
            }

            if sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1] {
                return false
            }
            continue
        }
    }
    return true
}

Sober

The question clearly mentions (and tags) javascript. Your response is go code without any explanation. – Severen

Answer 3

This is my solution to the problem. I hope someone would find it helpful.

function almostIncreasingSequence(sequence) {
    let flag = 0;
    for (let i = 0; i < sequence.length; i++) { 
      if (sequence[i] >= sequence[i+1]){
          flag++; 
          if(i !== 0 && sequence[i] >= sequence[i+2]){
              if(sequence[i-1] >= sequence[i+1])
                  return false;
          }
      }
  } 
  return flag < 2;
}

Taxi

Answer 4

This works :)) Hope it can help.

function solution(a) {
    
    const counts = {};
    var output = 0;
    
    var dupArr = []
    
    for (const num of a) {
        
        counts[num] = counts[num] ? counts[num] + 1:1;
        
        
        if (counts[num] > 1) {
            dupArr.push(num);
        }else{
            output = -1;
        }
        
    }
    
    if (dupArr.length > 0) {
        return dupArr[0];
    }
    else{
        return -1;
    }

}

Stammer

Answer 5

Checkout this solution I found, time complexity is O(n).Hope someone finds it helpful

function almostIncreasingSequence(){
  let bad=0,i; //initialize the number of bad counts
  for(i=1; i<sequence.length; i++){
        if(sequence[i]<=sequence[i-1]){
        bad++
        }
 // The descriptions say "removing no more than one element from the array."
 // if the number of bad counts is more than one, we can't obtain the desired result so return false
        if(bad>1) return false
// if the element on current index is  less than or equal the adjacent element -2 steps back
// && next element is less than or equal to the element on previous index return false 
        if(sequence[i]<=sequence[i-2] && sequence[i+1]<=sequence[i-1])return false

    }
   return true
}

Here is the link

Durden