Split an array into minimum number of non-increasing or non-decreasing subarrays
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.
- If the current is equal to N, do the following:
- 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:
3
Time Complexity: O(N)
Auxiliary Space: O(1)