11
\$\begingroup\$

I need to write a function that takes in a sequence of numbers and returns true if the sequence is increasing or false if it's not:

function isIncreasingSequence(numbers) {
  /**Check if numbers sequence is increasing
  * @param {number} numbers - a sequence of input numbers;
  * @return {boolean} - true if given sequence is increasing, false othrewise
  */
  let numArr = Array.prototype.slice.call(arguments);
  let truthArray = [];

  for (var num = 0; num < numArr.length; num++) {
    while (numArr[num + 1] !== undefined) {
      if (numArr[num] < numArr[num + 1]) {
        truthArray.push(true);
      } else {
        truthArray.push(false);
      }
      num++
    }
  }

  if (truthArray.includes(false)) {
    return false;
  } else {
    return true;
  }
}

Some samples:

console.log(isIncreasingSequence(1,2,3,4)); //true
console.log(isIncreasingSequence(1,255,53,0)); //false
console.log(isIncreasingSequence(0, 0.2, 0.3, 1)); //true

I don't like this while loop nested inside of a for loop. Is there a better way to handle it?

\$\endgroup\$
  • 1
    \$\begingroup\$ Given your parameter name and the jsdoc, I had expected numbers to be an array, to be checked instead of the numArr/arguments. Which do you want? \$\endgroup\$ – Bergi Nov 15 '17 at 20:47
  • \$\begingroup\$ What are you trying to accomplish with the loop? It doesn't seem to do anything. You could replace the loop with just var num = 0 before the while. \$\endgroup\$ – Rob Nov 15 '17 at 23:52
  • 1
    \$\begingroup\$ "if sequence is increasing" is ambiguous. I would add another kind of solution where you calculate the trend line of the values against the index in O(n) time and if the slope is +ve then the numbers are globally increasing, even if not always locally, e.g. I would class 1,2,3,5,4,6,7,8,9 as increasing by this definition. \$\endgroup\$ – Troy Wray Nov 16 '17 at 10:43
15
\$\begingroup\$

Implementation

  • The current return statement has the form if(condition) return !condition; else return condition;. This can be simplified to return !condition, i.e. return !truthArray.includes(false);.
  • The current implementation uses \$O(n^2)\$ runtime and memory, even though it is possible with \$O(n)\$ runtime and \$O(1)\$ memory:
    • The while loop can be exchanged for an if condition, or dropped entirely if there are no expected undefined entries in the input array (in that case, also remove the superfluous num++) by changing the for loops condition to num < numArr.length - 1.
    • There is no need to push every partial result into an array: If there is a mismatch, just return false. If there is no mismatch (i.e. you reach the end of the function), simply return true.
  • The current implementation returns false for input 1, 2, 2, 3. Is this intended?

Cleaned up code

/**Check if numbers sequence is increasing
* @param {number} numbers - a sequence of input numbers, must be valid floating point values;
* @return {boolean} - true if given sequence is increasing, false otherwise
*/
function isIncreasingSequence(numbers) {
  let numArr = Array.prototype.slice.call(arguments);

  for (var num = 0; num < numArr.length - 1; num++) {
      if (numArr[num] >= numArr[num + 1] || Number.isNaN(numArr[num]) || Number.isNaN(numArr[num + 1])) {
          return false;
      }
  }

  return true;
}

The condition numArr[num] >= numArr[num + 1] || Number.isNaN(numArr[num]) || Number.isNaN(numArr[num + 1]) could be reduced to !(numArr[num] < numArr[num + 1]), but I chose the current condition because it makes the handling of NaN values more visible.

NOTE: Arguments are not validated, call this function with non-Number arguments at your own risk!

