Count Strictly Increasing Subarrays

Given an integer array arr[], the task is to count the number of subarrays in arr[] that are strictly increasing and have a size of at least 2. A subarray is a contiguous sequence of elements from arr[]. A subarray is strictly increasing if each element is greater than its previous element.

Examples:

Input: arr[] = [1, 4, 5, 3, 7, 9]
Output: 6
Explanation: The strictly increasing subarrays are: [1, 4], [1, 4, 5], [4, 5], [3, 7], [3, 7, 9], [7, 9]

Input: arr[] = [1, 3, 3, 2, 3, 5]
Output: 4
Explanation: The strictly increasing subarrays are: [1, 3], [2, 3], [2, 3, 5], [3, 5]

Input: arr[] = [2, 2, 2, 2]
Output: 0
Explanation: No strictly increasing subarray exists.

[Naive Approach] Check All Subarrays - O(n²) Time and O(1) Space

The idea is to count all strictly increasing subarrays by expanding from each starting index i., we run an inner loop for ending point j, we extend j while the sequence remains increasing and stop immediately when it breaks.

// C++ Code to count strictly increasing 
// subarrays using Better Approach
#include <bits/stdc++.h>
using namespace std;

// Function to count strictly increasing 
// subarrays
int countIncreasing(vector<int>& arr) {
    
    int n = arr.size();
    int count = 0;

    // Iterate over all possible subarrays
    for (int i = 0; i < n; i++) {
        
        // Start from index i
        for (int j = i + 1; j < n; j++) {
            
            // If the sequence breaks, stop early
            if (arr[j - 1] >= arr[j]) {
                break;
            }

            // Otherwise, count the valid subarray
            count++;
        }
    }

    return count;
}

// Driver code
int main() {
    
    vector<int> arr = {1, 4, 5, 3, 7, 9};
    
    cout << countIncreasing(arr) << endl;
    
    return 0;
}

// Java Code to count strictly increasing 
// subarrays using Better Approach
import java.util.*;

class GfG {

    // Function to count strictly increasing 
    // subarrays
    static int countIncreasing(int[] arr) {
        
        int n = arr.length;
        int count = 0;

        // Iterate over all possible subarrays
        for (int i = 0; i < n; i++) {
            
            // Start from index i
            for (int j = i + 1; j < n; j++) {
                
                // If the sequence breaks, stop early
                if (arr[j - 1] >= arr[j]) {
                    break;
                }

                // Otherwise, count the valid subarray
                count++;
            }
        }

        return count;
    }

    // Driver code
    public static void main(String[] args) {
        
        int[] arr = {1, 4, 5, 3, 7, 9};
        
        System.out.println(countIncreasing(arr));
    }
}

# Python Code to count strictly increasing 
# subarrays using Better Approach

# Function to count strictly increasing 
# subarrays
def countIncreasing(arr):
    
    n = len(arr)
    count = 0

    # Iterate over all possible subarrays
    for i in range(n):
        
        # Start from index i
        for j in range(i + 1, n):
            
            # If the sequence breaks, stop early
            if arr[j - 1] >= arr[j]:
                break

            # Otherwise, count the valid subarray
            count += 1

    return count

# Driver code
if __name__ == "__main__":
    
    arr = [1, 4, 5, 3, 7, 9]
    
    print(countIncreasing(arr))

// C# Code to count strictly increasing 
// subarrays using Better Approach
using System;

class GfG {

    // Function to count strictly increasing 
    // subarrays
    public static int countIncreasing(int[] arr) {
        
        int n = arr.Length;
        int count = 0;

        // Iterate over all possible subarrays
        for (int i = 0; i < n; i++) {
            
            // Start from index i
            for (int j = i + 1; j < n; j++) {
                
                // If the sequence breaks, stop early
                if (arr[j - 1] >= arr[j]) {
                    break;
                }

                // Otherwise, count the valid subarray
                count++;
            }
        }

        return count;
    }

    // Driver code
    public static void Main() {
        
        int[] arr = {1, 4, 5, 3, 7, 9};
        
        Console.WriteLine(countIncreasing(arr));
    }
}

// JavaScript Code to count strictly increasing 
// subarrays using Better Approach

// Function to count strictly increasing 
// subarrays
function countIncreasing(arr) {
    
    let n = arr.length;
    let count = 0;

    // Iterate over all possible subarrays
    for (let i = 0; i < n; i++) {
        
        // Start from index i
        for (let j = i + 1; j < n; j++) {
            
            // If the sequence breaks, stop early
            if (arr[j - 1] >= arr[j]) {
                break;
            }

            // Otherwise, count the valid subarray
            count++;
        }
    }

    return count;
}

// Driver code
let arr = [1, 4, 5, 3, 7, 9];

console.log(countIncreasing(arr));

6

[Expected Approach] Using Subarray Count Formula - O(n) Time and O(1) Space

