Given an array arr[] of size N, the task is to find the count of subarrays with elements in alternate increasing-decreasing order or vice-versa. A subarray {a, b, c} will be valid if and only if either (a < b > c) or (a > b < c) is satisfied.
Examples:
Input: arr[] = {9, 8, 7, 6, 5}
Output: 4
Explanation: As each element is lesser than the other,
only consider the sequence of length 2, four times: [9, 8], [8, 7], [7, 6], [6, 5]Input: arr[] = {1, 2, 1, 2, 1}
Output: 10
Explanation: All possible sequences are: [1, 2, 1, 2, 1], [1, 2, 1, 2], [2, 1, 2, 1], [1, 2, 1],
[2, 1, 2], [1, 2, 1], [1, 2], [2, 1], [1, 2], [2, 1]
Approach: The task can be solved using a sliding window approach and mathematical concepts. The solution is built using the following steps:
- Find the longest current valid subarray.
- When the current longest valid subarray breaks, take the length of the subarray which was longest and store it in an array.
- Restart the window from the point where the previous longest subarray ended and find the next longest window and repeat till the array finishes.
- The array will have the length of contiguous subarrays in it which are non-overlapping.
- For each window of size k, which is a valid subarray, all possible windows of any size are also valid subsequences.
- To find all possible subsequences in a window, if one window is k, then count of all subarrays of all sizes = k x (k-1) /2
- Do this for each window size in the array and add it to count.
- Return count as final answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count // of valid subarrays int getSubsequenceCount(vector< int >& nums) { bool flag = false ; vector< int > arr; int i = 0, j = 1; while (j < nums.size()) { if ((nums[j] > nums[j - 1] && flag != true ) || (nums[j] < nums[j - 1] && flag != false )) { if (nums[j] > nums[j - 1]) flag = true ; else if (nums[j] < nums[j - 1]) flag = false ; j += 1; } else { if (j - i != 1) { arr.push_back(j - i); flag = false ; i = j - 1; } else { i = j; j += 1; } } } if (j - i != 1) arr.push_back(j - i); int count = 0; // Number of valid subsequences for ( int itm : arr) count += itm * (itm - 1) / 2; return count; } int main() { // Driver code vector< int > nums = { 1, 2, 1, 2, 1 }; cout << getSubsequenceCount(nums) << "\n" ; } // This code is contributed by Taranpreet |
Java
// Java program for the above approach import java.util.ArrayList; class GFG { // Function to find the count // of valid subarrays static int getSubsequenceCount( int [] nums) { boolean flag = false ; ArrayList<Integer> arr = new ArrayList<Integer>(); int i = 0 , j = 1 ; while (j < nums.length) { if ((nums[j] > nums[j - 1 ] && flag != true ) || (nums[j] < nums[j - 1 ] && flag != false )) { if (nums[j] > nums[j - 1 ]) flag = true ; else if (nums[j] < nums[j - 1 ]) flag = false ; j += 1 ; } else { if (j - i != 1 ) { arr.add(j - i); flag = false ; i = j - 1 ; } else { i = j; j += 1 ; } } } if (j - i != 1 ) arr.add(j - i); int count = 0 ; // Number of valid subsequences for ( int itm : arr) count += itm * (itm - 1 ) / 2 ; return count; } public static void main(String args[]) { // Driver code int [] nums = { 1 , 2 , 1 , 2 , 1 }; System.out.println(getSubsequenceCount(nums)); } } // This code is contributed gfgking |
Python3
# Python program for the above approach # Function to find the count # of valid subarrays def getSubsequenceCount(nums): flag = None length = 1 arr = [] i, j = 0 , 1 while j < len (nums): if (nums[j] > nums[j - 1 ] and flag ! = True ) \ or (nums[j] < nums[j - 1 ] \ and flag ! = False ): if (nums[j] > nums[j - 1 ]): flag = True elif (nums[j] < nums[j - 1 ]): flag = False j + = 1 else : if (j - i ! = 1 ): arr.append(j - i) flag = None i = j - 1 else : i = j j + = 1 if (j - i ! = 1 ): arr.append(j - i) count = 0 # Number of valid subsequences for n in arr: count + = n * (n - 1 ) / / 2 return count # Driver code if __name__ = = "__main__" : nums = [ 1 , 2 , 1 , 2 , 1 ] print (getSubsequenceCount(nums)) |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG{ // Function to find the count // of valid subarrays static int getSubsequenceCount( int [] nums) { bool flag = false ; List< int > arr = new List< int >(); int i = 0, j = 1; while (j < nums.Length) { if ((nums[j] > nums[j - 1] && flag != true ) || (nums[j] < nums[j - 1] && flag != false )) { if (nums[j] > nums[j - 1]) flag = true ; else if (nums[j] < nums[j - 1]) flag = false ; j += 1; } else { if (j - i != 1) { arr.Add(j - i); flag = false ; i = j - 1; } else { i = j; j += 1; } } } if (j - i != 1) arr.Add(j - i); int count = 0; // Number of valid subsequences foreach ( int itm in arr) count += itm * (itm - 1) / 2; return count; } static public void Main () { // Driver code int [] nums = { 1, 2, 1, 2, 1 }; Console.WriteLine(getSubsequenceCount(nums)); } } // This code is contributed Shubham Singh |
Javascript
<script> // JavaScript program for the above approach // Function to find the count // of valid subarrays const getSubsequenceCount = (nums) => { let flag = 0; let length = 1; let arr = []; let i = 0, j = 1; while (j < nums.length) { if ((nums[j] > nums[j - 1] && flag != true ) || (nums[j] < nums[j - 1] && flag != false )) { if (nums[j] > nums[j - 1]) flag = true ; else if (nums[j] < nums[j - 1]) flag = false ; j += 1; } else { if (j - i != 1) { arr.push(j - i) flag = false ; i = j - 1; } else { i = j; j += 1 } } } if (j - i != 1) arr.push(j - i); let count = 0; // Number of valid subsequences for (let itm in arr) count += parseInt(arr[itm] * (arr[itm] - 1) / 2) return count; } // Driver code nums = [1, 2, 1, 2, 1]; document.write(getSubsequenceCount(nums)); // This code is contributed by rakeshsahni </script> |
10
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!