Counting contiguous sawtooth subarrays-CodePudding

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

CodePudding user response：

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;

}