Given an array arr[] consisting of N distinct integers, the task is to rearrange the array elements such that the count of elements that are smaller than their adjacent elements is maximum.
Note: The elements left of index 0 and right of index N-1 are considered as -INF.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 2 1 3 4
Explanation:
One possible way to rearrange is as {2, 1, 3, 4}.
- For arr[0](= 2), is greater than the elements on both sides of it.
- For arr[1](= 1), is less than the elements on both sides of it.
- For arr[2](= 3), is less than the elements on its right and greater than the elements on its left.
- For arr[4](= 1), is greater than the elements on both sides of it.
Therefore, there is a total of 1 array element satisfying the condition in the above arrangement. And it is the maximum possible.
Input: arr[] = {2, 7}
Output: 2 7
Approach: The given problem can be solved based on the following observations:
- Consider the maximum number of indices that can satisfy the conditions being X.
- Then, at least (X + 1) larger elements are required to make it possible as each element requires 2 greater elements.
- Therefore, the maximum number of elements that is smaller than their adjacent is given by (N – 1)/2.
Follow the steps below to solve the problem:
- Initialize an array, say temp[] of size N, that stores the rearranged array.
- Sort the given array arr[] in the increasing order.
- Choose the first (N – 1)/2 elements from the array arr[] and place them at the odd indices in the array temp[].
- Choose the rest of the (N + 1)/2 elements from the array arr[] and place them in the remaining indices in the array temp[].
- Finally, after completing the above steps, print the array temp[] as the resultant array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange array such that// count of element that are smaller than// their adjacent elements is maximumvoid maximumIndices(int arr[], int N){ // Stores the rearranged array int temp[N] = { 0 }; // Stores the maximum count of // elements int maxIndices = (N - 1) / 2; // Sort the given array sort(arr, arr + N); // Place the smallest (N - 1)/2 // elements at odd indices for (int i = 0; i < maxIndices; i++) { temp[2 * i + 1] = arr[i]; } // Placing the rest of the elements // at remaining indices int j = 0; for (int i = maxIndices; i < N;) { // If no element of the array // has been placed here if (temp[j] == 0) { temp[j] = arr[i]; i++; } j++; } // Print the resultant array for (int i = 0; i < N; i++) { cout << temp[i] << " "; }}// Driver Codeint main(){ // Input int arr[] = { 1, 2, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call maximumIndices(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to rearrange array such that // count of element that are smaller than // their adjacent elements is maximum public static void maximumIndices(int arr[], int N) { // Stores the rearranged array int[] temp = new int[N]; // Stores the maximum count of // elements int maxIndices = (N - 1) / 2; // Sort the given array Arrays.sort(arr); // Place the smallest (N - 1)/2 // elements at odd indices for (int i = 0; i < maxIndices; i++) { temp[2 * i + 1] = arr[i]; } // Placing the rest of the elements // at remaining indices int j = 0; for (int i = maxIndices; i < N;) { // If no element of the array // has been placed here if (temp[j] == 0) { temp[j] = arr[i]; i++; } j++; } // Print the resultant array for (int i = 0; i < N; i++) { System.out.print(temp[i] + " "); } } // Driver Code public static void main(String[] args) { // Input int arr[] = { 1, 2, 3, 4 }; int N = 4; // Function call maximumIndices(arr, N); }}// This code is contributed by RohitOberoi. |
Python3
# Python program for the above approach# Function to rearrange array such that# count of element that are smaller than# their adjacent elements is maximumdef maximumIndices(arr, N): # Stores the rearranged array temp = [0] * N # Stores the maximum count of # elements maxIndices = (N - 1) // 2 # Sort the given array arr.sort() # Place the smallest (N - 1)/2 # elements at odd indices for i in range(maxIndices): temp[2 * i + 1] = arr[i] # Placing the rest of the elements # at remaining indices j = 0 i = maxIndices while(i < N): # If no element of the array # has been placed here if (temp[j] == 0): temp[j] = arr[i] i += 1 j += 1 # Print the resultant array for i in range(N): print(temp[i], end=" ")# Driver Code# Inputarr = [1, 2, 3, 4]N = len(arr)# Function callmaximumIndices(arr, N)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{// Function to rearrange array such that// count of element that are smaller than// their adjacent elements is maximumpublic static void maximumIndices(int []arr, int N){ // Stores the rearranged array int[] temp = new int[N]; // Stores the maximum count of // elements int maxIndices = (N - 1) / 2; // Sort the given array Array.Sort(arr); // Place the smallest (N - 1)/2 // elements at odd indices for(int i = 0; i < maxIndices; i++) { temp[2 * i + 1] = arr[i]; } // Placing the rest of the elements // at remaining indices int j = 0; for(int i = maxIndices; i < N;) { // If no element of the array // has been placed here if (temp[j] == 0) { temp[j] = arr[i]; i++; } j++; } // Print the resultant array for(int i = 0; i < N; i++) { Console.Write(temp[i] + " "); }}// Driver Codepublic static void Main(String[] args){ // Input int []arr = { 1, 2, 3, 4 }; int N = 4; // Function call maximumIndices(arr, N);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript program for the above approach // Function to rearrange array such that // count of element that are smaller than // their adjacent elements is maximum function maximumIndices(arr, N) { // Stores the rearranged array let temp = new Array(N).fill(0); // Stores the maximum count of // elements let maxIndices = parseInt((N - 1) / 2); // Sort the given array arr.sort(function (a, b) { return a - b; }) // Place the smallest (N - 1)/2 // elements at odd indices for (let i = 0; i < maxIndices; i++) { temp[2 * i + 1] = arr[i]; } // Placing the rest of the elements // at remaining indices let j = 0; for (let i = maxIndices; i < N;) { // If no element of the array // has been placed here if (temp[j] == 0) { temp[j] = arr[i]; i++; } j++; } // Print the resultant array for (let i = 0; i < N; i++) { document.write(temp[i] + " "); } } // Driver Code // Input let arr = [1, 2, 3, 4]; let N = arr.length; // Function call maximumIndices(arr, N); // This code is contributed by Potta Lokesh </script> |
Output
2 1 3 4
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!
