2
\$\begingroup\$

I wrote a function in JavaScript that expects an array of integers (negative or positive) and determines if that array has an increasing sequence.

For the sake of better time performance I made the function return out of the loop with false as soon as i+1 - i did not equal 1 or -1. I used continue to do this. Here is the function:

const increasingSequence = (arr) => {
    for (let i = 0; i < arr.length - 1; i ++) {
      if (arr[i+1] - arr[i] === 1 || arr[i+1] - arr[i] === -1) {
        continue;
      } else {
        return false;
      }
    }
    return true;
  }

Seems to be producing the desired output:

var arr1 = [1, 2, 3, 4];
var arr2 = [1, 2, 4, 5];
var arr3 = [-4, -3, -2, -1];
var arr4 = [-4, -3, -1, 0];

increasingSequence(arr1); // true
increasingSequence(arr2); // false
increasingSequence(arr3); // true
increasingSequence(arr4); // false

This is actually a helper function to a bigger problem I'm trying to solve, so time complexity is important. Feedback about improving time complexity or any missing edge cases would be greatly appreciated.

\$\endgroup\$
7
\$\begingroup\$

Your code has a bug because it will accept decreasing sequences as true as well, for example, increasingSequence([4,3,2,1]); will be true.

Having said that, you could do the tests a whole lot simpler by using a search:

  const increasingSequence = (arr) => !arr.some((val, idx) => val != arr[0] + idx);

How does that work? Well, each element in the array is expected to be the value of the first item, plus the index address of the current item, so, if the first value is 4 then the 3rd value will be expected to be 6 (4 + 2).

The above code simply looks for any value that does not meet those expectations.

If there is a value that does not meet the expectations, the some returns true, so we negate that, and return false.

Since the some(...) method is a short-circuiting function so it will terminate when the first mismatch is encountered (just like your logic).

Also, note that the short-circuit does not impact the time-complexity of the function, it is still \$O(N)\$ because the performance will scale linearly in relation to the number of elements.

You can see this running on Ideone.

\$\endgroup\$
  • 1
    \$\begingroup\$ Rather than !arr.some followed by a negative test, you might make the logic clearer if you used every and a positive test: const increasingSequence = (arr) => arr.every((val, idx) => val === arr[0] + idx); \$\endgroup\$ – CertainPerformance Jul 5 '18 at 22:49
  • \$\begingroup\$ @CertainPerformance - good point. As it happens, I used some(...) earlier today in my real job, and it came to mind first. I should have taken that extra step to make it more readable - even reviewed code can be reviewed. \$\endgroup\$ – rolfl Jul 5 '18 at 23:29
3
\$\begingroup\$

Your if/else statement could be shorter, I don't know if it makes much difference, but might be more to the point...

your code:

const increasingSequence = (arr) => {
    for (let i = 0; i < arr.length - 1; i ++) {
      if (arr[i+1] - arr[i] === 1 || arr[i+1] - arr[i] === -1) {
        continue;
      } else {
        return false;
      }
    }
    return true;
  }

instead of performing a continue you could invert the condition and return false, removing the else statement completely, like this:

const increasingSequence = (arr) => {
    for (let i = 0; i < arr.length - 1; i ++) {
      if !(arr[i+1] - arr[i] === 1 || arr[i+1] - arr[i] === -1) {
        return false;
      }
    }
    return true;
  }
\$\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.