Algorithm Saw Sequence

A saw sequence is a sequence of number that alternate between increasing and decreasing. In other words, each element is either strictly greater than it's neighboring element or strictly less than it's neighboring elements.

Problem Statement:

Given an array of integers arr, your task is to count the number of contiguous subarrays that represent a sawtooth sequence of at least two elements.

• For arr = [9, 8, 7, 6, 5], the output should be countSawSubarrays(arr) = 4.

  Since all the elements are arranged in decreasing order, it won't be possible to form any sawtooth subarray of length 3 or more. There are 4 possible subarrays containing two elements, so the answer is 4.

• For arr = [10, 10, 10], the output should be countSawSubarrays(arr) = 0 Since all of the elements are equal, none of subarrays can be sawtooth, so the answer is 0.

• For arr = [1, 2, 1, 2, 1], the output should be countSawSubarrays(arr) = 10.

  All contiguous subarrays containing at least two elements satisfy the condition of the problem. There are 10 possible contiguous subarrays containing at least two elements, so the answer is 10.

Here is my solution for saw sequence

function sawSequence(number) {      // best case      if (number.length === 0 || number.length === 1) {          return 0      }            if (number.length === 2 && ( number[0] > number[1] || number[1] > number[0])) {          return 1      }            let sawCount = 0;      for (let i = 0; i < number.length; i++) {          let prev = number[i];          let pattern = '-';          for (let j = (i + 1); j < number.length; j++) {              if (number[j] > prev && (pattern === 'down' || pattern === '-')) {                  pattern = 'up'                  sawCount += 1;              } else if (number[j] < prev && (pattern === 'up' || pattern === '-')) {                  pattern = 'down'                  sawCount += 1;              } else {                  break;              }              prev = number[j]          }      }      return sawCount  }    console.log(sawSequence([-14, -10, -20, -8, -10, 3, 2, 5, 5, 4]))

my solution get rejected because of time limit is 4s, I don't know the test case yet. My Question, is there any efficient to improve this algorithm ?

thanks

https://stackoverflow.com/questions/65590317/algorithm-saw-sequence January 06, 2021 at 12:42PM