Given an array of integers and k, find the difference between the number of the strictly increasing number of subarrays (of size more than one) and the number of the strictly decreasing subarray in the window of size k.
Examples:
Input : nums = {10, 20, 30, 15, 15};
k = 3;
Output : 3, 0, -1
Explanation
For the first window of [10, 20, 30], there are
3 increasing subranges ([10, 20, 30], [10, 20],
and [20, 30]) and 0 decreasing, so the answer
is 3. For the second window of [20, 30, 15],
there is 1 increasing subrange and 1 decreasing,
so the answer is 0. For the third window of
[20, 15, 15], there is 1 decreasing subrange
and 0 increasing, so the answer is -1.
We need to calculate the difference between increasing and decreasing subarrays for each of the window of size K. We iterate through the array and for each of the window of size k, we calculate the number of increasing and decreasing subarrays and insert the difference of them in the output array.
- Create two arrays of size N and initialize them by zero and create the output array.
- Iterate through array
- Calculate the numbers of increasing subarrays
- Calculate the decreasing subarrays
- Insert the difference between increasing and decreasing subarrays in output array.
Time Complexity of the solution: O(n*k)
n = Size of the array
k = Window size
Implementation:
C++
// CPP program to count the differences #include <iostream>#include <vector>using namespace std;// function to calculate the differencevector<int> Diffs(vector<int> const& a, int k){ vector<int> out; vector<int> inc, dec; // initializing inc and dec with 0 and resizing // equal to the size of main array inc.resize(a.size(), 0); dec.resize(a.size(), 0); int inc_sum = 0; int dec_sum = 0; // iterate through the array for (int i = 0; i < a.size(); ++i) { // finding number of increasing // subarrays in a window size k for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] > a[j]; --j) { ++inc[j]; ++inc_sum; } // Finding number of decreasing subarrays // in a window size k for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] < a[j]; --j) { ++dec[j]; ++dec_sum; } // calculate the difference if (i >= k - 1) { // if this is not the first window then // calculate inc_sum and dec_sum if (i >= k) { inc_sum -= inc[i - k]; dec_sum -= dec[i - k]; } // insert the difference in k size window // in the output vector out.push_back(inc_sum - dec_sum); } } return out;}// driver programint main(){ vector<int> out = Diffs({ 10, 20, 30, 15, 15}, 3); for (int n : out) cout << n << ", "; return 0;} |
Java
// JAVA program to count the differences import java.util.*;class GFG{// function to calculate the differencestatic Vector<Integer> Diffs(int []a, int k){ Vector<Integer> out = new Vector<Integer>(); int [] inc, dec; // initializing inc and dec with 0 and resizing // equal to the size of main array inc = new int[a.length]; dec = new int[a.length]; int inc_sum = 0; int dec_sum = 0; // iterate through the array for (int i = 0; i < a.length; ++i) { // finding number of increasing // subarrays in a window size k for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] > a[j]; --j) { ++inc[j]; ++inc_sum; } // Finding number of decreasing subarrays // in a window size k for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] < a[j]; --j) { ++dec[j]; ++dec_sum; } // calculate the difference if (i >= k - 1) { // if this is not the first window then // calculate inc_sum and dec_sum if (i >= k) { inc_sum -= inc[i - k]; dec_sum -= dec[i - k]; } // insert the difference in k size window // in the output vector out.add(inc_sum - dec_sum); } } return out;}// Driver codepublic static void main(String[] args){ int []arr = { 10, 20, 30, 15, 15}; Vector<Integer>out = Diffs(arr, 3); for (int n : out) System.out.print(n + ", ");}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to count the differences # Function to calculate the difference def Diffs(a, k): out, inc, dec = [], [0] * len(a), [0] * len(a) # Initializing inc and dec with 0 and # resizing equal to the size of main array inc_sum, dec_sum = 0, 0 # Iterate through the array for i in range(0, len(a)): # Finding number of increasing # subarrays in a window size k j = i - 1 while (j >= 0 and j > i - k and a[j + 1] > a[j]): inc[j] += 1 inc_sum += 1 j -= 1 # Finding number of decreasing # subarrays in a window size k j = i - 1 while (j >= 0 and j > i - k and a[j + 1] < a[j]): dec[j] += 1 dec_sum += 1 j -= 1 # calculate the difference if i >= k - 1: # if this is not the first window then # calculate inc_sum and dec_sum if i >= k: inc_sum -= inc[i - k] dec_sum -= dec[i - k] # insert the difference in k size window # in the output vector out.append(inc_sum - dec_sum) return out # Driver Codeif __name__ == "__main__": out = Diffs([10, 20, 30, 15, 15], 3) for n in out: print(n, end = ", ") # This code is contributed by Rituraj Jain |
C#
// C# program to count the differences using System;using System.Collections.Generic;class GFG{// function to calculate the differencestatic List<int> Diffs(int []a, int k){ List<int> Out = new List<int>(); int [] inc, dec; // initializing inc and dec with 0 and resizing // equal to the size of main array inc = new int[a.Length]; dec = new int[a.Length]; int inc_sum = 0; int dec_sum = 0; // iterate through the array for (int i = 0; i < a.Length; ++i) { // finding number of increasing // subarrays in a window size k for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] > a[j]; --j) { ++inc[j]; ++inc_sum; } // Finding number of decreasing subarrays // in a window size k for (int j = i - 1; j >= 0 && j > i - k && a[j + 1] < a[j]; --j) { ++dec[j]; ++dec_sum; } // calculate the difference if (i >= k - 1) { // if this is not the first window then // calculate inc_sum and dec_sum if (i >= k) { inc_sum -= inc[i - k]; dec_sum -= dec[i - k]; } // insert the difference in k size window // in the output vector Out.Add(inc_sum - dec_sum); } } return Out;}// Driver codepublic static void Main(String[] args){ int []arr = { 10, 20, 30, 15, 15}; List<int>Out = Diffs(arr, 3); foreach (int n in Out) Console.Write(n + ", ");}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Js program to count the differences // function to calculate the differencefunction Diffs( a, k){ let out = []; let inc, dec; // initializing inc and dec with 0 and resizing // equal to the size of main array inc = []; dec = []; for(let i = 0;i<a.length;i++){ inc.push(0); dec.push(0); } let inc_sum = 0; let dec_sum = 0; // iterate through the array for (let i = 0; i < a.length; ++i) { // finding number of increasing // subarrays in a window size k for (let j = i - 1; j >= 0 && j > i - k && a[j + 1] > a[j]; --j) { ++inc[j]; ++inc_sum; } // Finding number of decreasing subarrays // in a window size k for (let j = i - 1; j >= 0 && j > i - k && a[j + 1] < a[j]; --j) { ++dec[j]; ++dec_sum; } // calculate the difference if (i >= k - 1) { // if this is not the first window then // calculate inc_sum and dec_sum if (i >= k) { inc_sum -= inc[i - k]; dec_sum -= dec[i - k]; } // insert the difference in k size window // in the output vector out.push(inc_sum - dec_sum); } } return out;}// driver programlet out = Diffs([10, 20, 30, 15, 15], 3);document.write(out)// This code is contributed by rohitsingh07052.</script> |
Output:
3, 0, -1,
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
