Count Subarrays with strictly decreasing consecutive elements

0 0 6 minutes read

Given an array arr[] containing integers. The task is to find the number of decreasing subarrays with a difference of 1.

Examples:

Input: arr[] = {3, 2, 1, 4}
Output: 7
Explanation: Following are the possible decreasing subarrays with difference 1.
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]Therefore, the answer is 7.

Input: arr[] = {5, 4, 3, 2, 1, 6}
Output: 16

Naive Approach: This problem can be solved by using Dynamic Programming. Follow the steps below to solve the given problem.

For every index i the task is to calculate number of subarrays ending at i which follows this pattern arr[i-2]==arr[i-1]+1, arr[i-1]==arr[i]+1.
Initialize a variable say ans = 0, to store the number of decreasing subarrays with a difference of 1.
We can make a dp[] array which stores the count of these continuous elements for every index.
dp[i] is the number of subarrays ending at i which follows this pattern.
Traverse dp[] and add each value in ans.
Return ans as the final result.

Below is the implementation of the above approach.

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of
// decreasing subarrays with difference 1
long long getcount(vector<int>& p)
{
    int size = p.size(), cnt = 0;
    long long ans = 0;
    vector<int> dp(size, cnt);
    for (int i = 0; i < size; i++) {
        if (i == 0)
            cnt = 1;
        else if (p[i] + 1 == p[i - 1])
            cnt++;
        else
            cnt = 1;
        dp[i] = cnt;
    }
    for (int i = 0; i < size; i++)
        ans += dp[i];
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr{ 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    cout << getcount(arr);
 
    return 0;
}

Java

// Java code to implement the above approach
import java.util.*;
public class GFG
{
 
  // Function to count number of
  // decreasing subarrays with difference 1
  static long getcount(int p[])
  {
    int size = p.length, cnt = 0;
    long ans = 0;
 
    int dp[] = new int[size];
    for(int i = 0; i < size; i++) {
      dp[i] = cnt;
    }
 
    for (int i = 0; i < size; i++) {
      if (i == 0)
        cnt = 1;
      else if (p[i] + 1 == p[i - 1])
        cnt++;
      else
        cnt = 1;
      dp[i] = cnt;
    }
    for (int i = 0; i < size; i++)
      ans += dp[i];
    return ans;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int arr[] = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    System.out.println(getcount(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python code to implement the above approach
 
# Function to count number of
# decreasing subarrays with difference 1
def getcount(p):
    size = len(p)
    cnt = 0
    ans = 0
    dp = [cnt for i in range(size)]
    for i in range(size):
        if (i == 0):
            cnt = 1
        elif (p[i] + 1 == p[i - 1]):
            cnt += 1
        else:
            cnt = 1
        dp[i] = cnt
         
    for i in range(size):
        ans += dp[i]
    return ans
 
# Driver Code
arr = [5, 4, 3, 2, 1, 6]
 
# Function Call
print(getcount(arr))
 
# This code is contributed by Shubham Singh

C#

// C# code to implement the above approach
using System;
class GFG
{
   
  // Function to count number of
  // decreasing subarrays with difference 1
  static long getcount(int []p)
  {
    int size = p.Length, cnt = 0;
    long ans = 0;
 
    int []dp = new int[size];
    for(int i = 0; i < size; i++) {
      dp[i] = cnt;
    }
 
    for (int i = 0; i < size; i++) {
      if (i == 0)
        cnt = 1;
      else if (p[i] + 1 == p[i - 1])
        cnt++;
      else
        cnt = 1;
      dp[i] = cnt;
    }
    for (int i = 0; i < size; i++)
      ans += dp[i];
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int []arr = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    Console.Write(getcount(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
// JavaScript program for above approach 
 
// Function to count number of decreasing
// subarrays with difference 1
function getcount(p)
{
    let size = p.length, cnt = 0;
    let ans = 0;
    let dp = new Array(size).fill(cnt);
     
    for(let i = 0; i < size; i++) 
    {
        if (i == 0)
            cnt = 1;
        else if (p[i] + 1 == p[i - 1])
            cnt++;
        else
            cnt = 1;
             
        dp[i] = cnt;
    }
    for(let i = 0; i < size; i++)
        ans += dp[i];
         
    return ans;
}
 
// Driver Code
let arr = [ 5, 4, 3, 2, 1, 6 ];
 
// Function Call
document.write(getcount(arr));
 
// This code is contributed by Potta Lokesh
 
</script>

Output

Time complexity: O(N)
Auxiliary Space: O(N)

Efficient Approach: In the above approach the auxiliary space complexity can be further optimized to constant space by replacing dp[] array with a variable to keep track of the current number of subarrays. Follow the steps below to solve the given problem.

Initialize a variable say count = 0.
Start traversing the array when arr[i]-arr[i-1 ]==1 to make a chain of numbers that are decreasing by 1, then count++.
Add the count to the ans.
When the chain breaks that means, arr[i]-arr[i-1] !=1 then reset the count.
Return ans as the final result.

Below is the implementation of the above approach.

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// decreasing subarrays with difference 1
long long getcount(vector<int>& arr)
{
    long long int ans = arr.size();
    long long int count = 0;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i - 1] - arr[i] == 1)
            count++;
        else
            count = 0;
        ans = ans + count;
    }
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr{ 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    cout << getcount(arr);
 
    return 0;
}

Java

// Java program for above approach
class GFG
{
 
  // Function to count the number of
  // decreasing subarrays with difference 1
  static long getcount(int[] arr)
  {
    int ans = arr.length;
    int count = 0;
    for (int i = 1; i < arr.length; i++) {
      if (arr[i - 1] - arr[i] == 1)
        count++;
      else
        count = 0;
      ans = ans + count;
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    System.out.print(getcount(arr));
 
  }
}
 
// This code is contributed by 29AjayKumar

Python3

#Python program for the above approach
 
# Function to count the number of
# decreasing subarrays with difference 1
def getcount(arr):
    ans = len(arr)
    count = 0
    for i in range(1, len(arr)):
        if (arr[i - 1] - arr[i] == 1):
            count+=1
        else:
            count = 0
        ans = ans + count
         
    return ans
 
  # Driver Code
arr = [ 5, 4, 3, 2, 1, 6 ]
 
# Function Call
print(getcount(arr))
 
# This code is contributed by Shubham Singh

C#

// C# program for above approach
using System;
 
public class GFG
{
 
  // Function to count the number of
  // decreasing subarrays with difference 1
  static long getcount(int[] arr)
  {
    int ans = arr.Length;
    int count = 0;
    for (int i = 1; i < arr.Length; i++) {
      if (arr[i - 1] - arr[i] == 1)
        count++;
      else
        count = 0;
      ans = ans + count;
    }
    return ans;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] arr = { 5, 4, 3, 2, 1, 6 };
 
    // Function Call
    Console.Write(getcount(arr));
 
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program for above approach 
 
// Function to count the number of
  // decreasing subarrays with difference 1
  function getcount(arr)
  {
    var ans = arr.length;
    var count = 0;
    for (var i = 1; i < arr.length; i++) {
      if (arr[i - 1] - arr[i] == 1)
        count++;
      else
        count = 0;
      ans = ans + count;
    }
    return ans;
  }
 
  // Driver Code
var arr = [ 5, 4, 3, 2, 1, 6 ];
 
// Function Call
document.write(getcount(arr));
 
// This code is contributed by 29AjayKumar 
</script>

Output

Time complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!