77699

Determine whether array holds an almost increasing sequence

Question:

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.

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

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

Here is what I have so far:

function almostIncreasingSequence(sequence) { //compare current int to previous, return true if greater than //remove int at index and compare with new values, return false if comparison fails var result = false; for(var i = 0; i < sequence.length; i++){ var newSequence = sequence.slice(); var subSequence = newSequence.splice(i, 1); for(var j = 0; j < newSequence.length - 1; j++){ if(newSequence === newSequence.sort((a,b) => a < b).reverse()){ result = true; } } } return result; }

I'm trying to figure out how to solve this problem. I feel like I'm very close but for some reason when I call reverse in the conditional statement it also sorts out the newSequence variable. It's sorting two variables in the conditional, not one. As a result it resolves to true. I'm not clear why this is happening. Any feedback is appreciated.

Answer1:

There is no need to use a nested loop, nor to create new arrays. This can be done in <em>O(n)</em> time:

<pre class="snippet-code-js lang-js prettyprint-override">function almostIncreasingSequence(sequence) { var prev = -Infinity, beforePrev = -Infinity, allowExceptions = true; for (var curr of sequence) { // Is order not maintained? if (curr <= prev) { // Give up when this is not the first exception if (!allowExceptions) return false; allowExceptions = false; // Decide whether to skip the current or previous value if (curr > beforePrev) prev = curr; } else { // Normal case: keep track of two preceding values beforePrev = prev; prev = curr; } } return true; } console.log(almostIncreasingSequence([1,5,3,4,8])); // true console.log(almostIncreasingSequence([1,5,0,6,8])); // true console.log(almostIncreasingSequence([1,5,0,4,8])); // false

Answer2:

sort() modifies the array in place, it doesn't return a new array. And you can't compare the contents of two arrays using ==, so that's not a good way to tell if an array is sorted. You can simply loop through the array, testing if each element is greater than the previous one.

<pre class="snippet-code-js lang-js prettyprint-override">function almostIncreasingSequence(sequence) { for (var i = 0; i < sequence.length; i++) { var newSequence = sequence.slice(); newSequence.splice(i, 1); var isSorted = true; for (j = 1; isSorted && j < newSequence.length; j++) { if (newSequence[j] <= newSequence[j-1]) { isSorted = false; } } if (isSorted) { return true; } } return false; } console.log(almostIncreasingSequence([1, 3, 2, 1])); console.log(almostIncreasingSequence([1, 3, 2])); console.log(almostIncreasingSequence([1, 2, 3, 4, 5, 3])); console.log(almostIncreasingSequence([8, 1, 2, 3, 4, 5])); console.log(almostIncreasingSequence([8, 1, 2, 2, 4, 5]));

Recommend

  • Why is new Number(8) not exactly equal to 8?
  • What is the difference between Socket.Send and Stream.Write? (in relation to tcp ip connections)
  • Concise regex extract function in XSLT 2.0
  • ASPNetCore MVC Routing Let Server Handle Specific Route
  • How to get the date of next specified day of week
  • Python cosine function precision [duplicate]
  • What causes the runtime difference in this trivial fortran code?
  • npm 5.4.1 install/uninstall all failing
  • one Local Olampyad Questions on Informatic in 2011
  • OpenGL 3.3 on Mac OSX El Capitan with LWJGL
  • Running a C# exe file
  • When should I choose bucket sort over other sorting algorithms?
  • Convert array of 8 bytes to signed long in C++
  • Numpy divide by zero. Why?
  • php design question - will a Helper help here?
  • How to disable jQuery.jplayer autoplay?
  • How to delete a row from a dynamic generate table using jquery?
  • AngularJs get employee from factory
  • using HTMLImports.whenReady not working in chrome
  • Understanding cpu registers
  • Change div Background jquery
  • How to stop GridView from loading again when I press back button?
  • IndexOutOfRangeException on multidimensional array despite using GetLength check
  • Authorize attributes not working in MVC 4
  • Bitwise OR returns boolean when one of operands is nil
  • EntityFramework adding new object to nested object collection
  • sending mail using smtp is too slow
  • Is there any way to bind data to data.frame by some index?
  • Django query for large number of relationships
  • Busy indicator not showing up in wpf window [duplicate]
  • Recursive/Hierarchical Query Using Postgres
  • Running Map reduces the dimensions of the matrices
  • costura.fody for a dll that references another dll
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • Binding checkboxes to object values in AngularJs
  • Observable and ngFor in Angular 2
  • How can I use `wmic` in a Windows PE script?
  • UserPrincipal.Current returns apppool on IIS
  • java string with new operator and a literal
  • How to push additional view controllers onto NavigationController but keep the TabBar?