\$\endgroup\$
  • 1
    \$\begingroup\$ "The current implementation returns false for input 1, 2, 2, 3. Is this intended?" In an increasing sequence, every subsequent element must be bigger than the earlier. You probably thought of non-decreasing sequence. \$\endgroup\$ – Luke Nov 15 '17 at 13:12
  • 3
    \$\begingroup\$ @Luke: I was just mentioning it, since it wasn't clear (to me, at least) from the description in the question if he meant a strictly increasing sequence or not (in some context it seems the "strictly" is implied, in others it isn't). \$\endgroup\$ – hoffmale Nov 15 '17 at 13:22
  • \$\begingroup\$ Note that this implementation checks most of the array's elements for isNaN twice. \$\endgroup\$ – qntm Nov 16 '17 at 10:39
  • \$\begingroup\$ @qntm: Read the note at the bottom, one could incorporate those NaN checks into the comparison itself (x compared to NaN is always false), so they would be implicit. That said, !(x < y) might seem to be the same as x >= y for someone not as deeply involved with floating point math, so I prefer the more explicit variant (YMMV of course). (Of course, one could reduce that to one check per element, even in the explicit case. Feel free to adjust to your needs.) \$\endgroup\$ – hoffmale Nov 16 '17 at 11:07
  • \$\begingroup\$ For the handling of NaN to be effective, you should change the condition to isNaN(numArr[num + 1]) || numArr[num] >= numArr[num + 1], and use an early-return before the loop, in case numArr[0] is an NaN. This reduces the number of calls to the isNaN function by, at least, half. Also, without the change, you will be using the operator >= on NaNs. On the bit I gave you, I'm taking advantage of short-circuit evaluation, to skip numArr[num] >= numArr[num + 1] if isNaN(numArr[num + 1]) is true. \$\endgroup\$ – Ismael Miguel Nov 18 '17 at 16:44
15
\$\begingroup\$
const isIncreasingSequence = (...numbers) =>
  numbers.every((number, i) => i === 0 || numbers[i - 1] < number)

Here we use rest parameters ...numbers to treat the input arguments as an array. Then we use Array.prototype.every to examine each number in turn and check that it is greater than the previous entry in the array - or that it is the first entry in the array and hence has no previous entry. Note that Array.prototype.every will return as soon as it hits a counterexample, which saves time if the array is something like [0, -56, 1, 2, ..., 9999, 10000].

If NaNs are a possibility, then the presence of a NaN in the array can be made an instant failure like so:

const isIncreasingSequence = (...numbers) =>
  numbers.every((number, i) => !Number.isNaN(number) && (i === 0 || numbers[i - 1] < number))

Note that each number is only checked for isNaN once. Note also that this check happens before the numerical comparison - numerical comparisons with NaN are hazardous because of their poorly-understood, non-obvious behaviour, and hence best avoided.

\$\endgroup\$
  • 1
    \$\begingroup\$ Although it's possible to force it all on one line, I honestly think code readability is improved by writing it out. Right now this is very hard to read quickly. \$\endgroup\$ – David Mulder Nov 15 '17 at 11:59
  • \$\begingroup\$ For readability, split it into const lessThanLast = (num, idx, arr) => idx === 0 || num < arr[idx -1] and !numbers.some(Number.isNaN) && numbers.every(lessThanLast) \$\endgroup\$ – JollyJoker Nov 15 '17 at 13:27
  • \$\begingroup\$ Btw, is there a reason most answers here are still pre-ES6? \$\endgroup\$ – JollyJoker Nov 15 '17 at 13:31
  • 2
    \$\begingroup\$ @DavidMulder I disagree, it's quite clear what the code does. \$\endgroup\$ – Conor O'Brien Nov 16 '17 at 1:26
6
\$\begingroup\$

Besides what Hoffmale already said in his answer, you can also use rest parameters. You have a parameter numbers which you are not even using, and you have to turn arguments into an array. With rest parameters the remaining arguments (which is all of them in this case) will already be an array.

Documentation comments should also be before the function, instead of inside it.

/**
 * Checks if number sequence is increasing
 * @param {Number} numbers - a sequence of input numbers
 * @return {Boolean} - true if given sequence is increasing, false otherwise
 */
