Posted on by Kalkicode
Code Dynamic Programming

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.

Comment

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