Given an array arr[] of size N, the task is to rearrange the array elements such that the count of local minima in the array is maximum.
Note: An element arr[x] is said to be a local minimum if it is less than or equal to both its adjacent elements. The first and last array elements can’t be considered as local minima.
Examples:
Input: arr[]= {1, 2, 3, 4, 5}
Output: 3 1 4 2 5
Explanation:
Rearranging array elements to {3, 1, 4, 2, 5}. The count of local minima in the array is 2, i.e. {arr[1], arr[3]}, which is the maximum possible count of local minima that can be obtained from the array. Therefore, the required output is 3 1 4 2 5.Input: arr[]= {1, 2, 3, 4, 5, 6}
Output: 4 1 5 2 6 3
Approach: The idea is to use sorting algorithms and two pointer technique to solve this problem. Follow the steps below to solve this problem:
- Sort the array in ascending order.
- Initialize two variables, say left = 0 and right = N / 2 to store the index of the left and right pointers respectively.
- Traverse the array and in each traversal, first print the value of arr[right] and then print the value of arr[left] and increment the value of left and right by 1.
Below is the implementation for the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange array elements to// maximize count of local minima in the arrayvoid rearrangeArrMaxcntMinima(int arr[], int N){ // Sort the array in // ascending order sort(arr, arr + N); // Stores index of // left pointer int left = 0; // Stores index of // right pointer int right = N / 2; // Traverse the array elements while (left < N / 2 || right < N) { // if right is less than N if (right < N) { // Print array element cout << arr[right] << " "; // Update right right++; } if (left < N / 2) { // Print array element cout << arr[left] << " "; // Update left left++; } }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); rearrangeArrMaxcntMinima(arr, N); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to rearrange array elements to// maximize count of local minima in the arraystatic void rearrangeArrMaxcntMinima(int arr[], int N){ // Sort the array in // ascending order Arrays.sort(arr); // Stores index of // left pointer int left = 0; // Stores index of // right pointer int right = N / 2; // Traverse the array elements while (left < N / 2 || right < N) { // If right is less than N if (right < N) { // Print array element System.out.print(arr[right] + " "); // Update right right++; } if (left < N / 2) { // Print array element System.out.print(arr[left] + " "); // Update left left++; } }} // Driver Codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 4, 5 }; int N = arr.length; rearrangeArrMaxcntMinima(arr, N);}}// This code is contributed by code_hunt |
Python3
# Python3 program to implement# the above approach# Function to rearrange array # elements to maximize count of # local minima in the arraydef rearrangeArrMaxcntMinima(arr, N): # Sort the array in # ascending order arr.sort() # Stores index of # left pointer left = 0 # Stores index of # right pointer right = N // 2 # Traverse the array elements while (left < N // 2 or right < N): # if right is less # than N if (right < N): # Print array element print(arr[right], end = " ") # Update right right += 1 if (left < N // 2): # Print array element print(arr[left], end = " ") # Update left left += 1# Driver Codeif __name__ == "__main__": arr = [1, 2, 3, 4, 5] N = len(arr) rearrangeArrMaxcntMinima(arr, N)# This code is contributed by Chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to rearrange array elements to// maximize count of local minima in the arraystatic void rearrangeArrMaxcntMinima(int []arr, int N){ // Sort the array in // ascending order Array.Sort(arr); // Stores index of // left pointer int left = 0; // Stores index of // right pointer int right = N / 2; // Traverse the array elements while (left < N / 2 || right < N) { // If right is less than N if (right < N) { // Print array element Console.Write(arr[right] + " "); // Update right right++; } if (left < N / 2) { // Print array element Console.Write(arr[left] + " "); // Update left left++; } }} // Driver Codepublic static void Main(String[] args){ int []arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; rearrangeArrMaxcntMinima(arr, N);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to implement// the above approach// Function to rearrange array elements to// maximize count of local minima in the arrayfunction rearrangeArrMaxcntMinima(arr, N){ // Sort the array in // ascending order arr.sort(function(a, b){return a - b;}); // Stores index of // left pointer let left = 0; // Stores index of // right pointer let right = Math.floor(N / 2); // Traverse the array elements while (left < Math.floor(N / 2) || right < N) { // If right is less than N if (right < N) { // Print array element document.write(arr[right] + " "); // Update right right++; } if (left < Math.floor(N / 2)) { // Print array element document.write(arr[left] + " "); // Update left left++; } }}// Driver Codelet arr = [ 1, 2, 3, 4, 5 ];let N = arr.length;rearrangeArrMaxcntMinima(arr, N);// This code is contributed by avanitrachhadiya2155</script> |
Output:
3 1 4 2 5
Time Complexity: O(N log(N))
Auxiliary Space:O(1)
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!