function isIncreasingSequence(...numbers) {
  // Using Hoffmale's function
  for (var num = 0; num < numbers.length - 1; num++) {
    if (!(numbers[num] < numbers[num + 1])) {
      return false;
    }
  }
  return true;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ This was indeed what I was about to write, an in addition to this, if you do have a non-array iterable use Array.from instead of Array.prototype.slice.call. \$\endgroup\$ – David Mulder Nov 15 '17 at 11:57
  • \$\begingroup\$ With your implementation the empty sequence and the sequence with one element are both increasing. The rest looks nice. I think you could possibly merge the if with the condition in the for loop. I am not quite sure which of the two ways is the better one. \$\endgroup\$ – allo Nov 15 '17 at 15:31
5
\$\begingroup\$

It has already been mentioned, but if you mean a "non decreasing" sequence as opposed to a strictly increasing sequence, you could use the following.

function isNonDecreasingSequence(numbers) {

    return numbers.slice().sort().toString() == numbers.toString();

}

console.log(isNonDecreasingSequence([1,2,3,4])); //true
console.log(isNonDecreasingSequence([1,255,53,0])); //false
console.log(isNonDecreasingSequence([0, 0.2, 0.3, 1])); //true

I personally feel that this is easier to read, but it is definitely an abuse of toString().

Is it best practice? Definitely not. Is it a viable solution to a problem? Possibly.

\$\endgroup\$
3
\$\begingroup\$
function increasing(element, index, array) {
  return index > 0 ? element > array[index-1] : true
}

[1,2,3].every(increasing)

If you want something like [1,2,3,3] to return true as well, change the element > array[index-1] to >=. I find this solution to be pretty readable.

Bonus ugly naming one-liner fun:

[1,2,3].every((e,i,a) => i > 0 ? e > a[i-1] : true)
\$\endgroup\$
3
\$\begingroup\$

Nevermind: I thought that the original code tries to skip over undefined values in array with this nested while loop, but turns out that this is just an awkward way to avoid going past the last element in array.


First off, it seems that the handling of undefined values in input is buggy:

isIncreasingSequence(1, 2, undefined, 3) // false

Shouldn't the undefined values be all skipped, returning true as a result?

Herein lies the main problem with this function. It's attempting to perform two distinct operations:

  • skip undefined values
  • check if numbers in array are sequential

As @kruga and @qntm have pointed out, it's easy to write a function that checks for the right ordering as long as the input only consists of numbers. Like so:

function isIncreasing(numbers) {
    return numbers.every((number, i) => i === 0 || numbers[i - 1] < number);
}

We could write a separate function that eliminates undefined values from our input array and then feed the result into order checking function. Well, we don't even need to write our own function for that, but could use _.without:

function containsIncreasingNumbers(...maybeNumbers) {
    return isIncreasing(_.without(maybeNumbers, undefined));
}
\$\endgroup\$
  • \$\begingroup\$ The input is described as a "sequence of numbers" so I think we can safely assume there are no undefineds there. \$\endgroup\$ – qntm Nov 15 '17 at 14:52
  • \$\begingroup\$ Rather than pull in a third-party library, a better way to filter an array is to use what's already part of the language: maybeNumbers.filter(n => n !== undefined). \$\endgroup\$ – qntm Nov 16 '17 at 1:23
  • \$\begingroup\$ Ah... I think I completely misunderstood what the OP code was trying to achieve with this while (numArr[num + 1] !== undefined) loop. \$\endgroup\$ – Rene Saarsoo Nov 16 '17 at 8:36
2
\$\begingroup\$

If you want to use higher order functions, you can use Array.prototype.reduce():

return false !== numbers.reduce(function(accumulator, x) {
        return typeof accumulator === "number" &&
            typeof x === "number" &&
            accumulator < x && x;
    });

The reductor uses short-circuit logic to either return false or the currently inspected list item.

\$\endgroup\$
  • \$\begingroup\$ This still requires reducing over the entire list, even though you could stop at the first non-increasing adjacent elements. \$\endgroup\$ – Joshua Taylor Nov 15 '17 at 13:58
  • \$\begingroup\$ This fails for the sequence [0, 0], returning true when it should return false. \$\endgroup\$ – qntm Nov 15 '17 at 14:50
  • \$\begingroup\$ @qntm: I had to take a look at OP’s code again to spot that they appear to want to accept only strictly monotonic series. I didn't see that in any of the description text. Anyway, I changed the comparison operator. \$\endgroup\$ – David Foerster Nov 15 '17 at 14:56
  • \$\begingroup\$ @DavidFoerster this isn't about the definition of "increasing". It also fails for [1, 0]. \$\endgroup\$ – qntm Nov 15 '17 at 14:56
  • \$\begingroup\$ It's failing because your return statement is on a line by itself, returning undefined. All the accumulator logic is never being hit. Maybe you had different formatting locally? \$\endgroup\$ – qntm Nov 15 '17 at 15:13
2
\$\begingroup\$

Your function is really easy to read and follow.
I, personally, hate the double-space indentation, but that's a preference.

But there are a few things that you can improve:

  • You have absolutely no input validation.
    Verifying that you have more than 2 arguments is enough, and should be accomplished before running Array.prototype.slice.call(arguments);.
    Array.prototype.slice is very slow for long arrays and array-like objects. The array-like object arguments has a length property, refering to how many arguments were provided. More ahead, you don't check if you are comparing numbers with strings, arrays, functions, regular expressions and what-not, which may lead to weird results.
  • Your for loop is not optimal:
    • You are starting from index 0.
      If you store the previous number into a local variable, you can start your loop at 1. This is 1 less iteration, 1 less check and 1 less increment.
    • You keep reading the numArr.length.
      Consider storing this value in a local variable.
      Many will say that it doesn't matter much, and that this won't make much of a difference. Which is true, for smaller arrays.
  • You are currently building a truthy table, and checking if there's any false in it.
    It is a lot easier if you simply return false; as soon as one of the conditions doesn't return true.
    This avoids forcing you to check every single item ahead needlessly, since you knew the result before finishing the loop.
  • Aditionally, in contrast to what @hoffmale suggests, do not use if (numArr[num] >= numArr[num + 1] || isNaN(numArr[num]) || isNaN(numArr[num + 1])).
    This is why I say it:

    1. The comparisson is made first, before typechecking
    2. The current number is checked
    3. The next number is checked (on the next iteration, the "current number" will be the "next number").

    This makes it so that you are checking the same number twice.
    Doing the typechecking before comparing, and doing only to the current number will reduce the required checks by a large amount.

As such, you can write your function like this (keeping your style intact):

function isIncreasingSequence() {
  /**Check if numbers sequence is increasing
  * @param {number} numbers - a sequence of input numbers;
  * @return {boolean} - true if given sequence is increasing, false othrewise
  */
  var length = arguments.length;

  if(length < 2)
  {
    throw new TypeError('At least 2 arguments are required');
  }

  var numbers = Array.prototype.slice.call(arguments);
  var old = numbers[0];

  if(isNaN(old))
  {
    throw new TypeError('Invalid number on position 0');
  }
  for (var i = 1; i < length; i++)
  {
    if(isNaN(numbers[i] / 1))
    {
      throw new TypeError('Invalid number on position ' + i);
    }

    if(old > numbers[i])
    {
      return false;
    }
    old = numbers[i];
  }

  return true;
}

But still, the code isn't optimal. Running the following code:

console.time('code');
for(var i = 1e4; i--; )isIncreasingSequence(0, 0.2, 0.3, 1);
console.timeEnd('code');

Shows that it still takes 4-5 milliseconds, on Google Chrome (on my pc), while @Kruga's ES6 answer is a lot faster (0.9-2 milliseconds).

Here are some improvements I've made, without any regards to keep the programming style integrity:

  • Got rid of Array.prototype.slice.call(arguments); and access the arguments object directly.
  • Store the current number in a variable, reducing one more iteration and multiple accesses to the array, speeding up the code a lot.
  • Start the loop at 2, instead of 0 or 1.

Here's how I've made it into:

function isIncreasingSequence() {
    /**Check if numbers sequence is increasing
    * @param {number} numbers - a sequence of input numbers;
    * @return {boolean} - true if given sequence is increasing, false othrewise
    */

    var length = arguments.length;
    if(length < 2)
    {
        throw new TypeError('At least 2 arguments are required');
    }

    var old = arguments[0] / 1;
    var current = arguments[1] / 1;

    if(isNaN(old))
    {
        throw new TypeError('Invalid number on position 0');
    }
    if(isNaN(current))
    {
        throw new TypeError('Invalid number on position 1');
    }

    if(old > current)
    {
        return false;
    }
    old = current;

    for (var i = 2; i < length; i++)
    {
        current = arguments[i] / 1;

        if(isNaN(current))
        {
            throw new TypeError('Invalid number on position ' + i);
        }

        if(old > current)
        {
            return false;
        }
        old = current;
    }

    return true;
}

Alternatively, you can use a do{...}while loop, like this, to dry the code:

function isIncreasingSequence() {
    /**Check if numbers sequence is increasing
    * @param {number} numbers - a sequence of input numbers;
    * @return {boolean} - true if given sequence is increasing, false othrewise
    */

    var length = arguments.length;
    if(length < 2)
    {
        throw new TypeError('At least 2 arguments are required');
    }

    var old = arguments[0] / 1;

    if(isNaN(old))
    {
        throw new TypeError('Invalid number on position 0');
    }

    var i = 1;
    var current;

    do
    {
        current = arguments[i] / 1;
        if(isNaN(current))
        {
            throw new TypeError('Invalid number on position ' + i);
        }

        if(old > current)
        {
            return false;
        }

        old = current;
    }
    while(++i < length);

    return true;
}

Another way to improve the performance is to use old !== old and current !== current instead of isNaN(...), but the difference is neglectible.

This final version, using the do...while loop takes exactly the same time as @Kruga's ES6 answer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.