Data Modelling & AI Data Structure & Algorithm

Split an array into minimum number of non-increasing or non-decreasing subarrays

23 June 2025

0

Given an array arr[] of size N, the task is to split the given array into a minimum number of subarrays such that elements of each subarray are either in non-increasing order or non-decreasing order.

Examples:

Input: arr[] = {2, 3, 9, 5, 4, 6, 8}
Output: 3
Explanation: Split the array into 3 subarrays following three subarrays:

{2, 3, 9} (non-decreasing)

{5, 4} (non-increasing)

{6, 8} (non-decreasing)

Input: arr[] = {2, 5, 3, 3, 4, 5, 0, 2, 1, 0}
Output: 4
Explanation: Split the array into following 4 subarray:

{2, 5} (non-decreasing)

{3, 3, 4, 5} (non-decreasing)

{0, 2} (non-decreasing)

{1, 0} (non-increasing)

Approach: To minimize the number of subarrays, the size of each subarray should be maximized. It can be done by placing the elements in subarrays greedily.

Follow the steps below to solve the problem:

Initialize a variable, say ans, with 1 to store the required result and current with N to keep track of the order of the current sequence, whether it is non-decreasing(I), non-increasing(D), or none(N).
Now, iterate over the array in the range [1, N – 1]:
- If the current is equal to N, do the following:
  - If arr[i] < arr[i-1] then update current as D.
  - Otherwise, if arr[i] > arr[i-1], then update current as I.
  - Otherwise, update current as N.
- If the current is equal to I, do the following:
  - If arr[i]?arr[i-1] then update current as I.
  - Otherwise, update current as N and increment ans by 1.
- Otherwise, do the following:
  - If arr[i] ? arr[i-1], then update current as D.
  - Otherwise, update current as N and increment ans by 1.
After the above steps, print the value of ans as the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to split the array into minimum count
// of subarrays such that each subarray is either
// non-increasing or non-decreasing
void minimumSubarrays(int arr[], int n)
{
 
  // Initialize variable to keep
  // track of current sequence
  char current = 'N';
 
  // Stores the required result
  int answer = 1;
 
  // Traverse the array, arr[]
  for (int i = 1; i < n; i++) {
 
    // If current sequence is neither
    // non-increasing nor non-decreasing
    if (current == 'N') {
 
      // If previous element is greater
      if (arr[i] < arr[i - 1]) {
 
        // Update current
        current = 'D';
      }
 
      // If previous element is equal
      // to the current element
      else if (arr[i] == arr[i - 1]) {
 
        // Update current
        current = 'N';
      }
 
      // Otherwise
      else {
 
        // Update current
        current = 'I';
      }
    }
 
    // If current sequence
    // is in non-decreasing
    else if (current == 'I') {
 
      // If previous element is
      // less than or equal to
      // the current element
      if (arr[i] >= arr[i - 1]) {
        current = 'I';
      }
 
      // Otherwise
      else {
 
        // Update current as N and
        // increment answer by 1
        current = 'N';
        answer += 1;
      }
    }
 
    // If current sequence
    // is Non-Increasing
    else {
 
      // If previous element is
      // greater or equal to
      // the current element
      if (arr[i] <= arr[i - 1]) {
        current = 'D';
      }
 
      // Otherwise
      else {
 
        // Update current as N and
        // increment answer by 1
        current = 'N';
        answer += 1;
      }
    }
  }
 
  // Print the answer
  cout<<answer;
}
 
// Driver Code
int main() {
 
  // Given array
  int arr[] = { 2, 3, 9, 5, 4, 6, 8 };
 
  // Given size of array
  int n = sizeof(arr) / sizeof(arr[0]);
 
  minimumSubarrays(arr, n);
  return 0;
}
 
