data structures - Algorithm Saw Sequence

Question

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]))

Answer 1

Finally, I have found solution with O(n).

Here is the solution:

function sawSequenceImprove(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;
    if (number[0] > number[1] || number[1] > number[0]) {
        sawCount = 1;
    }
    let count = 0;
    let isLastConsArr = false;
    let startIndex = 0;
    for (let i = 2; i < number.length; i++) {
      // check sequence / and /
      if (
          (i - 2) >= 0 && 
          ((number[i - 2] < number[i - 1] && number[i - 1] > number[i]) ||
          (number[i - 2] > number[i - 1] && number[i - 1] < number[i]))
        ) {
        count += (2 + startIndex);
        const isDown = number[i - 1] > number[i];
        //checking last condition
        if (number[i] === number[i + 1] || 
            (isDown && number[i] > number[i+1]) || 
            (!isDown && number[i] < number[i+1]) || 
            (i + 1 === number.length)) {
            isLastConsArr = true
        }
        startIndex += 1
      }
      else if (number[i - 1] > number[i] || number[i - 1] < number[i]) {
          sawCount += 1
          count = 0
      }
      
      if (isLastConsArr) {
        sawCount += count
        isLastConsArr = false
        startIndex = 0
      }
    }
    return sawCount
}
console.log(sawSequenceImprove([-14, -10, -20, -8, -10, 3, 2, 5, 5, 4, 6, 2, 3]))
console.log(sawSequenceImprove([1, 2, 1, 3, 2]))
console.log(sawSequenceImprove([9, 8, 7, 6, 5]))
console.log(sawSequenceImprove([-14, -10, -20, -8, -10, 3, 2, 5, 5, 4]))