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

Nibelung

Answer 1

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;

}

Nellenelli

Thank you! This is a great solution! Another thing I might add is that sign = arr[e] - arr[s] might come inside the first while. And if the size is 1 then that means its the same number so we have to increase e by 1 or else it keeps looping on cases like [10,10,10]. I will edit the question with the python implementation of this solution. Thanks again! – Nibelung

Answer 2

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

Genteelism

Answer 3

I think this is a simple DP problem. The idea is to know the number of subarrays ending at i that can be extended from the previous alternating state (increasing/decreasing). If the current element is lower than the previous element it can contribute to the already increasing subarray ending at the previous state (i-1) or vice-versa.

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> arr) {
    int n = arr.size(), ans = 0;
    // vector<vector<int>> dp(n, vector<int>(2, 0));
    int inc = 0, dec = 0;
    for(int i = 1; i < n; i++) {
        if (arr[i] > arr[i-1]) {
            // dp[i][0] = dp[i-1][1] + 1;
            inc = dec + 1;
            dec = 0;
        } else if (arr[i] < arr[i-1]) {
            // dp[i][1] = dp[i-1][0] + 1;
            dec = inc + 1;
            inc = 0;
        } else {
            inc = 0, dec = 0;
        }
        // ans += dp[i][0] + dp[i][1];
        ans += (inc + dec);
    }
    cout << ans << endl;
}

int main() {
    auto inp = {-442024811,447425003,365210904,823944047,943356091,-781994958,872885721,-296856571,230380705,944396167,-636263320,-942060800,-116260950,-126531946,-838921202};
    solve(inp);
    return 0;
}

Milla

Answer 4

Here's my solution using dynamic programming. This is a bit more readable to me than the accepted answer (or the added answer in the OP), although there's probably still room for improvement.

O(n) time and O(1) space.

def solution(arr):
    # holds the count of sawtooths at each index of our input array,
    # for sawtooth lengths up to that index
    saws = [0 for x in range(0, len(arr))]
    # the resulting total sawtooth counts
    totalSawCounts = 0
    previousCount = 0

    for currIdx in range(1, len(arr)):
        currCount = 0
        before = currIdx -1
        if (arr[currIdx] > arr[before]):
            goingUp = True
        elif (arr[currIdx] < arr[before]):
            goingUp = False
        else:
            break

        # if we made it here, we have at least one sawtooth
        currCount =  1

        # see if there was a previous solution (the DP part)
        # and if it continues our current sawtooth
        if before >= 1:
            if goingUp:
                if arr[before-1] > arr[before]:
                    currCount = previousCount + currCount
            else:
                if arr[before-1] < arr[before]:
                    currCount = previousCount + currCount
        previousCount = currCount
        totalSawCounts = totalSawCounts + currCount

    return totalSawCounts

Test cases:

arr = [9,8,7,6,5]
print(solution(arr)) # 4

arr2 = [1,2,1,3,4,-2]
print(solution(arr2)) # 9

arr3 = [1,2,1,2,1]
print(solution(arr3)) # 10

arr4 = [10,10,10]
print(solution(arr4)) # 0

# from medium article comments
arr5 = [-442024811,447425003,365210904,823944047,943356091,-781994958,872885721,-296856571,230380705,944396167,-636263320,-942060800,-116260950,-126531946,-838921202]
print(solution(arr5)) # 31

Campion

Hey there, I know this an old post but I can't seem to wrap my head around how totalSawCounts = totalSawCounts + currCount seems to give you all sawtooth substrings leading up to currIdx? – Cotyledon

why are we doing currCount = previousCount + currCount? – Kimura

@Campion @Divyam Khanna How the sawtooth length currCount = previousCount + currCount is related to the number of subarrays? – Kimura

@Kimura when we get to that nested if condition it means that our current index is a continuing sawtooth and so we can use the previous index sawtooth count and add it to our current count. – Campion

@Cotyledon adding the currCount to totalSawCounts here because we do have indeed at least 1 new sawtooth (of length 2) for the current index. – Campion

@Campion can you help me understand how index sawtooth is related to getting continuous subarrays? – Kimura

"it means that our current index is a continuing sawtooth and so we can use the previous index sawtooth count and add it to our current count". Am I right to assume that this is very similar to prefixsum algorithm? Because now it all seems to add up. – Cotyledon

@Campion Thanks you for your solution. May I know why "currCount = previousCount + currCount" works? I thought to count the number of subarrays, there's a combination formula "n * (n - 1) / 2" then + n for each len = 1 subarrays. – Clo