// This code is contributed by shikhasingrajput

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to split the array into minimum count
    // of subarrays such that each subarray is either
    // non-increasing or non-decreasing
    static void minimumSubarrays(int[] arr, int n)
    {
 
        // Initialize variable to keep
        // track of current sequence
        char current = 'N';
 
        // Stores the required result
        int answer = 1;
 
        // Traverse the array, arr[]
        for (int i = 1; i < n; i++) {
 
            // If current sequence is neither
            // non-increasing nor non-decreasing
            if (current == 'N') {
 
                // If previous element is greater
                if (arr[i] < arr[i - 1]) {
 
                    // Update current
                    current = 'D';
                }
 
                // If previous element is equal
                // to the current element
                else if (arr[i] == arr[i - 1]) {
 
                    // Update current
                    current = 'N';
                }
 
                // Otherwise
                else {
 
                    // Update current
                    current = 'I';
                }
            }
 
            // If current sequence
            // is in non-decreasing
            else if (current == 'I') {
 
                // If previous element is
                // less than or equal to
                // the current element
                if (arr[i] >= arr[i - 1]) {
                    current = 'I';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
 
            // If current sequence
            // is Non-Increasing
            else {
 
                // If previous element is
                // greater or equal to
                // the current element
                if (arr[i] <= arr[i - 1]) {
                    current = 'D';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
        }
 
        // Print the answer
        System.out.print(answer);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given array
        int arr[] = { 2, 3, 9, 5, 4, 6, 8 };
 
        // Given size of array
        int n = arr.length;
 
        minimumSubarrays(arr, n);
    }
}

Python3

# Python3 program for the above approach
 
# Function to split the array into minimum count
# of subarrays such that each subarray is either
# non-increasing or non-decreasing
def minimumSubarrays(arr, n):
 
    # Initialize variable to keep
    # track of current sequence
    current = 'N'
 
    # Stores the required result
    answer = 1
 
    # Traverse the array, arr[]
    for i in range(1, n):
 
        # If current sequence is neither
        # non-increasing nor non-decreasing
        if (current == 'N'):
 
            # If previous element is greater
            if (arr[i] < arr[i - 1]):
 
                # Update current
                current = 'D'
 
            # If previous element is equal
            # to the current element
            elif (arr[i] == arr[i - 1]):
 
                # Update current
                current = 'N'
 
            # Otherwise
            else:
 
                # Update current
                current = 'I'
 
        # If current sequence
        # is in non-decreasing
        elif (current == 'I'):
 
            #I f previous element is
            # less than or equal to
            # the current element
            if (arr[i] >= arr[i - 1]):
                current = 'I'
 
            # Otherwise
            else:
 
                # Update current as N and
                # increment answer by 1
                current = 'N'
                answer += 1
 
        # If current sequence
        # is Non-Increasing
        else:
 
            # If previous element is
            # greater or equal to
            # the current element
            if (arr[i] <= arr[i - 1]):
                current = 'D'
 
            # Otherwise
            else:
 
                # Update current as N and
                # increment answer by 1
                current = 'N'
                answer += 1
 
    # Print the answer
    print(answer)
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [ 2, 3, 9, 5, 4, 6, 8 ]
 
    # Given size of array
    n = len(arr)
     
    minimumSubarrays(arr, n)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG 
{
 
    // Function to split the array into minimum count
    // of subarrays such that each subarray is either
    // non-increasing or non-decreasing
    static void minimumSubarrays(int[] arr, int n)
    {
 
        // Initialize variable to keep
        // track of current sequence
        char current = 'N';
 
        // Stores the required result
        int answer = 1;
 
        // Traverse the array, []arr
        for (int i = 1; i < n; i++) {
 
            // If current sequence is neither
            // non-increasing nor non-decreasing
            if (current == 'N') {
 
                // If previous element is greater
                if (arr[i] < arr[i - 1]) {
 
                    // Update current
                    current = 'D';
                }
 
                // If previous element is equal
                // to the current element
                else if (arr[i] == arr[i - 1]) {
 
                    // Update current
                    current = 'N';
                }
 
                // Otherwise
                else {
 
                    // Update current
                    current = 'I';
                }
            }
 
            // If current sequence
            // is in non-decreasing
            else if (current == 'I') {
 
                // If previous element is
                // less than or equal to
                // the current element
                if (arr[i] >= arr[i - 1]) {
                    current = 'I';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
 
            // If current sequence
            // is Non-Increasing
            else {
 
                // If previous element is
                // greater or equal to
                // the current element
                if (arr[i] <= arr[i - 1]) {
                    current = 'D';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
        }
 
        // Print the answer
        Console.Write(answer);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        // Given array
        int []arr = { 2, 3, 9, 5, 4, 6, 8 };
 
        // Given size of array
        int n = arr.Length;
 
        minimumSubarrays(arr, n);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Java script program for the above approach
 
 
 
    // Function to split the array into minimum count
    // of subarrays such that each subarray is either
    // non-increasing or non-decreasing
    function minimumSubarrays(arr,n)
    {
 
        // Initialize variable to keep
        // track of current sequence
        let current = 'N';
 
        // Stores the required result
        let answer = 1;
 
        // Traverse the array, arr[]
        for (let i = 1; i < n; i++) {
 
            // If current sequence is neither
            // non-increasing nor non-decreasing
            if (current == 'N') {
 
                // If previous element is greater
                if (arr[i] < arr[i - 1]) {
 
                    // Update current
                    current = 'D';
                }
 
                // If previous element is equal
                // to the current element
                else if (arr[i] == arr[i - 1]) {
 
                    // Update current
                    current = 'N';
                }
 
                // Otherwise
                else {
 
                    // Update current
                    current = 'I';
                }
            }
 
            // If current sequence
            // is in non-decreasing
            else if (current == 'I') {
 
                // If previous element is
                // less than or equal to
                // the current element
                if (arr[i] >= arr[i - 1]) {
                    current = 'I';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
 
            // If current sequence
            // is Non-Increasing
            else {
 
                // If previous element is
                // greater or equal to
                // the current element
                if (arr[i] <= arr[i - 1]) {
                    current = 'D';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
        }
 
        // Print the answer
        document.write(answer);
    }
 
    // Driver Code
     
        // Given array
        let arr = [ 2, 3, 9, 5, 4, 6, 8 ];
 
        // Given size of array
        let n = arr.length;
 
        minimumSubarrays(arr, n);
 
// contributed by sravan kumar
</script>

Output:

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

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

Split an array into minimum number of non-increasing or non-decreasing subarrays

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

I’ve taken heat for defending the Google Pixel 10, but the sales numbers prove I’m right

7 Android security settings I change first on every new phone

I dropped these 5 habits — and Google Maps navigation instantly got faster

10 Best Antivirus Black Friday/Cyber Monday Deals 2025 by Katarina Glamoslija

EDITOR PICKS

I’ve taken heat for defending the Google Pixel 10, but the sales numbers prove I’m right

7 Android security settings I change first on every new phone

I dropped these 5 habits — and Google Maps navigation instantly got faster

POPULAR POSTS

I’ve taken heat for defending the Google Pixel 10, but the sales numbers prove I’m right

7 Android security settings I change first on every new phone

I dropped these 5 habits — and Google Maps navigation instantly got faster

POPULAR CATEGORY

ABOUT US

FOLLOW US