Number of strictly increasing subarrays

Given an array, this function will find the number of strictly increasing subarrays. This can be clearly explained in below example

Example

Input :
arr[] = {4, 8, 7, 10, 11}

Output :
4
The input array has 4 strictly increasing subarrays ie, {4, 8}, {7, 10}, {7, 10, 11}, {10, 11}

Time Complexity:O( ),

where m is the number of subarrays in the output.

This method will use the fact that if the subarray arr[i,j] is  not strictly increasing then arr[i,j+1], arr[i,j+2], ...., arr[i,n-1] cannot be strictly increasing

Algorithm

1. Simply create two loops

2. In the outer loop select an element till end of the array. ie, i=0 to n-1, where n is the size

3. In the inner loop select an element from i+1 to n-1. ie, j=i+1 to n-1

4. Check if the array is increasing ie, arr[j]>arr[j-1]. If it is increasing, increment the count of number of subarrays strictly increasing by 1.

5. else, break the inner loop.

C++ Program

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

int incSubarray(int arr[], int n) //this function returns the number of strictly inc subarrays
{
	int count = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i+1; j < n; ++j)
		{
			if(arr[j]>arr[j-1]) //if it is inc, increment the count
			{
				count++;
			}
			else
			{
				break; //if it is not strictly inc, break
			}
		}
	}
	return count;
}
int main()
{
	int arr[]= {4,8,7,10,11};  //creating an array
	int n = sizeof(arr)/sizeof(arr[0]); //size of the array
	cout<<"Number of strictly increasing subarrays are "<<incSubarray(arr, n);
	return 0;
}
Try It

Time Complexity : O(n)

In this method, we will use the fact that the sorted array of length l will have (l)*(l-1)/2 strictly increasing subarrays

Algorithm

1. Initialize count to 0 and length to 1.

2. Till end of the array

3. If the array is increasing ie, arr[i+1]>arr[i], then increment the length by 1. else, increment count by (length)(length-1)/2 and make length =1.

4. After traversing the array, if the length is greater than 1, then increment count by (length)(length-1)/2.

5. return count.

C++ Program

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

int incSubarray(int arr[], int n) //this function returns the number of strictly inc subarrays
{
	int count = 0;
	int length = 1;
	for (int i = 0; i < n; ++i)
	{
		if(arr[i+1] > arr[i])
		{
			length++;
		}
		else
		{
			count = count + (length)*(length -1)/2;
			length = 1;
		}
	}
	return count;
}
int main()
{
	int arr[]= {4,8,7,10,11};  //creating an array
	int n = sizeof(arr)/sizeof(arr[0]); //size of the array
	cout<<"Number of strictly increasing subarrays are "<<incSubarray(arr, n);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top