Count strictly decreasing subarrays
In this problem, we are given an array of integers, and we need to count the number of strictly decreasing subarrays in the given array. A subarray is defined as a contiguous sequence of elements within the array. A strictly decreasing subarray is a subarray in which each element is strictly smaller than the previous element.
For example, let's consider the array [1, 2, 1, 0, 2, 1, 6, 4, 2]. The strictly decreasing subarrays in this array are [2, 1], [2, 1, 0], [1, 0], [2, 1], [6, 4], [4, 2], and [6, 4, 2]. So the total count of strictly decreasing subarrays in this case is 7.
Solution Approach
To solve this problem, we can use dynamic programming. We create an auxiliary array, dp[], of the same size as the input array. The dp[] array will store the count of strictly decreasing subarrays ending at each index.
We initialize the dp[] array with all zeros. Then, we iterate through the input array from the second element onwards. At each index, if the previous element is greater than the current element, it indicates the start of a decreasing subarray. We update dp[i] as dp[i-1] + 1, which means we extend the previous subarray by one element. We also increment a counter variable, count, by dp[i] to keep track of the total count of strictly decreasing subarrays.
Finally, we print the input array and the count of strictly decreasing subarrays.
Code Solution
// C Program
// Count strictly decreasing subarrays
#include <stdio.h>
// Display given array elements
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
void countDecreasingArr(int arr[], int n)
{
int count = 0;
int dp[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
printArr(arr, n);
printf(" Decreasing subarrays : %d \n", count);
}
int main()
{
// Arrays
int a[] = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int b[] = {
2 , 4 , 6 , 7
};
int c[] = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
countDecreasingArr(c, l3);
return 0;
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Java Program
Count strictly decreasing subarrays
*/
public class Subarrays
{
// Display given array elements
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
public void countDecreasingArr(int[] arr, int n)
{
int count = 0;
int[] dp = new int[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
printArr(arr, n);
System.out.print(" Decreasing subarrays : " + count + " \n");
}
public static void main(String[] args)
{
Subarrays task = new Subarrays();
int[] a = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int[] b = {
2 , 4 , 6 , 7
};
int[] c = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = a.length;
int l2 = b.length;
int l3 = c.length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Count strictly decreasing subarrays
*/
class Subarrays
{
public:
// Display given array elements
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
void countDecreasingArr(int arr[], int n)
{
int count = 0;
int dp[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
this->printArr(arr, n);
cout << " Decreasing subarrays : " << count << " \n";
}
};
int main()
{
Subarrays *task = new Subarrays();
int a[] = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int b[] = {
2 , 4 , 6 , 7
};
int c[] = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task->countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task->countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task->countDecreasingArr(c, l3);
return 0;
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
// Include namespace system
using System;
/*
Csharp Program
Count strictly decreasing subarrays
*/
public class Subarrays
{
// Display given array elements
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public void countDecreasingArr(int[] arr, int n)
{
int count = 0;
int[] dp = new int[n];
// Set zero to all slot
for (int i = 0; i < n; ++i)
{
dp[i] = 0;
}
for (int i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
this.printArr(arr, n);
Console.Write(" Decreasing subarrays : " + count + " \n");
}
public static void Main(String[] args)
{
Subarrays task = new Subarrays();
int[] a = {
1 , 2 , 1 , 0 , 2 , 1 , 6 , 4 , 2
};
int[] b = {
2 , 4 , 6 , 7
};
int[] c = {
5 , 5 , 2 , 4 , 6 , 7
};
// Get the size
int l1 = a.Length;
int l2 = b.Length;
int l3 = c.Length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
package main
import "fmt"
/*
Go Program
Count strictly decreasing subarrays
*/
// Display given array elements
func printArr(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func countDecreasingArr(arr[] int, n int) {
var count int = 0
// Set zero to all slot
var dp = make([] int, n)
for i := 1 ; i < n ; i++ {
if arr[i - 1] > arr[i] {
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1
// Add counter
count += dp[i]
}
}
printArr(arr, n)
fmt.Print(" Decreasing subarrays : ", count, " \n")
}
func main() {
var a = [] int {
1,
2,
1,
0,
2,
1,
6,
4,
2,
}
var b = [] int {
2,
4,
6,
7,
}
var c = [] int {
5,
5,
2,
4,
6,
7,
}
// Get the size
var l1 int = len(a)
var l2 int = len(b)
var l3 int = len(c)
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
countDecreasingArr(a, l1)
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
countDecreasingArr(b, l2)
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
countDecreasingArr(c, l3)
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
<?php
/*
Php Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
public function printArr($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
echo("\n");
}
public function countDecreasingArr($arr, $n)
{
$count = 0;
// Set zero to all slot
$dp = array_fill(0, $n, 0);
for ($i = 1; $i < $n; ++$i)
{
if ($arr[$i - 1] > $arr[$i])
{
// When decreasing subarray occurs
$dp[$i] = $dp[$i - 1] + 1;
// Add counter
$count += $dp[$i];
}
}
$this->printArr($arr, $n);
echo(" Decreasing subarrays : ".$count." \n");
}
}
function main()
{
$task = new Subarrays();
$a = array(1, 2, 1, 0, 2, 1, 6, 4, 2);
$b = array(2, 4, 6, 7);
$c = array(5, 5, 2, 4, 6, 7);
// Get the size
$l1 = count($a);
$l2 = count($b);
$l3 = count($c);
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
$task->countDecreasingArr($a, $l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
$task->countDecreasingArr($b, $l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
$task->countDecreasingArr($c, $l3);
}
main();
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Node JS Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
printArr(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
countDecreasingArr(arr, n)
{
var count = 0;
// Set zero to all slot
var dp = Array(n).fill(0);
for (var i = 1; i < n; ++i)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
}
this.printArr(arr, n);
console.log(" Decreasing subarrays : " + count );
}
}
function main()
{
var task = new Subarrays();
var a = [1, 2, 1, 0, 2, 1, 6, 4, 2];
var b = [2, 4, 6, 7];
var c = [5, 5, 2, 4, 6, 7];
// Get the size
var l1 = a.length;
var l2 = b.length;
var l3 = c.length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
main();
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
# Python 3 Program
# Count strictly decreasing subarrays
class Subarrays :
# Display given list elements
def printArr(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
def countDecreasingArr(self, arr, n) :
count = 0
# Set zero to all slot
dp = [0] * (n)
i = 1
while (i < n) :
if (arr[i - 1] > arr[i]) :
# When decreasing sublist occurs
dp[i] = dp[i - 1] + 1
# Add counter
count += dp[i]
i += 1
self.printArr(arr, n)
print(" Decreasing subarrays : ", count ," ")
def main() :
task = Subarrays()
a = [1, 2, 1, 0, 2, 1, 6, 4, 2]
b = [2, 4, 6, 7]
c = [5, 5, 2, 4, 6, 7]
# Get the size
l1 = len(a)
l2 = len(b)
l3 = len(c)
# Test A
# arr = [1,2,1,0,2,1,6,4,2]
# --------------------------
# ➀ [2,1]
# ➁ [2,1,0]
# ➂ [1,0]
# ➃ [2,1]
# ➄ [6,4]
# ➅ [4,2]
# ➆ [6,4,2]
# ---------------
# Total : 7
task.countDecreasingArr(a, l1)
# Test B
# arr = [5,5,2,4,6,7]
# --------------------------
# No decreasing sublist
# ---------------
# Total : 0
task.countDecreasingArr(b, l2)
# Test C
# arr = [5,5,2,4,6,7]
# --------------------------
# ➀ [5,2]
# ---------------
# Total : 1
task.countDecreasingArr(c, l3)
if __name__ == "__main__": main()
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
# Ruby Program
# Count strictly decreasing subarrays
class Subarrays
# Display given array elements
def printArr(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
def countDecreasingArr(arr, n)
count = 0
# Set zero to all slot
dp = Array.new(n) {0}
i = 1
while (i < n)
if (arr[i - 1] > arr[i])
# When decreasing subarray occurs
dp[i] = dp[i - 1] + 1
# Add counter
count += dp[i]
end
i += 1
end
self.printArr(arr, n)
print(" Decreasing subarrays : ", count ," \n")
end
end
def main()
task = Subarrays.new()
a = [1, 2, 1, 0, 2, 1, 6, 4, 2]
b = [2, 4, 6, 7]
c = [5, 5, 2, 4, 6, 7]
# Get the size
l1 = a.length
l2 = b.length
l3 = c.length
# Test A
# arr = [1,2,1,0,2,1,6,4,2]
# --------------------------
# ➀ [2,1]
# ➁ [2,1,0]
# ➂ [1,0]
# ➃ [2,1]
# ➄ [6,4]
# ➅ [4,2]
# ➆ [6,4,2]
# ---------------
# Total : 7
task.countDecreasingArr(a, l1)
# Test B
# arr = [5,5,2,4,6,7]
# --------------------------
# No decreasing subarray
# ---------------
# Total : 0
task.countDecreasingArr(b, l2)
# Test C
# arr = [5,5,2,4,6,7]
# --------------------------
# ➀ [5,2]
# ---------------
# Total : 1
task.countDecreasingArr(c, l3)
end
main()
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Scala Program
Count strictly decreasing subarrays
*/
class Subarrays()
{
// Display given array elements
def printArr(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
def countDecreasingArr(arr: Array[Int], n: Int): Unit = {
var count: Int = 0;
// Set zero to all slot
var dp: Array[Int] = Array.fill[Int](n)(0);
var i: Int = 1;
while (i < n)
{
if (arr(i - 1) > arr(i))
{
// When decreasing subarray occurs
dp(i) = dp(i - 1) + 1;
// Add counter
count += dp(i);
}
i += 1;
}
printArr(arr, n);
print(" Decreasing subarrays : " + count + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarrays = new Subarrays();
var a: Array[Int] = Array(1, 2, 1, 0, 2, 1, 6, 4, 2);
var b: Array[Int] = Array(2, 4, 6, 7);
var c: Array[Int] = Array(5, 5, 2, 4, 6, 7);
// Get the size
var l1: Int = a.length;
var l2: Int = b.length;
var l3: Int = c.length;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
import Foundation;
/*
Swift 4 Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
func printArr(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func countDecreasingArr(_ arr: [Int], _ n: Int)
{
var count: Int = 0;
// Set zero to all slot
var dp: [Int] = Array(repeating: 0, count: n);
var i: Int = 1;
while (i < n)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
i += 1;
}
self.printArr(arr, n);
print(" Decreasing subarrays : ", count ," ");
}
}
func main()
{
let task: Subarrays = Subarrays();
let a: [Int] = [1, 2, 1, 0, 2, 1, 6, 4, 2];
let b: [Int] = [2, 4, 6, 7];
let c: [Int] = [5, 5, 2, 4, 6, 7];
// Get the size
let l1: Int = a.count;
let l2: Int = b.count;
let l3: Int = c.count;
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
main();
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
/*
Kotlin Program
Count strictly decreasing subarrays
*/
class Subarrays
{
// Display given array elements
fun printArr(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
fun countDecreasingArr(arr: Array < Int > , n: Int): Unit
{
var count: Int = 0;
// Set zero to all slot
val dp: Array < Int > = Array(n)
{
0
};
var i: Int = 1;
while (i < n)
{
if (arr[i - 1] > arr[i])
{
// When decreasing subarray occurs
dp[i] = dp[i - 1] + 1;
// Add counter
count += dp[i];
}
i += 1;
}
this.printArr(arr, n);
print(" Decreasing subarrays : " + count + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Subarrays = Subarrays();
val a: Array < Int > = arrayOf(1, 2, 1, 0, 2, 1, 6, 4, 2);
val b: Array < Int > = arrayOf(2, 4, 6, 7);
val c: Array < Int > = arrayOf(5, 5, 2, 4, 6, 7);
// Get the size
val l1: Int = a.count();
val l2: Int = b.count();
val l3: Int = c.count();
// Test A
// arr = [1,2,1,0,2,1,6,4,2]
// --------------------------
// ➀ [2,1]
// ➁ [2,1,0]
// ➂ [1,0]
// ➃ [2,1]
// ➄ [6,4]
// ➅ [4,2]
// ➆ [6,4,2]
// ---------------
// Total : 7
task.countDecreasingArr(a, l1);
// Test B
// arr = [5,5,2,4,6,7]
// --------------------------
// No decreasing subarray
// ---------------
// Total : 0
task.countDecreasingArr(b, l2);
// Test C
// arr = [5,5,2,4,6,7]
// --------------------------
// ➀ [5,2]
// ---------------
// Total : 1
task.countDecreasingArr(c, l3);
}
Output
1 2 1 0 2 1 6 4 2
Decreasing subarrays : 7
2 4 6 7
Decreasing subarrays : 0
5 5 2 4 6 7
Decreasing subarrays : 1
Time Complexity
The time complexity of this solution is O(n), where n is the size of the input array. This is because we iterate through the array once to calculate the count of strictly decreasing subarrays.
The space complexity of the solution is O(n) as well, as we need to allocate an auxiliary array of the same size as the input array.
Output:
1 2 1 0 2 1 6 4 2
Decreasing subarrays: 7
2 4 6 7
Decreasing subarrays: 0
5 5 2 4 6 7
Decreasing subarrays: 1
This implementation correctly counts the number of strictly decreasing subarrays in the given arrays and displays the results.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment