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

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

UFS 5.0 is on the way, but most Android users probably won’t notice

Android’s backup settings are returning to their former glory

EDITOR PICKS

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

UFS 5.0 is on the way, but most Android users probably won’t notice

POPULAR POSTS

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

UFS 5.0 is on the way, but most Android users probably won’t notice

POPULAR CATEGORY

ABOUT US

FOLLOW US