Approach
This coding challenge can be solved using a greedy approach. Two conditions that the problem demands are:
- Minimum possible absolute difference between the first and last elements
- Maximum score among all rearrangements.
Let's focus on the first one. To identify elements in the array with the minimum absolute difference, we can sort the array and check the absolute difference between adjacent elements. Let ‘IND’ be the index of the first element in such a pair of elements with a minimum absolute difference.
Now, let's focus on the second condition of the problem. Once we have identified the first and last elements, the task is to rearrange the remaining elements in the best way possible to achieve the maximum score. It can be done as follows:
- Create a new array, ‘OPTIMAL_ARRAY’ of size ‘N’ and put ‘OPTIMAL_ARRAY[0] = ARR[IND] and OPTIMAL_ARRAY[N - 1] = ARR[IND + 1].
- From the first index onwards, fill the array with elements greater than ARR[IND] in non-decreasing order.
- Fill the remaining indices with the left-out elements in non-decreasing order.
Algorithm
- Take the input.
- Sort the array.
- Find the index ‘IND’ such that ARR[IND + 1] - ARR[IND] is the minimum possible absolute difference between overall adjacent elements.
- Create a new array ‘OPTIMAL_ARRAY’ to store the rearranged array.
- Update OPTIMAL_ARRAY[0] = ARR[IND] and OPTIMAL_ARRAY[N - 1] = ARR[IND].
-
Loop over the sorted array with current index i and maintain a variable INDEX = 1 to fill the empty indices in the OPTIMAL_ARRAY.
- If the current element ARR[i] is greater than ARR[IND] and i is not equal to either of IND or IND + 1, update OPTIMAL_ARRAY[INDEX++] = ARR[i].
- Fill the remaining elements in the OPTIMAL_ARRAY array with the left-out elements in the sorted array.
Program
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
// Solve for the given input.
void solve(vector<int>& arr, int N)
{
// Sort the array.
sort(arr.begin(), arr.end());
int ind = 0;
// Initial minimum absolute difference.
int difference = arr[1] - arr[0];
for(int i = 1; i < N - 1; i++)
{
// Check for the minimum absolute difference and update if required.
if(difference > arr[i + 1] - arr[i])
{
difference = arr[i + 1] - arr[i];
ind = i;
}
}
// To store the rearranged array.
int optimalArray[N];
// As discussed in the approach.
optimalArray[0] = arr[ind];
optimalArray[N - 1] = arr[ind + 1];
// To fill the remaining positions.
int index = 1;
for(int i = 0; i < N; i++)
{
// First fill the elements greater than optimalArray[0] in non-decreasing order.
if(i != ind && i != ind + 1 && arr[i] > arr[ind])
{
optimalArray[index] = arr[i];
index++;
}
}
// Fill the remaining elements in non-decreasing order.
for(int i = 0; i < N; i++)
{
if(i != ind && i != ind + 1 && arr[i] <= arr[ind])
{
optimalArray[index] = arr[i];
index++;
}
}
// Output the array.
for(int i = 0; i < N; i++)
{
cout<<optimalArray[i]<<" ";
}
cout<<endl;
}
int main()
{
// Take the input.
int N; cin>>N;
vector<int> arr(N);
for(int i = 0; i < N; i++)
{
cin>>arr[i];
}
// Solve for the given input.
solve(arr, N);
}

You can also try this code with Online C++ Compiler
Run Code
Input
6
6 3 10 13 20 25
Output
3 10 13 20 25 6
Time Complexity
The time complexity of the above approach is O(N * log N), where ‘N’ is the size of the array. It is because we are sorting the array to identify elements satisfying the first condition.
Space Complexity
The space complexity of the above approach is O(N), as we are using extra space to store the rearranged array.
Key Takeaways
In this blog, we discussed a problem based on greedy algorithms. Greedy algorithms are one of the most popular algorithms in technical interviews. It requires critical observations to identify the algorithm. Most of the time, it is easy to code a greedy algorithm, however, we may have to use set/map/multiset to implement a greedy approach in the proposed time limit.
Hence learning never stops, and there is a lot more to learn.
Recommended Problems -
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!