The idea is to count all strictly increasing subarrays efficiently by using a single pass through the array. Instead of checking every subarray explicitly, we track the length of increasing segments using len. When a decreasing element is encountered, we use the formula (len * (len - 1)) / 2 to count subarrays formed by the segment and then reset len. Finally, we add the remaining subarrays after the loop ends.

Steps to implement the above idea:

• Initialize count to store the number of strictly increasing subarrays and len to track the length of increasing sequences.
• Iterate through the array starting from index 1, comparing each element with its previous element to check for increasing order.
• If the current element is greater than the previous, increment len as it extends the increasing subarray.
• If the current element breaks the increasing sequence, update count using the formula (len*(len-1))/2 and reset len to 1.
• Continue iterating until the end of the array, applying the same logic for each increasing and non-increasing sequence.
• After the loop, add the remaining subarrays count using (len * (len - 1)) / 2 to include the last segment.
• Finally, return count, which holds the total number of strictly increasing subarrays in the given array.

// C++ Code to count strictly increasing 
// subarrays using Length based Formula
#include <bits/stdc++.h>
using namespace std;

// Function to count strictly increasing 
// subarrays
int countIncreasing(vector<int>& arr) {
    
    int n = arr.size();
    int count = 0;
    int len = 1;

    // Iterate through the array
    for (int i = 1; i < n; i++) {
        
        // If current element is greater than 
        // previous, increase len
        if (arr[i] > arr[i - 1]) {
            len++;
        } 
        
        else {
            
            // Add subarrays count and reset len
            count += (len * (len - 1)) / 2;
            len = 1;
        }
    }

    // Add remaining subarrays count
    count += (len * (len - 1)) / 2;

    return count;
}

// Driver code
int main() {
    
    vector<int> arr = {1, 4, 5, 3, 7, 9};
    
    cout << countIncreasing(arr) << endl;
    
    return 0;
}

// Java Code to count strictly increasing 
// subarrays using Length based Formula
class GfG {

    // Function to count strictly increasing 
    // subarrays
    static int countIncreasing(int[] arr) {
        
        int n = arr.length;
        int count = 0;
        int len = 1;

        // Iterate through the array
        for (int i = 1; i < n; i++) {
            
            // If current element is greater than 
            // previous, increase len
            if (arr[i] > arr[i - 1]) {
                len++;
            } 
            
            else {
                
                // Add subarrays count and reset len
                count += (len * (len - 1)) / 2;
                len = 1;
            }
        }

        // Add remaining subarrays count
        count += (len * (len - 1)) / 2;

        return count;
    }

    // Driver code
    public static void main(String[] args) {
        
        int[] arr = {1, 4, 5, 3, 7, 9};
        
        System.out.println(countIncreasing(arr));
    }
}

# Python Code to count strictly increasing 
# subarrays using Length based Formula

# Function to count strictly increasing 
# subarrays
def countIncreasing(arr):
    
    n = len(arr)
    count = 0
    len = 1

    # Iterate through the array
    for i in range(1, n):
        
        # If current element is greater than 
        # previous, increase len
        if arr[i] > arr[i - 1]:
            len += 1
        
        else:
            
            # Add subarrays count and reset len
            count += (len * (len - 1)) // 2
            len = 1

    # Add remaining subarrays count
    count += (len * (len - 1)) // 2

    return count

# Driver code
if __name__ == "__main__":
    
    arr = [1, 4, 5, 3, 7, 9]
    
    print(countIncreasing(arr))

// C# Code to count strictly increasing 
// subarrays using Length based Formula
using System;

class GfG {

    // Function to count strictly increasing 
    // subarrays
    static int countIncreasing(int[] arr) {
        
        int n = arr.Length;
        int count = 0;
        int len = 1;

        // Iterate through the array
        for (int i = 1; i < n; i++) {
            
            // If current element is greater than 
            // previous, increase len
            if (arr[i] > arr[i - 1]) {
                len++;
            } 
            
            else {
                
                // Add subarrays count and reset len
                count += (len * (len - 1)) / 2;
                len = 1;
            }
        }

        // Add remaining subarrays count
        count += (len * (len - 1)) / 2;

        return count;
    }

    // Driver code
    static void Main() {
        
        int[] arr = {1, 4, 5, 3, 7, 9};
        
        Console.WriteLine(countIncreasing(arr));
    }
}

// JavaScript Code to count strictly increasing 
// subarrays using Length based Formula

// Function to count strictly increasing 
// subarrays
function countIncreasing(arr) {
    
    let n = arr.length;
    let count = 0;
    let len = 1;

    // Iterate through the array
    for (let i = 1; i < n; i++) {
        
        // If current element is greater than 
        // previous, increase len
        if (arr[i] > arr[i - 1]) {
            len++;
        } 
        
        else {
            
            // Add subarrays count and reset len
            count += (len * (len - 1)) / 2;
            len = 1;
        }
    }

    // Add remaining subarrays count
    count += (len * (len - 1)) / 2;

    return count;
}

// Driver code
let arr = [1, 4, 5, 3, 7, 9];

console.log(countIncreasing(arr));

6