Counting contiguous sawtooth subarrays

Question

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.

What would be the best way to solve this question? I saw a possible solution here:https://medium.com/swlh/sawtooth-sequence-java-solution-460bd92c064

But this code fails for the case [1,2,1,3,4,-2] where the answer should be 9 but it comes as 12.

I have even tried a brute force approach but I am not able to wrap my head around it. Any help would be appreciated!

EDIT: Thanks to Vishal for the response, after a few tweaks, here is the updated solution in python. Time Complexity: O(n) Space Complexity: O(1)

def samesign(a,b):
    if a/abs(a) == b/abs(b):
        return True
    else:
        return False

def countSawSubarrays(arr):
    n = len(arr)
    
    if n<2:
        return 0

    s = 0
    e = 1
    count = 0
    
    while(e<n):
        sign = arr[e] - arr[s]
        while(e<n and arr[e] != arr[e-1] and samesign(arr[e] - arr[e-1], sign)):
            sign = -1*sign
            e+=1
        size = e-s
        if (size==1):
            e+=1
        count += (size*(size-1))//2
        s = e-1
        e = s+1
    return count

arr1 = [9,8,7,6,5]
print(countSawSubarrays(arr1))
arr2 = [1,2,1,3,4,-2]
print(countSawSubarrays(arr2))
arr3 = [1,2,1,2,1]
print(countSawSubarrays(arr3))
arr4 = [10,10,10]
print(countSawSubarrays(arr4))

Result: 4 9 10 0

Answer 1

I was stuck on this for a while when doing a similar practice problem before finally having an "ah-ha" moment and getting a pretty short and elegant solution.

• As we iterate, every time we flip between increasing and decreasing of subarray length 2, the number of contiguous arrays goes up by the current streak of flips in a row. e.g. [1, 2, 1, 2, 1] has 4 flips in a row so 1 + 2 + 3 + 4 = 10
• When we break out of a sawtooth streak, that is, when we increase twice in a row or decrease twice in a row, the longest contiguous subarray now is just 2, so we reset the counter to 1 if the two values are not equal (since that is a valid sawtooth) or 0 if the values are the same.
• Example with streaks and broken streaks: [1, 7, 3, 4, 5]. we maintain a streak of 3 as we iterate ([1, 7], [7, 3], [3, 4]), then [4, 5] breaks this streak since [3, 4] was also increasing, so we have the final count as (3 + 2 + 1) + 1 = 7 possible sawtooths.

def solution(arr):
    if len(arr) < 2:
        return 0

    count = 0
    streak = 0
    prev_increasing = None

    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            prev_increasing = None
            streak = 0
        else:
            curr_increasing = arr[i] > arr[i-1]
            if curr_increasing != prev_increasing:
                # keep track of streak of flips between increasing and decreasing
                streak += 1
                prev_increasing = curr_increasing
            else:
                # when we break out of a streak, we reset the streak counter to 1
                streak = 1

            # number of sawtooth contiguous subarrays goes up by the current streak
            count += streak

    return count

Answer 2

This can be solved by just splitting the array into multiple sawtooth sequences..which is O(n) operation. For example [1,2,1,3,4,-2] can be splitted into two sequence [1,2,1,3] and [3,4,-2] and now we just have to do C(size,2) operation for both the parts.

Here is psedo code explaining the idea ( does not have all corner cases handled )

 public int countSeq(int[] arr) {
int len = arr.length;
if (len < 2) {
  return 0;
}

int s = 0;
int e = 1;
int sign = arr[e] - arr[s];
int count = 0;

while (e < len) {
  while (e < len && arr[e] - arr[e-1] != 0 && isSameSign(arr[e] - arr[e-1], sign)) {
    sign = -1 * sign;
    e++;
  }
  // the biggest continue subsequence starting from s ends at e-1;
  int size = e - s;
  count = count + (size * (size - 1)/2); // basically doing C(size,2)
  s = e - 1;
  e = s + 1;
}

return count;

}