Answer 5

Below is a very simple and straightforward solution with a single for loop

import math

def comb(x):
    st = 0
    total_comb = 0
    if len(x) < 2: #edge case
        return 0
    if len(x) == 2: #edge case
        return 2
    
    seq_s = 0
    for i in range(1, len(x)-1): 
        if  (x[i]<x[i-1] and x[i]<x[i+1]) or (x[i]>x[i-1] and x[i]>x[i+1]):
            continue
        else:
            print(x[seq_s:i+1])
            if i+1-seq_s == 2 and x[i] == x[i-1]: #means we got two same nums like 10, 10
                pass
            else: total_comb+=math.comb(i+1-seq_s,2)
            seq_s=i
            i+=1
            
    print(x[seq_s:])
    if i+1-seq_s == 2 and x[i] == x[i-1]: #means we got two same nums like 10, 10
        pass
    else: total_comb+=math.comb(len(x)-seq_s,2)
    return total_comb
    

x= [1,2,1,3,4,-2]
print(comb(x))

Outgroup

Answer 6

Used gradient method.

Passes all test cases

from math import comb
def solution(arr):
    
    n=len(arr)
    
    if arr[1]!=arr[0]:
        l=2
        
    else:
        l=0
    pre=arr[1]-arr[0]
    ans=0
    
    for i in range(2,n):
        cur=arr[i]-arr[i-1]
        
        if cur*pre<0:
            l+=1
        else:
            if l==2:
                ans+=1
            elif l==0:
                ans+=0
            else:
                ans+=comb(l,2)
            if cur!=0:
                l=2
            else:
                l=0
        pre=cur
    if l==2:
        ans+=1
    elif l==0:
        ans+=0
    else:
        ans+=comb(l,2)
    return ans

Semiautomatic

Answer 7

I think the trick here is to realise that: assuming you have a valid sawtooth sequence of length x, adding one additional valid element would increase the number of subsequences by x too.

Example:

• [1,2,1] is a valid sawtooth sequence.

• adding 2 to this valid sequence of [1,2,1] forms [1,2,1,2]. We see here that adding a new element to a valid sequence of length 3 here adds 3 new valid subsequences which are: [1,2,1,2],[2,1,2], and [1,2].

• Correspondingly, adding another valid element such as -1 to [1,2,1,2] would add 4 new subsequences which are: [1,2,1,2,-1], [2,1,2,-1],[1,2,-1],and [2,-1].

Thus, what we can use a moving window with left and right pointers l and r to keep track of the length of valid sequence, reseting the l pointer when an invalid sequence is detected.

.

def solution(arr: list) -> int:
    '''
    for every char, check if still current sawtooth
    if still currently sawtooth, numberOfWays += length
    else reset temp counter
    '''
    l, r = 0, 1
    ways = 0
    while r < len(arr):

        # check if current char + past 2 chars are sawtooth
        if r-l > 1 and (arr[r-2] < arr[r-1] > arr[r] or
                        arr[r-2] > arr[r-1] < arr[r]):  
            ways += r-l

        # check if current char + past 1 chars are sawtooth
        elif arr[r-1] != arr[r]:                
            ways += 1
            l = r-1

        else:                                   
            # reset left pointer
            l = r

        r += 1
    return ways

Animality

Answer 8

I did something extremely simple but it gave the correct answers for all the test cases you provided:

function sawtooth(arr) {
  if (arr.length < 2) return 0;
  
  let previousLongest = 1;
  let result = 0;
  for (let i = 1; i < arr.length; i++) {
    if (i >= arr.length) break;
    if (arr[i - 1] === arr[i]) continue;
    if (arr[i - 1] > arr[i] && arr[i] < arr[i + 1] || arr[i - 1] < arr[i] && arr[i] > arr[i + 1]) {
      previousLongest += 1;
    } else {
      previousLongest = 1;
    }
    result += previousLongest;
  }
  return result;
}

Aviate

Answer 9

I had the same problem and took an approach similar to @appu but I kept track of the negative/positive changes slightly differently.

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0

        last_sign = None
        count = 0 # total number of sawteeth
        streak = 0

        for i in range(1, n):
            if nums[i] == nums[i - 1]:
                last_sign = None
                streak = 0
                continue   

            diff = nums[i] - nums[i - 1]

            # handle positive/negative changes
            if (diff > 0 and last_sign != 1) or (diff < 0 and last_sign != -1):
                streak += 1
                last_sign = 1 if diff > 0 else -1
            else:
                # handle broken streak
                streak = 1
            count += streak

        return count

Midget