Given an array arr[] consisting of N integers, the task is to partition the array into two non-empty subarrays such that every element present in the right subarray is strictly greater than every element present in the left subarray. If it is possible to do so, then print the two resultant subarrays. Otherwise, print “Impossible”.
Examples:
Input: arr[] = {5, 3, 2, 7, 9}
Output:
5 3 2
7 9
Explanation:
One of the possible partition is {5, 3, 2} and {7, 9}.
The minimum of 2nd subarray {7} is greater than the maximum of the first subarray (5).Input: arr[] = {1,1,1,1,1}
Output: Impossible
Explanation:
There is no partition possible for this array.
Naive Approach: The simplest approach is to traverse the array and for every index, check if the maximum of the first subarray is less than the minimum of the second subarray or not. If found to be true, then print the two subarrays.
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to partition the array// into two non-empty subarrays// which satisfies the given conditionvoid partitionArray(vector<int>& arr, int n){ for (int i = 0; i < n - 1; i++) { int leftMax = arr[0]; int j = 0; for (; j <= i; j++) { leftMax = max(leftMax, arr[j]); } int rightMin = arr[j]; for (int k = j; k < n; k++) { rightMin = min(rightMin, arr[k]); } if (rightMin > leftMax) { for (int l = 0; l <= i; l++) { cout << arr[l] << " "; } cout << endl; for (int o = j; o < n; o++) { cout << arr[o] << " "; } return; } } cout << "Impossible" << endl;}// Driver Codeint main(){ vector<int> arr = { 5, 3, 2, 7, 9 }; int N = 5; partitionArray(arr, N); return 0;} |
Java
import java.util.Arrays;import java.util.List;public class Gfg { // Function to partition the array // into two non-empty subarrays // which satisfies the given condition static void partitionArray(List<Integer> arr, int n) { for (int i = 0; i < n - 1; i++) { int leftMax = arr.get(0); int j = 0; for (; j <= i; j++) { leftMax = Math.max(leftMax, arr.get(j)); } int rightMin = arr.get(j); for (int k = j; k < n; k++) { rightMin = Math.min(rightMin, arr.get(k)); } if (rightMin > leftMax) { for (int l = 0; l <= i; l++) { System.out.print(arr.get(l) + " "); } System.out.println(); for (int o = j; o < n; o++) { System.out.print(arr.get(o) + " "); } return; } } System.out.println("Impossible"); } public static void main(String[] args) { List<Integer> arr = Arrays.asList(5, 3, 2, 7, 9); int N = 5; partitionArray(arr, N); }} |
Python3
# Python program of the above approach# Function to partition the array# into two non-empty subarrays# which satisfies the given conditiondef partitionArray(arr, n): for i in range(0,n-1): leftMax = arr[0]; j = 0; for j in range(0,i+1): leftMax = max(leftMax, arr[j]); j=i+1; rightMin = arr[j]; for k in range(j,n): rightMin = min(rightMin, arr[k]); if (rightMin > leftMax) : for l in range(0,i+1): print(arr[l] , end= " "); print(); for o in range(j,n): print(arr[o] , end=" "); return; print("Impossible");# Driver Codearr = [ 5, 3, 2, 7, 9 ];N = 5;partitionArray(arr, N); |
C#
using System;using System.Collections.Generic;class Gfg { static void partitionArray(List<int> arr, int n) { for (int i = 0; i < n - 1; i++) { int leftMax = arr[0]; int j = 0; for (; j <= i; j++) { leftMax = Math.Max(leftMax, arr[j]); } int rightMin = arr[j]; for (int k = j; k < n; k++) { rightMin = Math.Min(rightMin, arr[k]); } if (rightMin > leftMax) { for (int l = 0; l <= i; l++) { Console.Write(arr[l] + " "); } Console.WriteLine(); for (int o = j; o < n; o++) { Console.Write(arr[o] + " "); } return; } } Console.WriteLine("Impossible"); } public static void Main(string[] args) { List<int> arr = new List<int>() { 5, 3, 2, 7, 9 }; int N = 5; partitionArray(arr, N); }} |
Javascript
// Javascript program of the above approach// Function to partition the array// into two non-empty subarrays// which satisfies the given conditionfunction partitionArray(arr, n){ for (let i = 0; i < n - 1; i++) { let leftMax = arr[0]; let j = 0; for (; j <= i; j++) { leftMax = Math.max(leftMax, arr[j]); } let rightMin = arr[j]; for (let k = j; k < n; k++) { rightMin = Math.min(rightMin, arr[k]); } if (rightMin > leftMax) { for (let l = 0; l <= i; l++) { console.log(arr[l] , " "); } console.log("\n"); for (let o = j; o < n; o++) { console.log(arr[o] , " "); } return; } } console.log("Impossible");}// Driver Codelet arr = [ 5, 3, 2, 7, 9 ];let N = 5;partitionArray(arr, N);// This code is contributed by agrawalpoojaa976. |
Output
5 3 2 7 9
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by calculating the prefix maximum array and suffix minimum array which results in the constant time calculation of the maximum of the first subarray and minimum of 2nd subarray. Follow the steps below to solve the problem:
- Initialize an array, say min[], to store the minimum suffix array.
- Initialize 3 variables, say ind, mini and maxi, to store the index of partition, minimum of the suffix, and the maximum of the prefix respectively.
- Traverse the array in reverse and update mini as mini = min (mini, arr[i]). Assign mini to min[i].
- Now, traverse the array arr[] and perform the following operations:
- Update maxi as maxi =max(maxi, arr[i]).
- If i+1 < N as well as maxi < min[i+1], then print the partition made at index i and break.
- After completing the above steps, if none of the above cases are satisfied, then print “Impossible”.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to partition the array// into two non-empty subarrays// which satisfies the given conditionvoid partitionArray(int *a, int n){ // Stores the suffix Min array int *Min = new int[n]; // Stores the Minimum of a suffix int Mini = INT_MAX; // Traverse the array in reverse for (int i = n - 1; i >= 0; i--) { // Update Minimum Mini = min(Mini, a[i]); // Store the Minimum Min[i] = Mini; } // Stores the Maximum value of a prefix int Maxi = INT_MIN; // Stores the index of the partition int ind = -1; for (int i = 0; i < n - 1; i++) { // Update Max Maxi = max(Maxi, a[i]); // If Max is less than Min[i+1] if (Maxi < Min[i + 1]) { // Store the index // of partition ind = i; // break break; } } // If ind is not -1 if (ind != -1) { // Print the first subarray for (int i = 0; i <= ind; i++) cout << a[i] << " "; cout << endl; // Print the second subarray for (int i = ind + 1; i < n; i++) cout << a[i] << " "; } // Otherwise else cout << "Impossible";}// Driver Codeint main(){ int arr[] = { 5, 3, 2, 7, 9 }; int N = 5; partitionArray(arr, N); return 0;}// This code is contributed by Shubhamsingh10 |
Java
// Java program of the above approachimport java.util.*;class GFG { // Function to partition the array // into two non-empty subarrays // which satisfies the given condition static void partitionArray(int a[], int n) { // Stores the suffix min array int min[] = new int[n]; // Stores the minimum of a suffix int mini = Integer.MAX_VALUE; // Traverse the array in reverse for (int i = n - 1; i >= 0; i--) { // Update minimum mini = Math.min(mini, a[i]); // Store the minimum min[i] = mini; } // Stores the maximum value of a prefix int maxi = Integer.MIN_VALUE; // Stores the index of the partition int ind = -1; for (int i = 0; i < n - 1; i++) { // Update max maxi = Math.max(maxi, a[i]); // If max is less than min[i+1] if (maxi < min[i + 1]) { // Store the index // of partition ind = i; // break break; } } // If ind is not -1 if (ind != -1) { // Print the first subarray for (int i = 0; i <= ind; i++) System.out.print(a[i] + " "); System.out.println(); // Print the second subarray for (int i = ind + 1; i < n; i++) System.out.print(a[i] + " "); } // Otherwise else System.out.println("Impossible"); } // Driver Code public static void main(String[] args) { int arr[] = { 5, 3, 2, 7, 9 }; int N = arr.length; partitionArray(arr, N); }} |
Python3
# Python3 program for the above approachimport sys# Function to partition the array# into two non-empty subarrays# which satisfies the given conditiondef partitionArray(a, n): # Stores the suffix Min array Min = [0] * n # Stores the Minimum of a suffix Mini = sys.maxsize # Traverse the array in reverse for i in range(n - 1, -1, -1): # Update Minimum Mini = min(Mini, a[i]) # Store the Minimum Min[i] = Mini # Stores the Maximum value of a prefix Maxi = -sys.maxsize - 1 # Stores the index of the partition ind = -1 for i in range(n - 1): # Update Max Maxi = max(Maxi, a[i]) # If Max is less than Min[i+1] if (Maxi < Min[i + 1]): # Store the index # of partition ind = i # break break # If ind is not -1 if (ind != -1): # Print first subarray for i in range(ind + 1): print(a[i], end=" ") print() # Print second subarray for i in range(ind + 1, n, 1): print(a[i], end=" ") # Otherwise else: print("Impossible")# Driver Codearr = [5, 3, 2, 7, 9]N = 5partitionArray(arr, N)# This code is contributed by sanjoy_62. |
C#
// C# program of the above approachusing System;class GFG { // Function to partition the array // into two non-empty subarrays // which satisfies the given condition static void partitionArray(int[] a, int n) { // Stores the suffix min array int[] min = new int[n]; // Stores the minimum of a suffix int mini = Int32.MaxValue; // Traverse the array in reverse for (int i = n - 1; i >= 0; i--) { // Update minimum mini = Math.Min(mini, a[i]); // Store the minimum min[i] = mini; } // Stores the maximum value of a prefix int maxi = Int32.MinValue; // Stores the index of the partition int ind = -1; for (int i = 0; i < n - 1; i++) { // Update max maxi = Math.Max(maxi, a[i]); // If max is less than min[i+1] if (maxi < min[i + 1]) { // Store the index // of partition ind = i; // break break; } } // If ind is not -1 if (ind != -1) { // Print the first subarray for (int i = 0; i <= ind; i++) Console.Write(a[i] + " "); Console.WriteLine(); // Print the second subarray for (int i = ind + 1; i < n; i++) Console.Write(a[i] + " "); } // Otherwise else Console.Write("Impossible"); } // Driver Code public static void Main(string[] args) { int[] arr = { 5, 3, 2, 7, 9 }; int N = arr.Length; partitionArray(arr, N); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript program of the above approach // Function to partition the array// into two non-empty subarrays// which satisfies the given condition function partitionArray(a , n) { // Stores the suffix min array var min = Array(n).fill(0); // Stores the minimum of a suffix var mini = Number.MAX_VALUE; // Traverse the array in reverse for (i = n - 1; i >= 0; i--) { // Update minimum mini = Math.min(mini, a[i]); // Store the minimum min[i] = mini; } // Stores the maximum value of a prefix var maxi = Number.MIN_VALUE; // Stores the index of the partition var ind = -1; for (i = 0; i < n - 1; i++) { // Update max maxi = Math.max(maxi, a[i]); // If max is less than min[i+1] if (maxi < min[i + 1]) { // Store the index // of partition ind = i; // break break; } } // If ind is not -1 if (ind != -1) { // Print the first subarray for (i = 0; i <= ind; i++) document.write(a[i] + " "); document.write("<br/>"); // Print the second subarray for (i = ind + 1; i < n; i++) document.write(a[i] + " "); } // Otherwise else document.write("Impossible"); } // Driver Code var arr = [ 5, 3, 2, 7, 9 ]; var N = arr.length; partitionArray(arr, N);// This code contributed by Rajput-Ji</script> |
Output
5 3 2 7 9
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
