Dada una array arr[] que consta de N enteros, la tarea es dividir la array en dos subarreglos no vacíos de modo que cada elemento presente en el subarreglo derecho sea estrictamente mayor que cada elemento presente en el subarreglo izquierdo. Si es posible hacerlo, imprima los dos subarreglos resultantes . De lo contrario, escriba «Imposible».
Ejemplos:
Entrada: arr[] = {5, 3, 2, 7, 9}
Salida:
5 3 2
7 9
Explicación:
Una de las posibles particiones es {5, 3, 2} y {7, 9}.
El mínimo del segundo subarreglo {7} es mayor que el máximo del primer subarreglo (5).Entrada: arr[] = {1,1,1,1,1}
Salida: Imposible
Explicación:
No hay partición posible para esta array.
Enfoque ingenuo: el enfoque más simple es recorrer la array y, para cada índice, verificar si el máximo del primer subarreglo es menor que el mínimo del segundo subarreglo o no. Si se encuentra que es cierto, imprima los dos subarreglos.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar : O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar calculando la array máxima de prefijos y la array mínima de sufijos, lo que da como resultado el cálculo en tiempo constante del máximo del primer subarreglo y el mínimo del segundo subarreglo . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos min[], para almacenar la array de sufijos mínimos.
- Inicialice 3 variables, digamos ind , mini y maxi, para almacenar el índice de partición, el mínimo del sufijo y el máximo del prefijo, respectivamente.
- Recorra la array en reversa y actualice mini como mini = min (mini, arr[i]) . Asigne mini a min[i].
- Ahora, recorra la array arr[] y realice las siguientes operaciones:
- Actualice maxi como maxi =max(maxi, arr[i]).
- Si i+1 < N así como maxi < min[i+1] , imprima la partición hecha en el índice i y rompa.
- Después de completar los pasos anteriores, si no se cumple ninguno de los casos anteriores, imprima » Imposible».
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 condition
void 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 Code
int 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 approach
import 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 approach
import sys
# Function to partition the array
# into two non-empty subarrays
# which satisfies the given condition
def 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 Code
arr = [ 5, 3, 2, 7, 9 ]
N = 5
partitionArray(arr, N)
# This code is contributed by sanjoy_62.
C#
// C# program of the above approach
using 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>
Producción:
5 3 2 7 9
Complejidad temporal: O(N)
Espacio auxiliar: O(N)