Given an array, arr[] of size N, the task is to rearrange the array elements to maximize the count of triplets (i, j, k) that satisfy the condition arr[i] > arr[j] < arr[k] and i < j < k.
Examples:
Input: arr[] = {1, 4, 3, 3, 2, 2, 5}
Output:
Count of triplets: 3
Array: {3, 1, 3, 2, 4, 2, 5}
Explanation:
Rearrange the array to {3, 1, 3, 2, 4, 2, 5} which gives the maximum count of triplets {(3, 1, 3), (3, 2, 4), (4, 2, 5)} that satisfies the given condition.
Therefore, the required count of triplets is 3.Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 7}
Output:
Count of triplets = 3
Array = {5, 1, 6, 2, 7, 3, 7, 4}
Naive Approach: The simplest approach to solve the problem is to generate all possible permutations of the array and count the number of triplets that satisfy the given condition. Finally, print the count of triplets and the permutations of the given array which contain the maximum count of triplets with the given condition.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to first sort the given array and place the first half of the given array at odd indexes and the last half of the array at even indexes in a temporary array. Finally, print the temporary array and count of triplets with the given condition. Follow the steps below to solve the problem:
- Initialize a temporary array, say temp[], to store the permutations of the given array.
- Sort the given array, arr[].
- Place the first half of the given array at odd indexes of the temp array.
- Place the last half of the given array at even indexes of the temp array.
- Finally, print the count of triplets with the given conditions in temp[] and temp array.
Below are the implementations of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange the array// to maximize the count of tripletsvoid ctTriplets(int arr[], int N){ // Sort the given array sort(arr, arr + N); // Stores the permutations // of the given array vector<int> temp(N); // Stores the index // of the given array int index = 0; // Place the first half // of the given array for (int i = 1; i < N; i += 2) { temp[i] = arr[index++]; } // Place the last half // of the given array for (int i = 0; i < N; i += 2) { temp[i] = arr[index++]; } // Stores the count // of triplets int ct = 0; for (int i = 0; i < N; i++) { // Check the given conditions if (i > 0 && i + 1 < N) { if (temp[i] < temp[i + 1] && temp[i] < temp[i - 1]) { ct++; } } } cout << "Count of triplets:" << ct << endl; cout << "Array:"; for (int i = 0; i < N; i++) { cout << temp[i] << " "; }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); ctTriplets(arr, N);} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.Arrays; class GFG{ // Function to rearrange the array// to maximize the count of tripletsstatic void ctTriplets(int arr[], int N){ // Sort the given array Arrays.sort(arr); // Stores the permutations // of the given array int[] temp = new int[N]; // Stores the index // of the given array int index = 0; // Place the first half // of the given array for(int i = 1; i < N; i += 2) { temp[i] = arr[index++]; } // Place the last half // of the given array for(int i = 0; i < N; i += 2) { temp[i] = arr[index++]; } // Stores the count // of triplets int ct = 0; for(int i = 0; i < N; i++) { // Check the given conditions if (i > 0 && i + 1 < N) { if (temp[i] < temp[i + 1] && temp[i] < temp[i - 1]) { ct++; } } } System.out.println("Count of triplets:" + ct ); System.out.print("Array:"); for(int i = 0; i < N; i++) { System.out.print(temp[i] + " "); }} // Driver Codepublic static void main (String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = arr.length; ctTriplets(arr, N);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement# the above approach # Function to rearrange the array# to maximize the count of tripletsdef ctTriplets(arr, N): # Sort the given array arr.sort() # Stores the permutations # of the given array temp = [0] * N # Stores the index # of the given array index = 0 # Place the first half # of the given array for i in range(1, N, 2): temp[i] = arr[index] index += 1 # Place the last half # of the given array for i in range(0, N, 2): temp[i] = arr[index] index += 1 # Stores the count # of triplets ct = 0 for i in range(N): # Check the given conditions if (i > 0 and i + 1 < N): if (temp[i] < temp[i + 1] and temp[i] < temp[i - 1]): ct += 1 print("Count of triplets:", ct) print("Array:", end = "") for i in range(N): print(temp[i], end = " ") # Driver Codearr = [ 1, 2, 3, 4, 5, 6 ]N = len(arr)ctTriplets(arr, N)# This code is contributed by sanjoy_62 |
C#
// C# program to implement// the above approachusing System; class GFG{ // Function to rearrange the array// to maximize the count of tripletsstatic void ctTriplets(int[] arr, int N){ // Sort the given array Array.Sort(arr); // Stores the permutations // of the given array int[] temp = new int[N]; // Stores the index // of the given array int index = 0; // Place the first half // of the given array for(int i = 1; i < N; i += 2) { temp[i] = arr[index++]; } // Place the last half // of the given array for(int i = 0; i < N; i += 2) { temp[i] = arr[index++]; } // Stores the count // of triplets int ct = 0; for(int i = 0; i < N; i++) { // Check the given conditions if (i > 0 && i + 1 < N) { if (temp[i] < temp[i + 1] && temp[i] < temp[i - 1]) { ct++; } } } Console.WriteLine("Count of triplets:" + ct ); Console.Write("Array:"); for(int i = 0; i < N; i++) { Console.Write(temp[i] + " "); }} // Driver Codepublic static void Main () { int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; ctTriplets(arr, N);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program to implement// the above approach// Function to rearrange the array// to maximize the count of tripletsfunction ctTriplets(arr, N){ // Sort the given array arr.sort(); // Stores the permutations // of the given array let temp = []; // Stores the index // of the given array let index = 0; // Place the first half // of the given array for(let i = 1; i < N; i += 2) { temp[i] = arr[index++]; } // Place the last half // of the given array for(let i = 0; i < N; i += 2) { temp[i] = arr[index++]; } // Stores the count // of triplets let ct = 0; for(let i = 0; i < N; i++) { // Check the given conditions if (i > 0 && i + 1 < N) { if (temp[i] < temp[i + 1] && temp[i] < temp[i - 1]) { ct++; } } } document.write("Count of triplets:" + ct + "<br/>"); document.write("Array:"); for(let i = 0; i < N; i++) { document.write(temp[i] + " "); }}// Driver Code let arr = [ 1, 2, 3, 4, 5, 6 ]; let N = arr.length; ctTriplets(arr, N);// This code is contributed by target_2.</script> |
Output:
Count of triplets:2 Array:4 1 5 2 6 3
Time Complexity: O(N*log(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!
