Given an array arr[] of size N, the task is to rearrange the array to achieve the maximum possible score, keeping the absolute difference of the first and last element as minimum as possible. The distribution of score is given as:
- If arr[i] < arr[i+1], increment score by 1.
- Else keep the score same.
Examples:
Input: N = 5, arr[] = {5, 7, 9, 5, 8}
Output: {5, 7, 8, 9, 5}
Explanation: After rearranging the array, absolute difference of first and last element = abs(5 – 5) = 0, which is the minimum possible.
Maximum score that can be achieved :
- arr[0] < arr[1], score = 1
- arr[1] < arr[2], score = 2
- arr[2] > arr[3], score = 3
- arr[3] > arr[4], score = 3
Input: N = 4, arr[] = {6, 4, 1, 3}
Output: {3, 6, 1, 4}
Approach: The given problem can be solved by the greedy approach. Follow the below steps to solve the problem:
- Sort the array and find the smallest absolute difference between every pair of adjacent elements and store the index of it say ind.
- Now, work only with elements left apart from these two elements at indices (ind – 1 and ind). These two elements will be the first and last elements of the required array.
- Solve the problem by storing the remaining elements in the following two ways:
- First store the elements in the res array which are greater than the element at index (ind – 1).
- Then, store the elements in the res array which are less or equal to the element at index (ind).
- In the end, push the last element i.e, the element at index (ind), and return the res vector.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to rearrange the array to// achieve the maximum scorevector<int> rearrangeArray(vector<int> arr){ int min_diff = INT_MAX; int ind = -1; int n = arr.size(); // Sort the array sort(arr.begin(), arr.end()); // Iterate the array and find the // minimum difference between two // elements along with its index for (int i = 1; i < n; i++) { if (abs(arr[i] - arr[i - 1]) < min_diff) { min_diff = abs(arr[i] - arr[i - 1]); ind = i; } } // Vector to store the rearranged // elements vector<int> res; // Push the element at (ind - 1) res.push_back(arr[ind - 1]); // Traverse the array and push the // elements in res which are greater // than the element at index (ind - 1) for (int i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr[i] > arr[ind - 1]) { res.push_back(arr[i]); } } // Again traverse the array and push the // elements in res which are less or equal // to the element at index (ind) for (int i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr[i] <= arr[ind]) { res.push_back(arr[i]); } } // At the end, push the element at (ind) res.push_back(arr[ind]); // Return res vector return res;}// Driver Codeint main(){ vector<int> arr = { 5, 7, 9, 5, 8 }; vector<int> res = rearrangeArray(arr); for (auto it : res) cout << it << " "; return 0;} |
Java
// Java implementation of the above approachimport java.util.*;public class GFG{ // Function to rearrange the array to// achieve the maximum scorestatic ArrayList<Integer> rearrangeArray(ArrayList<Integer> arr){ int min_diff = Integer.MAX_VALUE; int ind = -1; int n = arr.size(); // Sort the array Collections.sort(arr); // Iterate the array and find the // minimum difference between two // elements along with its index for (int i = 1; i < n; i++) { if (Math.abs(arr.get(i) - arr.get(i - 1)) < min_diff) { min_diff = Math.abs(arr.get(i) - arr.get(i - 1)); ind = i; } } // Vector to store the rearranged // elements ArrayList<Integer> res = new ArrayList<Integer>(); // Push the element at (ind - 1) res.add(arr.get(ind - 1)); // Traverse the array and push the // elements in res which are greater // than the element at index (ind - 1) for (int i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr.get(i) > arr.get(ind - 1)) { res.add(arr.get(i)); } } // Again traverse the array and push the // elements in res which are less or equal // to the element at index (ind) for (int i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr.get(i) <= arr.get(ind)) { res.add(arr.get(i)); } } // At the end, push the element at (ind) res.add(arr.get(ind)); // Return res return res;}// Driver Codepublic static void main(String args[]){ ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add(5); arr.add(7); arr.add(9); arr.add(5); arr.add(8); ArrayList<Integer> res = rearrangeArray(arr); for (int i = 0; i < res.size(); i++) { System.out.print(res.get(i) + " "); }}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach# Function to rearrange the array to# achieve the maximum scoredef rearrangeArray(arr): min_diff = 9999999 ind = -1 n = len(arr) # Sort the array arr.sort() # Iterate the array and find the # minimum difference between two # elements along with its index for i in range(n): if abs(arr[i] - arr[i - 1]) < min_diff: min_diff = abs(arr[i] - arr[i - 1]) ind = i # Vector to store the rearranged # elements res = [] # Push the element at (ind - 1) res.append(arr[ind - 1]) # Traverse the array and push the # elements in res which are greater # than the element at index (ind - 1) for i in range(n): if i == ind or i == ind - 1: continue if arr[i] > arr[ind - 1]: res.append(arr[i]) # Again traverse the array and push the # elements in res which are less or equal # to the element at index (ind) for i in range(n): if i == ind or i == ind - 1 : continue; if arr[i] <= arr[ind] : res.append(arr[i]) # At the end, push the element at (ind) res.append(arr[ind]) # Return res vector return res # Driver Codearr = [ 5, 7, 9, 5, 8 ]res = rearrangeArray(arr)for i in range(len(res)): print(str(res[i]),end =" ")# This code is contributed by Potta Lokesh |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG{ // Function to rearrange the array to// achieve the maximum scorestatic List<int> rearrangeArray(List<int> arr){ int min_diff = Int32.MaxValue; int ind = -1; int n = arr.Count; // Sort the array arr.Sort(); // Iterate the array and find the // minimum difference between two // elements along with its index for (int i = 1; i < n; i++) { if (Math.Abs(arr[i] - arr[i - 1]) < min_diff) { min_diff = Math.Abs(arr[i] - arr[i - 1]); ind = i; } } // Vector to store the rearranged // elements List<int> res = new List<int>(); // Push the element at (ind - 1) res.Add(arr[ind - 1]); // Traverse the array and push the // elements in res which are greater // than the element at index (ind - 1) for (int i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr[i] > arr[ind - 1]) { res.Add(arr[i]); } } // Again traverse the array and push the // elements in res which are less or equal // to the element at index (ind) for (int i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr[i] <= arr[ind]) { res.Add(arr[i]); } } // At the end, push the element at (ind) res.Add(arr[ind]); // Return res return res;}// Driver Codepublic static void Main(){ List<int> arr = new List<int>(); arr.Add(5); arr.Add(7); arr.Add(9); arr.Add(5); arr.Add(8); List<int> res = rearrangeArray(arr); foreach(int k in res) Console.Write(k + " ");}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript implementation of the above approach// Function to rearrange the array to// achieve the maximum scorefunction rearrangeArray(arr){ let min_diff = Number.MAX_SAFE_INTEGER; let ind = -1; let n = arr.length; // Sort the array arr.sort(); // Iterate the array and find the // minimum difference between two // elements along with its index for (let i = 1; i < n; i++) { if (Math.abs(arr[i] - arr[i - 1]) < min_diff) { min_diff = Math.abs(arr[i] - arr[i - 1]); ind = i; } } // Vector to store the rearranged // elements let res = []; // Push the element at (ind - 1) res.push(arr[ind - 1]); // Traverse the array and push the // elements in res which are greater // than the element at index (ind - 1) for (let i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr[i] > arr[ind - 1]) { res.push(arr[i]); } } // Again traverse the array and push the // elements in res which are less or equal // to the element at index (ind) for (let i = 0; i < n; i++) { if (i == ind || i == ind - 1) { continue; } if (arr[i] <= arr[ind]) { res.push(arr[i]); } } // At the end, push the element at (ind) res.push(arr[ind]); // Return res vector return res;}// Driver Codelet arr = [ 5, 7, 9, 5, 8 ];let res = rearrangeArray(arr);for (let i = 0; i < res.length; i++) document.write(res[i] + " "); // This code is contributed by Samim Hossain Mundal.</script> |
Output
5 7 8 9 5
Time Complexity: O(n logn)
Auxiliary Space: O(n)
